본문 바로가기

알고리즘(Algorithm)

 (19)
[알고리즘] 이진 탐색(Binary Search) 우선 탐색은 여러 정보들 중에서 특정한 값을 찾는 것이다. 사전을 예로 들어, 사전에서 특정한 단어를 찾는 방법은 대표적으로 2가지가 있다. Orange라는 단어를 찾는다고 해보자. 첫 번째 방법은 처음부터 Orange가 나올 때까지 찾아보는 것이다. 이 방법도 생각할 수 있다. 사전의 중간(Kiwi)을 펼쳐놓고 Orange의 위치는 이보다 뒤이므로 나머지 뒷부분에서 중간을 펼치고... 를 반복해 Orange를 찾는 방법이다. 첫번째 방법이 선형 탐색(순차 검색), 두번째 방법이 이진 탐색(이분 탐색)이라고 볼 수 있다. 선형 탐색(Linear Search) 처음부터 찾고자 하는 값이 나올 때까지 탐색하는 기법이다. 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이 있고 8을 찾는다고 하면, 선..
[알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬(ex, 2 by 4 행렬 x 4 by 7 행렬 x 7 by 9 행렬 x ...)의 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬 곱셈은 결합 법칙이 성립하기 때문에 곱하는 순서에 상관은 없지만, 순서에 따라 연산의 양이 달라진다. 2 x 3 행렬 A와 3 x 5 행렬 B, 5 x 7 행렬 C가 있다고 하자. 이 행렬들의 곱 ABC를 구하는 경우는 아래와 같다. 1. AB를 먼저 곱하고 C를 곱할 때의 연산 수 = 2 x 3 x 5 + 2 x 5 x 7 = 100 2. BC를 먼저 곱하고 A를 곱할 때의 연산 수 = 3 x 5 x 7 + 2 x 3 x 7 = 147 둘은 같은 곱셈이지만..
[알고리즘] 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm) 눈앞의 이익만 좇는 선택을 반복하는 알고리즘이다. 그리디 알고리즘은 당장의 경우에는 최적의 경우일지라도, 결과는 대부분 최적이 아니다. 그렇지만 드물게 최적의 답을 보장해주는 경우가 있다. 해가 만들어 질 때 까지 가장 좋아 보이는 선택을 하는 것을 반복한다. 그리디 알고리즘은 이미 앞에서 사용되었다. 바로, 최소 신장 트리를 구할 때 사용한 프림 알고리즘과 크루스칼 알고리즘이다. 또한, 프림 알고리즘과 크루스칼 알고리즘은 최적해가 보장되는 예들 중 하나이기도 하다. 그러나 이 둘이 특별한 경우이고 대부분의 경우에는 최적의 해를 보장하지 못한다. 아래와 같은 예시를 보자. 1. 이진 트리의 그리디 탐색 이진 트리에서 리프 노드를 만날 때 까지 방문한 노드..
[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 다음과 같은 도시들과 그 도시들끼리 이어주는 도로망이 있다고 해보자. A 도시에서 F 도시를 방문한다고 하자. 최단 거리를 찾아서 방문한다면 시간이 절약될 것이다. 그러므로, C 도시를 거쳐서 F 도시로 가는 것이 가장 짧은 경로이다. 이때의 거리는 도로의 길이의 합이 가장 짧은 60km가 된다. 가중치 그래프에서도 마찬가지이다. 한 정점 v에서 각 정점들까지의 최단 경로를 구하고자하는 경우가 있다. v에서 각 정점까지의 가중치들을 더하고, 그 가중치가 가장 작으면 최단 거리가 된다. 이렇게 한 시작 정점 v에서 모든 다른 정점들 까지의 최단 경로를 구하는 알고리즘이 다익스트라 알고리즘(Dijkstra Algorithm)이다. 단, 모든 가중치가 음수가 아닐 경우에 사용이 가능하다. ..
[알고리즘] NP-완비(NP-Complete) 세상의 문제 모든 문제들은 "해결할 수 있는 문제인가?" 와 "해결할 수 없는 문제인가?"라는 두 가지의 집합으로 나눌 수 있다. 해결할 수 없는 문제의 대표적인 경우가 앨런 튜닝이 증명한 정지 문제가 되겠다. 해결할 수 없는 문제는 다시 "현실적인 시간 안에 풀 수 있는 문제" 와 "현실적인 시간 안에 풀 수 없는 문제"로 나눌 수 있다. 지금까지 공부한 알고리즘들은 모두 다항식 시간이 걸리는 문제들이었다. 예를 들어, \(O(n^2)\)의 시간이 필요한 선택 정렬, \(O(nlogn)\)의 시간이 필요한 병합 정렬, \(O(n^3)\)의 플로이드-워셜 알고리즘, ... 등이 있었다. \(O(nlogn)\)은 다항식은 아니지만, \(O(n^2)\)에 속하기 때문에 다항식 시간에 속한다고 볼 수 있다. ..
[알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming) 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조(Optimal Substructure)라고 한다. 이 최적 부분 구조가 지켜진 상태에서 문제에 대한 해답을 찾는 과정이 바로 동적 계획법이다. 동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 예시로 피보나치 수를 보자. 피보나치 수는 다음과 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 이를 점화식으로 나타내면 다음과 같다. $$\begin{align} f(1) & = f(2) = 1 \\ f(n) & = f(n-1) + f(n-2) \end{align}$$ \(n\)의 피보나치 수는 더 작은 크기인 \(n-1\)의 피보나치 수와..
[알고리즘] 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)란 그래프의 모든 정점을 포함하는 트리를 말한다. n개의 정점이 있다면 n-1개의 간선이 존재해야 한다. 이는 트리의 일종이기에 모든 정점들은 최소 하나의 간선에는 연결되어 있어야 하고, 사이클이 없어야 하기 때문이다. DFS와 BFS를 통해 얻어낸 트리도 신장 트리의 한 예가 된다. 최소 신장 트리(Minimum Spanning Tree)는 가중치 그래프에서 가중치의 합이 가장 작은 트리를 뜻한다. 이러한 최소 신장 트리를 찾는 알고리즘의 종류에는 프림 알고리즘(Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm)이 있다. 프림 알고리즘(Prim Algorithm) 프림 알고리즘은 ..
[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS) 그래프에서 탐색은 하나의 정점에서 시작해 모든 정점들을 한 번씩 방문하는 작업이다. 이에 대한 방법들이 바로 너비 우선 탐색과 깊이 우선 탐색이다. 자료구조에 대한 그래프는 여기로 [자료구조] 그래프 [자료구조] 그래프 그래프 그래프는 요소들이 서로 연결되어 있는 관계를 표현한 자료구조이다. 그래프는 정점(vertex)와 그들을 연결하는 간선(edge)의 집합으로 구성된다. 수학적으로는 다음과 같이 표시한다. (\G = ggjjdiary.tistory.com 너비 우선 탐색(Breadth First Search) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법이다. 너비 우선 탐색은 큐를 이용한다. 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고, 더 이상 ..

티스토리툴바