Algorithm

앞으로 알고리즘 시리즈에 올라오는 모든 내용은 Sanjoy Dasgupta, Christos Papadiimitriou, Umesh Vazirani 저자의 Algorithms과 POSTECH의 안희갑 교수님의 강의를 기반으로 하며, 추가로 공부한 내용을 개인적으로 정리하고자 글을 작성할 것이다. 이 외에도 여러 알고리즘과 관련된 문제들을 풀거나 아이디어가 ...

Convex Hulls의 정의 Convex Hulls이란 무엇인가? 조금 어렵게 이야기 하면, 2차원의 유클리드 좌표에서 어떠한 점들의 집합이 만든 다각형이 다른 모든 점들을 포함하는 점들의 집합을 이야기 한다. 조금 쉽게 말함면 여러 개의 점이 주어졌을 때, 이 모든 점들을 포함하는 최소 크기의 볼록 다각형을 Convex Hulls이라 한다. 이 Con...

Big-O 표기법 사용 이유 수행 시간을 분석하는 것이 정말 중요함을 계속해서 강조하고 있다. 분석을 잘못하였을 경우 큰 오류가 생길 수 있지만, 반대로 너무 자세하게 분석을하는 것도 문제가 될 수 있다. 그래서 정확한 정보를 알려주는 분석을 위해서 적절하게 단순화하는 작업이 필요하다. 수행 시간을 컴퓨터 기본 연산들로 표현하는 것 자체가 이미 단순화한 것...

분할정복법 분할 정복법(Divide-and-Conquer)을 알아보기 위해서 가장 먼저 어떠한 알고리즘을 수행하여 문제를 해결하지는 살펴볼 것이다. 주어진 문제를 같은 유형의 더 작은 인스턴스(instance)들인 부분 문제(subproblem)들로 분할한다. 이 부분 문제들을 재귀적으로 풀어간다. 이들의 해답을 적절히 결합해간다. 위와 같은 구조는 ...

순환 관계(Recurrence Relations) 분할정복법 알고리즘은 보통 특정 패턴을 따르는데, 크기가 n인 문제가 있다고 했을 때 부분 문제들이 a개씩 분할이 되고, 각 문제들이 b의 크기로 나누어지며, 추가적으로 n의 d제곱만큼의 수행 시간이 요구되어지면, 이들의 수행 시간은 다음과 같은 수식으로 얻을 수가 있게 된다. 그리고 이 수식은 Maste...

합병 정렬(Merge Sort) 숫자들의 리스트를 정렬하는 문제는 그 자신을 즉시 분할정복법(Divide and Conquer)에 따를 수 있다. 합병 정렬(Merge sort)은 '존 폰 노이만(John vodn Neumann)'이라는 사람이 제안한 방법으로, 하나의 리스트를 2개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음 2개의 정렬된...

행렬 곱셈(Matrix Multiplication) 두 n * n 행렬인 X와 Y의 곱셈 Z의 (i, j)번째 값은 다음과 같다. 이를 행렬 표현으로 시각적으로 표현하면, Z의 (i, j)번째 값은 X의 i번째 행(row)와 Y의 j번째 열(column)의 내적(dot product)이다. 행과 열이 모두 n이고 내적하는 단계에서 선형적 시간이 필요하기...

중앙값 찾기(Find Median) 숫자들의 중앙값(Median)은 리스트가 존재할 때 정중앙에 있는 값으로, 이 값을 기준으로 절반은 이 값보다 작고, 나머지 절반은 이 값보다 크다. 간단하게 예를 들어 리스트 [45, 1, 10, 30, 25]가 있을 때, 중앙값은 25가 된다. 왜냐하면 이 숫자들을 크기 순서대로 배치하게 되면 [1, 10, 25, 3...

최근접 점의 쌍 찾기(Find Closest Pair of Points) 우리는 n개의 점들이 평면에 주어졌을 때, 유클리드 거리(Euclidian distance)가 가장 적은 점의 쌍을 찾고 싶다. 어떻게 하면 될까? 1. Brute force - 총 n개의 점에서 나머지 n - 1개의 점들을 대상으로 하나씩 비교해가면 된다. 2. Divide and...

왜 그래프를 사용하는가? 문제마다 유형이 다를 것이고, 많은 영역의 문제들은 그래프(Graph)의 간결한 장점을 사용해서 분명하고 정확하게 표현될 수 있다. 예를 들어 그래프 색칠하기(Graph coloring)는 여러 곳에 활용이 될 수 있다. 지도를 표현할 때 이웃한 나라 혹은 지형에 따라 다른 색을 활용해야 하고, 학교에서 시험 시간표를 만들 때 겹치...

무방향 그래프(Undirected Graph) 무방향 그래프(Undirected Graph)는 보통 G = (V, E)로 표현된다. 여기서 V는 정점(Node)을 이야기하고, E는 정점들을 연결하는 간선(EdgE)를 말한다. 무방향 그래프의 특징은 이 간선들이 방향이 없다는 것이다. 즉, 정점들 사이에 정해진 방향은 없는 셈이다. 예를 들어, 위와 같이 ...

경로(Path) 그래프에서 경로(Path)란 서로 연결되어 있는 간선 혹은 정점들을 순서대로 나열한 것을 말한다. 일반적으로 그래프의 경로는 단순(Simple) 경로를 말하는데, 여기서 단순하다는 것은 정점을 단 한번만 지나가는 경로를 말한다. 아래 그림에서 예를 들면, "1245"가 하나의 단순 경로가 될 수 있다. 일반적으로 알고리즘 문제를 해결하는 ...

Shortest Paths in Graphs 그래프의 node는 무수히 많이 존재할 수 있고, 이에따라 이를 연결하는 edge들도 많이 존재할 수 있다. 이때, 우리는 특정한 node 2개를 골라 이들 사이의 최단 거리를 구하고 싶은 경우가 존재할텐데, 이때의 최단 거리를 distance라고 한다. 다음의 그래프를 예를 들 것이고 S와 C 사이의 dista...

Directed Acyclic Graph Directed acyclic graph(DAG)는 이름에서부터 우선 방향성이 있어야하며, acyclic 해야한다. 여기서 cyclic이라는 것은 그래프 상에 cycle이 존재하지 않는다는 이야기이다. 즉, 어느 한 지점에서 출발하였을 경우에 다시 그 지점으로 돌아올 수 없다. Topological Ordering...

Disjoint Set Disjoint Set이란 서로 중복되지 않는 부분들로 나눠진 원소들에 대한 정보를 저장하고 사용할 수 있는 자료 구조이다. 즉, 두 집합이 서로 서로소인 셈이다. 이러한 자료 구조는 집합의 일종이기 때문에 array나 linked list와 같은 자료 구조를 사용할 수도 있는데, 가장 효율적인 tree를 사용할 것이다. 그리고 이러...

이번에는 greedy algorithm의 대표적인 예시중 selecting break points에 대해서 알아보고자 한다. 먼저 알고리즘을 생각하기 이전에 상황에 대해서 설명부터 하겠다. 이 문제는 일종의 scheduling 문제로 greedy algorithm의 대표적인 문제이다. 당신은 차를 타고 여행을 떠나는 사람이다. 대한민국에서 서울과 포항을 ...

Interver scheduling은 어떠한 일 j가 sj에서 시작해서 fj에서 끝난다고 했을 때, 다른 일들과의 수행 시간이 겹치지 않으면서 주어진 일들을 최대한 많이 할 수 있는 조합을 찾는 스케줄링 문제이다. 그렇기 때문에 두가지 일이 있다고 했을 때, 이 두가지 일은 절대 겹쳐서는 안되며 최대한 많은 일을 수행해야만 한다. 우리는 여기서 greedy...

Interval partitioning은 n개의 강의에 대해서 같은 강의실에서 동시에 진행되지 않는 2개의 수업에 대해서 모든 수업을 시간과 강의실이 겹치지 않도록 최소한의 강의실을 배정하는 것을 목표로 한다. 수업 j에 대해서 시작은 sj에 하고 끝은 fj에 한다. 여기서 중요한 부분은 필요한 강의실의 수는 최소한 특정 시간에 강의의 개수보다 많거나 같아...

Dynamic Programming Dynamic Programming(DP)는 일종의 점화식을 세울 수 있는 문제들을 풀 때 유용한 알고리즘이다. 우리가 풀고자 하는 문제를 하위 문제들로 나누어 작은 문제들을 푼 다음에 이를 이용하여 점점 상위 문제들을 풀어나가는 것이다. 점점 풀어나가면서 이전의 답이 이후의 문제의 힌트가 되어 직접적으로 도움이 되기에 ...

이번에는 edit distance라고 해서 편집거리 알고리즘에 대해서 알아보려고 한다. 이는 두 문자열이 주어졌을 때, 두 문자열의 상호간의 유사도를 판단하는 알고리즘이다. 여기서 유사도를 판단한다는 것은 두 문자열이 같아지기 위해서 몇번의 추가(add), 편집(edit), 삭제(delete)가 이루어지는지 그 최소한의 횟수를 구하는 것이다. 다음의 예시를...

Dynamic programming에서 knapsack, 배낭 알고리즘은 대표적인 예시 중에 하나이다. 상황은 다음과 같다. 우리는 가방을 하나 가지고 있다. 이 가방은 W = 10으로 모든 아이템의 무게가 10을 넘길 수 없다. 이러한 상황에서 최적의 조합을 어떻게 만들 수 있을까? 이때 최적의 조합이라는 것은 무게의 한도를 지키면서 값을 최대한 큰 것...

Traveling salesman problem(TSP)은 외판원 순회라 해서 도시가 n개 존재할 때, 특정 도시에서 다른 도시로 이동할 때 드는 distance value(d)가 주어지게 되고, 어떠한 도시에서부터 나머지 다른 모든 도시들을 돌고 다시 출발한 도시로 돌아왔을 때 드는 최소한의 d값을 구하는 문제이다. 이 문제는 모든 도시를 단 한번씩만 방...

Weighted interval scheduling은 n개의 일이 주어지고 각각의 일을 j라고 할 때, sj에서 시작해서 fj에 끝나며 v_j의 weight를 가지고 있다. 여기서 모든 weight가 1인 경우에는 interval scheduling 문제로 greedy algorithm으로 해결하면 된다. 하지만 weight가 존재하는 경우에는 dynami...