자료구조와 알고리즘/알고리즘31 Shell Sort 셸 정렬 목표 삽입 정렬을 이해한다. 삽입 정렬을 구현할 수 있다. 삽입 정렬의 시간 복잡도 삽입 정렬에서 장점으로부터 착안된 쉘 정렬을 이해한다. 셸 정렬을 구현할 수 있다. 셸 정렬의 gap sequence에 대해서 이해한다. 셸 정렬의 시간 복잡도 셸 정렬은 삽입 정렬이 어느 정도 정렬된 상태에서 상당히 빠른 정렬 속도를 보인다는 점에서 착안하여 삽입 정렬을 수행하기 전에 어느 정도를 정렬한 상태에서 삽입 정렬을 하면 좋은 시간 복잡도를 기대할 수 있다는 생각에 만들어진 알고리즘이다. 그렇기 때문에 삽입 정렬에 대한 기본적인 이론을 익힌 이후 추가적으로 셸 정렬까지 공부해본다. 삽입 정렬 삽입 정렬은 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하여 자리를 swap 하는 정렬 알고리즘이다. 삽.. 2021. 5. 30. 백 트래킹 기법 1. Back Tracking 백트래킹 혹은 퇴각 검색으로 불려진다. 제약 조건 만족 문제에서 해를 찾기 위한 전략 중 하나로 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약조건을 만족할 수 없다고 판단되는 즉시 다시는 이 후보군을 체킹 하지 않을 것을 표기한 다음 다른 후보군으로 넘어가는 방법이다. 실제 구현시 모든 경우의 수를 상태 공간 트리를 통해 표현한다. - 각 후보군을 DFS 방식으로 확인 1) Promising : 해당 루트가 조건에 맞는지를 검사하는 기법 2) Pruning : 조건에 맞지않으면 포기하여 탐색 시간 절약하는 기법 즉 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는 지제크 하고 조건이 다르다면 더 이상 자식 노드.. 2020. 9. 9. 프림 알고리즘 프림 알고리즘(Prim's algorithm) 대표적인 최소 신장 트리 알고리즘으로 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고 해장 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해나가는 방식이다. 크루스 칼 알고리즘과 프림 알고리즘 두 개의 알고리즘 다 탐욕 알고리즘을 기초로 하고 있다. 다만 크루스칼 알고리즘은 가장 가중치가 작은 간선을 선택하면서 MST를 구하지만 프림 알고리즘은 특정 정점에서 시작해 해정 정점에 연결된 가장 적은 가중치를 가진 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구한다. 파이썬 코드 from collections import def.. 2020. 9. 9. 크루스칼 알고리즘 신장 트리에서도 말했듯이 크루스 칼 알고리즘은 최소 신장 트리를 구현하기 위한 알고리즘이다. 이때 크루스칼의 시간 복잡도를 낮추기 위해 path-compression 기법과 , union-by-rank기법을 사용한다. 구현 트리는 노드와 브랜치로 이루어져 사이클을 돌지 않는 그래프에서 나온 데이터 구조이다. 따라서 그래프를 먼저 생성한다. graph ={ 'vertices' : ['A','B'.....'G'], 'edges' : [ (7,'A','B') .... ] } 여기서 vertices는 노드를 이야기하며 edges는 간선으로 연결된 노드와 간선의 가중치를 의미한다. 변수 선언 parent =dict() //path-compression을 위한 부모 딕셔너리이다. rank = dict() //uni.. 2020. 9. 9. 신장 트리 신장 트리란? Spanning Tree, 또는 신장 트리라 불린다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 말한다. 조건은 다음과 같다 - 본래의 그래프의 모든 노드를 포함해야한다. - 모든 노드가 서로 연결되어야 한다. - 트리의 속성을 만족시켜야 한다. (사이클이 존재하지 않는다.) 최소 신장 트리 MST 가능한 ST 중에서 간선의 가중치 합의 최소인 ST를 지칭한다. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다. 대표적으로 크루스 칼 알고리즘과 프림 알고리즘이 있다. 1) 크루스칼 알고리즘 1. 모든 정점을 독립적인 집합으로 만든다. 2. 모든 간선을 비용 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 .. 2020. 9. 9. 탐욕 알고리즘 탐욕 알고리즘이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리운다. 최적의 해에 가까운 값을 구하기 위해서 사용되며 여러 경우 중 하나를 선택해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종값을 구하는 방식이다. 예를 들어 4720원을 1원 50원 100원 500원으로 지불하되 가장 적은 동전만 낸다고 생각하자. 여러 경우중 500원을 가장 많이내는 경우가 최적이고 그 다음은 100원 ... 이렇게 진행해서 최종값을 구할 수 있게된다. coin_list=[500,100,50,1] price = 4720 def coin(coin_list,price): total_coin =0 details=list() for coin in coin_list: coin_.. 2020. 9. 8. 너비 우선 탐색 && 깊이 우선 탐색 1. BFS와 DFS란? 대표적인 그래프 탐색 알고리즘이다 BFS는 Breadth-First Search약자로 너비 우선 탐색이며 정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색하는 방식이다. 이와 다르게 DFS는 Depth First Search의 약자로 깊이 우선 탐색이며 정점의 자식들을 먼저 탐색하는 방식이다. BFS 알고리즘 구현 자료구조 큐를 사용한다. 각 노드에 연결된 정점의 노드들을 나타낸 표이며 KEY와 VALUE형식으로 나타낸다. 그래프는 위 이미지의 DFS를 따른다. KEY VALUE a b c b a d e c a f g d b h e b i j f c k g c h d i e j e k f 탐색을 위한 큐 방문한 큐 a 최상위 노드의 a를 방문해야 하는 큐에 넣는다. 방문해야 하.. 2020. 9. 8. 병합 정렬 병합 정렬은 재귀 용법을 활용한 정렬 알고리즘이다. 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 병합 정렬은 분할 정복의 알고리즘 기법입니다. 분할 정복은 문제를 부분 문제로 나누며 이때 나누어진 부분 문제는 중복되지 않아야 합니다. 이러한 부분 문제를 통해 상위 문제를 해결하는 방법이며 하향식 즉 아래에서부터 위로 해결하는 방식입니다. 자바 코드 배열을 받아 분할한다. public static List split(List data) { List leftSplit = new ArrayList(); List rightSplit = new ArrayLis.. 2020. 9. 7. 퀵 정렬 퀵 정렬(Quick Sort) 버블 정렬, 선택 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터의 개수가 많을수록 사용하기 힘든 알고리즘입니다. 더욱 빠른 정렬 알고리즘이 필요한데 그중 하나인 퀵 정렬입니다. 퀵 정렬은 말 그대로 엄청나게 빠른 정렬 기법입니다. 이 퀵 정렬은 분할 정복(Divide and Conquer)에 근거하며, 퀵 정렬은 다른 정렬과는 달리 기준값을 하나 택하고 순회를 돌면서 기준값보다 작은 데이터는 좌측에, 기준값보다 큰 데이터는 우측으로 분할하고 다시 퀵 정렬을 적용합니다. 이러한 기준값을 피벗(Pivot)이라고도 하는데 보통 첫 번째 원소를 피벗 값으로 설정하고 사용합니다. 위 그림에서의 과정을 글로 나타내면 아래와 같습니다. 5를 기준값으로.. 2020. 8. 13. 3. 삽입정렬 삽입 정렬은 도대체 어떤 정렬 방식일까요? 간단히 말하면 삽입 정렬은 정렬할 새로운 데이터를 뽑아 적당한 새 위치에 삽입하는 알고리즘이라고 말할 수 있습니다. 삽입 정렬도 버블 정렬과 마찬가지로 구현이 간단하여 많이 사용이 되기도 합니다. 버블 정렬과 선택 정렬 같은 경우 모든 요소를 매번 검사하여 정렬을 했다면 삽입 정렬은 앞의 요소들이 정렬이 되었다는 가정 하에서 해당 요소보다 큰 값들의 맨 앞에 넣어 주도록 구현되어 버블 정렬과 선택 정렬보다는 효율성이 더 좋습니다. 위 그림에서의 과정을 글로 나타내면 아래와 같습니다. 6 과 4를 비교하여 4가 더 작으므로 6 앞으로 4를 삽입한다. 6과 1을 비교하여 1이 더 작으므로 4 앞으로 1을 삽입한다. 6과 7을 비교하여 정렬할 필요가 없으므로 변동 사.. 2020. 8. 11. 이전 1 2 3 4 다음
