알고리즘 & 자료구조

힙 정렬을 공부하기 전에 힙(Heap)이 무엇인지 알아야 한다. 그리고 힙을 알기 전에는 이진트리(Binary Tree)에 대해서 알고 있을 필요가 있다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드이다. 이진트리로 완전 이진트리를 구성할 수 있는데 별 다른 것은 아니고 이진트리의 노드가 중간에 비어있지 않고 빽빽이 가득 찬 구조를 완전 이진트리라고 한다. 즉 아래도 완전 이진트리라고 할 수 있다. 이제 힙을 알아보자. 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있고 최소 힙은 그 반대이다. 그런데 힙 구조 안에서 특정 노드 때문에 최대 힙 구조가 붕괴..

위상 정렬(Topology Sort)는 순서가 정해져 있는 작업들의 수행 순서를 정해주기 위한 알고리즘이다. 예를 들어서 숫자가 하나의 작업이라고 했을 때, 다음과 같이 작업의 순서가 정해져 있다고 가정하자. 1 -> 3 -> 4 3 -> 2 그럼 (1 -> 3 -> 4 -> 2) 또는 (1 -> 3 -> 2 -> 4) 순서로 작업을 수행해야 함을 알 수 있다. 이렇게 정해진 순서를 고려해서 작업의 수행 순서를 결정해주는 알고리즘을 위상 정렬이라고 한다. 주의할 점은 위상 정렬은 DAG(Directed Acyclic Graph) 에만 적용이 가능하다. 위상 정렬이 "작업의 순서를 고려한다"는 점을 생각해보면 당연한 것이다. 사이클이 존재하는 것은 출발 지점이 따로 없다는 것이고 순서도 없다는 의미가 된다..

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표 알고리즘이라고 할 수 있다. 흔히 여러 개의 도시를 최소한의 비용으로 도로를 설치하고자 할 때 실제로 사용되는 알고리즘이라고 한다. 최소 비용 신장 트리란? [Minimum Spanning Tree] 우선 신장 트리란(Spanning Tree) 그래프의 최소 연결 부분 그래프이다. 특징으로는 모든 정점을 포함해야 한다는 것과 가장 적은 간선 개수로 모든 정점을 연결해야 한다는 특징이 있다. 최소 비용 신장 트리란 신장 트리의 특징을 포함하며, 간선의 가중치를 고려해서 최소한의 비용으로 신장 트리를 구성해야한다는 특징을 가지고 있다. 따라서 구성된 그래프의 간선의 합이 최소여야..

다익스트라는 간선에 가중치가 있을 때 출발 정점에서 도착 정점까지의 최단 거리를 구하는 알고리즘이다. 플루이드 와샬도 최단 거리를 구한다는 점은 동일하다. 하지만 플루이드 와샬은 모든 정점에서 모든 정점까지의 최단 거리를 구한다는 점에서 차이가 있다. 또한 다익스트라는 가장 적은 비용의 간선을 선택하지만 플루이드 와샬은 거쳐가는 정점을 정해서 비용을 비교하고 갱신한다. 그림으로 알고리즘의 진행 과정을 살펴보자. 먼저 다음과 같이 그래프에 대해서 인접 행렬을 초기화한다. 이제 1을 거치지 않는 경로와 1을 거쳐가는 경로의 비용을 비교해서 인접 행렬을 갱신해준다. 다음으로 2를 거치지 않는 경로와 2를 거쳐가는 경로의 비용을 비교해서 갱신한다. 다음으로 3 다음으로 4 다음으로 5 최종 모습 이제 소스 코드..

Union find - 합집합을 찾는 대표적인 그래프 알고리즘이다. 합집합 여부를 판별할 수 있기 때문에 서로소 집합 여부도 판별할 수 있어 서로소 집합(Disjoint-set) 알고리즘이라고도 한다. Union find는 여러 개의 노드가 있을 때 두 노드를 선택해서, 현재 같은 그래프(집합)에 속하는지를 판별하는 알고리즘이다. 현재 같은 그래프에 속하는지 여부는 부모를 통해서 알 수 있는데 부모가 같다면 같은 그래프(집합)에 속한다고 볼 수 있는 것이다. 그럼 각 노드 별로 부모를 어떻게 설정하고 비교할 수 있는지 확인해보자. 먼저 아래와 같이 노드가 있다고 하자. 처음에는 모든 노드가 자기 자신을 부모로 설정한다. 그리고 다음과 같이 1과 2가 Union(합침)되면 2의 부모가 1로 변하게 된다. ..

Trie 자료구조는 문자열을 저장하고 주어진 문자열에 겹치는 접두사(문자열)가 있는지 빠르게 검색할 수 있는 트리 자료구조이다. Trie 자료구조가 문자열을 저장하는 방법을 그림으로 살펴보자. 아래 그림은 Trie 자료구조를 이용해서 문자열 "TREE" 와 "TRIE" 를 저장한 모습이다. Trie의 특징은 사용하는 문자열 셋(a~f, A~F, '0'~'9') 을 이용해서 자식 노드를 생성한다는 점과 주어진 문자열을 순회하면서 재귀적으로 자식 노드를 생성한다는 것이다. 위에 그림의 경우 A~F 까지의 문자열 셋을 이용하고 문자 단위로 자식 노드가 생성되는 예시이다. 만약 전화번호를 저장한다면? 0~9 까지의 문자열 셋을 이용하는 것이다. 그럼 Trie 자료구조를 구현해보자. 아래는 영어 소문자로 이루어진..