Breadth-First Search (BFS) 너비 우선 탐색 - 그래프 상의 모든 Vertex를 탐색하는 알고리즘 중 하나이다. - 시작 Vertex에 인접한 Vertex를 모두 방문하고, 인접한 Vertex에 인접해 있는 Vertex를 방문해 나아간다. - Tree에서 BFS를 수행하면, Root부터 Tree의 Level 순서대로 Traversal하게 된다. * Graph (그래프) (URL) [Data Structures] Graph | 그래프 Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로, Vertex로 대상이나 개체를 표현하고, Edge로는 이들 간의 관계를 표현한다. Examples of Algorithm using Graph St..
Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로, Vertex로 대상이나 개체를 표현하고, Edge로는 이들 간의 관계를 표현한다. Examples of Algorithm using Graph Structure [Spanning Tree; 신장 트리] * Breadth-First Search (BFS) (너비 우선 탐색) (URL) * Depth-First Search (DFS) (깊이 우선 탐색) (URL) - Strongly Connected Components (강연결 요소) (URL)는 DFS를 활용한 알고리즘이다. [Minimum Spanning Tree; 최소 신장 트리] * Prim's Algorithm (프림 알고리즘) (URL) ..
Longest Common Subsequence Problem (LCS) 최장 공통 부분 순서 문제 - 두 문자열에 존재하는 가장 긴 공통 부분 순서*를 찾아내는 문제이다. - 단순히, 전체 문자열에서 부분 문자열을 찾아내는 문제는 문자열 매칭 알고리즘 (URL)을 참고하자. Example. 공통 부분 순서 (Common Subsequence) - "bcdb"는 문자열 "abcbdab"의 부분 순서이다. ("bcdb"가 문자열 "abcbdab"에 순서대로 나타나기 때문이다.) - 문자열 "abcbdab"와 문자열 "bdcaba"에 대해, 문자열 "bca"는 공통 부분 순서 중 하나이다. (두 문자열에 "bca"가 순서대로 나타나기 때문이다.) - 문자열 "abcbdab"와 문자열 "bdcaba"에 대해,..
Matrix-Chain Multiplication Problem 행렬 곱셈 순서 문제 - \(n\)개의 행렬들에 대해서, 스칼라 곱셈 횟수를 최소로 하는 곱셈 순서를 정의하는 문제이다. - 예를 들어, \(p\times q\) Matrix \(A\)와 \(q\times r\) Matrix \(B\)에 대한 스칼라 곱셈 횟수는 \(p * q * r\)회 이다. - 일반적으로 \(n\)개의 행렬들에 대해서는 \(n-1\)번의 행렬 곱셈이 행해져야 하고, 곱셈의 순서의 경우의 수는 충분히 큰 \(n\)에 대해 \(\Omega(2^n)\)이다. - 예를 들어, 행렬 \(A_1, A_2, A_3, A_4\)의 곱셈 \(A_1A_2A_3A_4\)의 순서는 아래와 같은 경우로 나눌 수 있다. \(((A_1A_2)A_..
Pebble Placement Problem 돌 놓기 문제 - \(3 \; X \; n\) Matrix가 주어졌을 때, (\(n\)은 자연수) 제한조건*을 만족시켜가며 돌을 놓았을 때(= 원소를 선택했을 때), 돌이 놓인 곳에 있는 수의 합이 최대로 되게 하는 경우는 어느 경우인지를 계산해야 하는 문제이다. * 제한조건 1) 가로나 세로로 인접한 두 칸에 동시에 돌을 놓을 수 없다. 2) 각 Column에는 적어도 하나 이상의 돌이 놓여야 한다. Example. Rule Violations and Compliance with Rules Mechanism (원리) ※ 이 문제의 답은 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 ..
Matrix Path Problem 행렬 경로 문제 - \(n \; X \; n\) Matrix가 주어졌을 때, (\(n\)은 자연수) 이 행렬의 왼쪽 위에서 시작해 한 칸씩 이동하며, 행렬의 오른쪽 아래까지 도달하되, 이 과정에서 거쳐가는 행렬의 원소의 합이 가장 큰 경우는 어느 경우인지를 계산해야 하는 문제이다. - 이 때, 이동방향은 오직 오른쪽, 아래쪽만 허용된다. (즉, 왼쪽, 위쪽, 대각선 이동은 허용되지 않는다.) Example. Rule Violations and Compliance with Rules Mechanism (원리) ※ 이 문제의 답은 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 있다. [Algori..
Fibonacci Sequence 피보나치 수열 \(f(n) = f(n-1) + f(n-2)\\ f(1) = f(2) = 1\) - 즉, 피보나치 수는 \(n-1\)의 피보나치 수와 \(n-2\)의 피보나치 수를 포함하고 있는 수 이다. - 즉, 피보나치 수열에서는 다음 항을 구하려면, 이전 항의 값을 알아야 하기 때문에 피보나치 수열은 Optimal Substructure를 가졌다 할 수 있으며, 이는 Dynamic Programming 기법이 적용 가능함을 의미한다. [Algorithms] Dynamic Programming (DP) | 동적 프로그래밍 Dynamic Programming (DP) 동적 프로그래밍 - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알..
Dynamic Programming (DP) 동적 프로그래밍 - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알고리즘을 통칭하는 말이다. - 특히 이러한 "작은 문제의 해답"을 Optimal Substructure(최적 부분 구조)라 부른다. - DP에서는 이러한 Optimal Substructure를 재귀적으로 해결하되, 중복된 연산을 최소화하여 효율적으로 해결하는 것이 관건이다. ※ 즉, 어떤 문제가 Optimal Substructure를 가지고 있되, 이를 단순한 재귀로 해결했을 때 큰 비효율이 발생한다면, 동적 프로그래밍을 적용해 볼 수 있다. * 이렇게 DP에서 중복된 재귀 호출을 피하는 것을 Memoization(메모하기)라 부른다. 이는 Top-Down ..
