다이나믹 프로그래밍 (Dynamic Programming) 직역하면 동적 프로그래밍으로 불리는 이 프로그래밍 방법은 큰 문제를 작은 부분으로 나누어 작은 부분들을 이용해 큰 문제를 해결하는 기법입니다. 이와 대조되는 분할 정복 알고리즘 역시 큰 문제를 한번에 처리하기에 연산 수가 크고 복잡하여 큰 문제를 작은 부분으로 나누는 기법입니다. 방법은 유사하지만 동적 프로그래밍은 작은 부분들을 다시 반복하여 연산하지 않는다는 차이점이 존재합니다. 즉, 큰 문제들을 작은 문제들로 나누는 과정은 동일하지만 분할 정복은 작은 문제들을 다시 연산하고 다이나믹 프로그래밍은 미리 연산된 결괏값을 재사용합니다. 다이나믹 프로그래밍에서 모든 작은 문제들은 반드시 한번만 사용하게 됩니다. 따라서 연산이 끝난 문제들은 어딘가에 ..

크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘은 최소 비용 신장 트리(MST)를 만드는 데 사용되는 알고리즘입니다. 최소 비용 신장 트리란 가장 적은 최소한의 가중치(비용)로 모든 노드를 연결한 트리입니다. 즉, 여러 장소를 최소한의 비용으로 연결하고자 할 때 적용되는 알고리즘입니다. 우선 정점(노드) vertex과 간선 edge의 개념에 대해 알고 가야합니다. 그래프 자료구조에서 자세히 다루었으니 참고하시기 바랍니다. 알고리즘 원리 크루스칼 알고리즘의 동작 원리는 다음과 같습니다. 1. 최소 비용을 기준으로 간선을 오름차순 정렬 2. 사이클 확인 후 집합 생성 (사이클이면 사이클되는 간선을 배제함) 최소 비용 신장 트리의 경우 사이클이 생성되어서는 안됩니다. 사이클 여부는 유니..

합집합 찾기 알고리즘 (Union-Find) 서로소 집합(Disjoint-Set)이라고도 불리는 유니온 파인드는 서로 아무런 연결성도 없는 두 원소를 선택하여 그것들이 서로 같은 집합 내에 연결되어 있는 지 연결성을 확인하는 알고리즘입니다. 알고리즘 원리 위와 같이 6개의 아무런 연결성 없는 원소들이 존재할 때 각각의 원소들은 자기 자신의 집합에 속해있습니다. 원소 1은 집합 1에 속해있으며 원소 4는 집합 4에 속해있는 것입니다. 원소 1과 2를 연결하게 되면 이 둘을 Union 한 것이며 일반적으로 값이 더 작은 쪽으로 집합을 합치게 됩니다. 즉 원소 1과 2는 모두 집합 1에 속하게 되는 것입니다. 위 원리대로 볼 때 원소 2와 3을 연결하게 되면 원소 3은 집합 2에 속해야 할 것입니다. 하지만 ..

DFS 알고리즘 (Depth First Search) 깊이 우선 탐색(DFS)은 BFS와 달리 스택 자료구조를 사용하여 깊이를 우선적으로 탐색하는 알고리즘입니다. 또한 재귀적 함수로도 구현이 가능합니다. 위와 같은 이진 트리에 대하여 깊이 우선 탐색을 해보겠습니다. 깊이 우선 탐색은 기본적으로 노드를 스택에 넣고 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문이 완료되었으면 다시 방문하지 않은 노드를 찾아서 스택에 넣는 방식입니다. 가장 먼저 방문하는 노드 1을 스택에 넣고 방문 완료(visited)합니다. 스택은 큐와 달리 나중에 들어온 것이 먼저 나가는 후입선출 방식입니다. 인접해있던 노드 2를 스택에 넣고 방문 완료합니다. 위 과정을 통해 노드 7까지 스택에 삽입되었다면 노드 7, 6, 3은..

BFS 알고리즘 (Breath First Search) 너비 우선 탐색 (BFS)은 큐 자료구조를 사용하여 너비를 우선적으로 탐색하는 탐색 알고리즘입니다. 흔히 최단 경로를 파악하여 최단 길이를 찾아낼 때 활용합니다. 순회의 순서로만 보면 이진 트리의 레벨 순회와 유사한 방식입니다. 위와 같은 이진 트리에 대하여 너비 우선 탐색을 해보겠습니다. 너비 우선 탐색은 기본적으로 '노드를 큐에넣고 -> 꺼내서 출력하고 -> 인접한 노드를 큐에넣고' 를 반복하는 알고리즘입니다. 가장 먼저 방문하는 노드1을 큐에 넣고 방문 완료(visited)합니다. 큐에 들어있던 1을 꺼내서 출력하고 인접해있던 노드 2와 3을 큐에 넣고 방문 완료합니다. 큐에서 먼저들어온 2를 꺼내서 출력하고 인접해있던 노드 4와 5를 큐에 넣..

계수 정렬 알고리즘 (Counting Sort) 계수 정렬은 반드시 어떠한 범위안에 존재하는 데이터들로 이루어진 데이터 배열에 한하여 데이터의 크기를 기준으로 카운트하여 정렬하는 알고리즘입니다. 쉽게 말해 기준이 크기 5이하인 데이터 배열로 정수 1, 4, 4, 2, 3 가 들어있다면 크기가 1인 것은 1개, 크기가 2인 것은 1개, 크기가 3인 것은 1개, 크기가 4인 것은 2개로 카운트하여 크기가 작은 순, 혹은 큰 순으로 정렬합니다. 1 4 5 2 2 4 1 3 5 3 위와 같은 수가 있을 때 수들을 오름차순으로 계수 정렬을 해보겠습니다. 1 4 5 2 2 4 1 3 5 3 크기1 | 1 크기2 | 0 크기3 | 0 크기4 | 0 크기5 | 0 1 4 5 2 2 4 1 3 5 3 크기1 | 1 크기..