Algorithm

학습 내용 강한 결합 요소(Strongly Connected Component) 강한 결합 요소란 그래프 안에서 '강하게 결합된 정점 집합'을 의미한다. 서로 긴밀하게 연결되어 있다고 하여 강한 결합 요소라고 말한다. SSC는 '같은 SSC에 속하는 두 정점은 서로 도달이 가능하다'는 특징이 있다. 위의 예시에서 0번 노드부터 4번 노드까지는 서로가 서로에게 도달이 가능하기 때문에 강한 결합 요소라고 할 수 있더. 그러나 2번 노드와 5번 노드의 경우 2번 노드는 4번 노드를 거쳐 5번 노드에 도달할 수 있지만 5번 노드는 2번 노드에 도달할 수 없어 강한 결합 요소라고 할 수 없다. 따라서 예시에서는 3개의 강한 결합 요소 집합이 존재한다. 기본적으로 사이클이 발생하는 경우 무조건 SCC에 해당한다는 ..

학습 내용 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 순서가 정해져 있는 작업의 대표적인 예시는 다음과 같다. 이처럼 작업의 순서가 정해져 있을 때 작업을 정확하게 정렬해 주는 알고리즘이 바로 위상 정렬이며 여러 개의 답이 존재할 수 있다는 특징을 가지고 있다. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 이것은 사이클이 발생하지 않는 방향 그래프를 의미하며 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 왜냐하면 위상 정렬은 반드시 시작점이 존재해야 하는데 그래프에 사이클이 발생한다면 시작점을 찾을 수 없기 때문이다..

학습 내용 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함할 수 없다. 이러한 점에서 다익스트라 알고리즘은 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나이다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.' 즉 , 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를..

학습 내용 에라토스테네스의 체(Eratosthenes Sieve) 에라토스테네스의 체(Eratosthenes Sieve)는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 소수란 '양의 약수를 두 개만 가지는 자연수'를 의미하며 2, 3, 5, 7, 11,... 등이 존재한다. 이러한 소수를 대량으로 빠르고 정확하게 구하는 방법이 에라토스 테네스의 체라고 할 수 있다. 다음은 간단한 소수 판별 코드이다. #include bool isPrimeNumber(int x){ for(int i = 2; i < x; i++) if(x % i == 0) return false; return true; } int main() { printf("%d", isPrimeNumber(97)); return 0..

학습 내용 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍이란 '하나의 문제는 단 한 번만 풀도록 하는 알고리즘'이다. 즉, 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법이다. 일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 한다. 피보나치수열의 점화식: D[i] = D [i - 1] + D [i - 2] 위 공식에 따라서 1, 1, 2, 3, 5, ... 와 같이 나아갈 수 있다. 만약 15번째 피보나치수열을 구한다고 가정..

학습 내용 이진트리의 구현과 순회 알고리즘 이진트리(Binary Tree)는 가장 많이 사용되는 비선형 자료구조로 데이터의 탐색 속도 증진을 위해 사용되는 구조이다. 트리를 구현하기 위해서는 포인터(Pointer)를 이용해 특정한 루트(Root)에서 자식 노드로 접근해야 한다. 이진트리의 노드는 모두 왼쪽 자식과 오른쪽 자식을 가질 수 있도록 설계가 되어있다. 왜 굳이 '포인터'를 사용해서 왼쪽과 오른쪽 자식을 가리킬 수 있도록 하는 것일까? 그 이유는 힙 정렬을 구현할 때는 '완전 이진트리(Complete Binary Tree)'가 사용되었기 때문에 배열로 표현할 수 있지만 완전 이진 트리가 아닌 이진트리는 배열로 표현하기 어렵기 때문이다. 포인터를 사용해 이진 트리를 구현하는 경우 굉장히 유동적으로 ..

학습 내용 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘으로 흔히 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 최소 비용을 계산하기 위해 실제로 적용되는 알고리즘이다. 우선 그래프 이론을 위한 용어를 정리하면 다음과 같다. 노드 = 정점 = 도시: 그래프에서 동그라미에 해당되는 부분이다. 간선 = 거리 = 비용: 그래프에서 선에 해당하는 부분이다. 아래의 그래프를 살펴보았을 때 노드의 개수는 7개이고, 간선의 개수는 11개이다. 이때 단 6개의 간선으로 모든 노드를 연결할 수 있다. 또한 최소 비용 신장 트리를 만들 때 사용되는 간선..

학습 내용 합집합 찾기(Union-Find) Union-Find는 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있으며 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 만약 여러 개의 노드가 서로 자유분방하게 존재한다면 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있는 것과 같다. 이러한 경우 모든 값이 자기 자신을 가리키도록 만들어서 표현할 수 있다. 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 이때 1과 2가 연결되었다면 다음과 같이 2번째 인덱스의 ..

학습 내용 깊이 우선 탐색(Depth First Search) 깊이 우선 탐색(Depth First Search, DFS)은 탐색을 할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 특히 '맹목적인 탐색' 목적으로 사용할 수 있는 기법이다. 너비 우선 탐색에서는 큐(Queue)가 사용되었다면 깊이 우선 탐색에서는 스택(Stack)이 사용된다. 또한 사실 스택을 사용하지 않더라도 구현이 가능하다는 특징이 있다. 이는 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다. DFS는 BFS와 마찬가지로 시작 노드를 스택에 삽입하면서 시작한다. 또한 시작 노드를 방문했다는 표시로 '방문 처리'를 해준다. 아래 예제에서는 검은색으로 표시하였다. 이제 DFS는 다음과 같은 간단한 알고리즘에 따라서..

학습 내용 너비 우선 탐색(Breath First Search) 너비 우선 탐색(Breath First Search, BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 특히 '맹목적인 탐색' 목적으로 사용할 수 있는 기법이다. 너비 우선 탐색은 기본적으로 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용한다. 필요한 것은 큐(Queue)이며 선입선출의 특징을 가지고 있기 때문에 너비 우선 탐색을 가능하게 한다. BFS는 맨 처음 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 또한 시작 노드를 방문했다는 표시로 '방문 처리'를 해주도록 한다. 아래의 예시에서는 진한 검은색으로 표시하였다. 이제 BFS는 다음과 같이 간단한 알고리즘에 따라..