Computer Science and Engineering/Data Structures and Algorithms

다항 시간 내에 해결이 가능한 polynomial-time algorithm이 있다면 당연히 그렇지 못한 문제들도 있지 않겠는가? 오늘은 컴퓨터공학 전공자라면 반드시 알아야 할 NP problem에 대해 알아보자. NP-completeness 우리가 이때까지 배웠던 거의 대부분의 알고리즘은 다항시간 내에 해결이 가능하다. input size가 n이라면 이 알고리즘의 시간 복잡도는 어떤 상수 k에 대해 $O(n^{k})$라는 소리. 그렇다면 모든 문제들이 다항 시간 내에 해결이 가능한가? 정답은 No (라고 대부분의 사람들이 믿는다.) 대표적인 예로는 튜링의 Halting Problem인데 이는 어떤 컴퓨터로도, 얼마나 오랜 시간을 들이더라도 해결할 수 없다. Turing's halting problem ..

Greedy algorithms 최적화 문제에서 DP의 방식은 간혹 너무 많은 자원을 낭비하거나 비효율적일 수도 있다. DP는 항상 최적의 경우를 찾아주지만, 꼭 그러한 방식을 따르지 않아도 최적의 경우를 찾는 경우는 상당히 많다. 바로 sub-problem의 문제에 대한 해답이 전체 문제에 대한 해답으로 이어지는 경우인데, 이렇듯 지역적으로 최적화된 선택이 전역적으로도 최선의 선택을 만드는 경우, 또 그 선택들이 항상 순간마다 Best 해 보이는 것을 고르는 경우라면 우리는 이것을 그리디 알고리즘이라고 명명한다. 그리디 알고리즘에는 대표적으로 Minimum-spanning tree와 Dijkstra 알고리즘이 있으며, 이는 앞으로 차차 다룰 예정이다. 이에 앞서 그리디 알고리즘의 대표 문제로 거론되는 ..

Subproblem graphs DP에서 우리는 sub-problem이 어떻게 구성되어 있는지, 그리고 서로 어떤 연관을 지니고 있는지를 이해하는 것이 중요하다.위 그래프 중 오른쪽은 앞선 dynamic programming 1 포스팅에서 살펴봤었던 그래프이다. 해당 그래프는 4라는 문제를 해결하기 위해 어떤 sub-problem이 필요하고, 또 이들은 또 다른 sub-problem을 지니고 있음을 가시적으로 보여준다. 왼쪽 그래프는 오른쪽을 단순화한 버전이다. 우리는 subproblem graphs를 통해 어떤 문제를 해결할 때 필요한 sub-problem이 뭔지를 한눈에 알 수 있다. 궁극적으로는 이 그래프를 통해 시간 복잡도를 결정할 수 있는데, 실행 시간은 각각의 sub-problem을 해결하기 ..

익히 들어봤을 다이내믹  프로그래밍에 대해 정리해보려 한다. Dynamic programming 먼저 dynamic programming (이하 DP)이란 sub-problem의 solution들을 결합하여 문제를 해결하는 방식이다. 이는 앞서 배웠던 분할 정복 (Divide and conquer) 알고리즘과 비슷해 보이지만, 분명한 차이점이 존재한다. 분할 정복 알고리즘도 마찬가지로 문제를 서브 문제들로 나누고 해결한 다음에 합치는 것이지만 각각의 서브 문제들이 중복되지 않는다는 점이 다르다. DP는 각각의 서브 문제들을 단 한 번만 풀고, 이를 테이블에 저장해 둔 후에 필요할 때마다 꺼내서 사용한다. 이는 같은 문제를 다시 계산하는 문제를 해결할 수 있다는 장점이 있다. DP는 전형적으로 최적화 문제..

Binary search tree Search Tree 데이터 구조는 다음과 같은 operations를 제공한다. - Search : 탐색 - Minimum : 최솟값 - Maximum : 최댓값 - Predecessor : 다음에 오는 요소 - Successor : 이전 요소 - Insert : 삽입 - Delete : 삭제 이와 같은 operations들은 트리의 깊이에 실행 시간이 비례한다. 완벽한 binary tree를 이룰 때에는 $\Theta(\lg(n))$ 의 시간 복잡도를, 만약 한쪽으로 치우쳐져 linear chain에 가깝다면 $\Theta(n)$의 시간 복잡도를 가지게 된다. What is a binary search tree?그렇다면 이분 탐색 트리란 무엇일까? 이분 탐색은 이분 트..

앞서 분할 정복 알고리즘의 예시 중에는 퀵 정렬도 있었는데, 이번 시간에는 퀵 정렬에 대해 알아보려고 한다. 우리는 계속해서 더 나은 Complexity를 가진 알고리즘을 알아보고 있기 때문에 퀵 정렬의 장·단점 또한 알아두는 것이 중요할 것이다. pros and cons 앞으로 다룰 정렬에는 더 나은 복잡도가 있을지도 모르겠다 (아직 공부 중이므로 알 수 없다). 하지만 퀵 정렬의 경우 앞서 살펴본 병합, 힙 정렬처럼 일반적으로 $\Theta(n·\log{n})$의 시간 복잡도를 가지며, 추가적인 메모리 공간이 필요하지 않은 in-place 알고리즘에 속한다. 그러나 다른 알고리즘과 다른 특이한 점은 퀵 정렬의 경우 최악의 상황에서는 $\Theta(n^{2})$의 시간을 가진다는 것이다. divide ..

우리는 보통 알고리즘을 공부할 때 가장 많이 다루는 게 바로 정렬 알고리즘이다. 왜 이렇게 중요하게 여겨질까? 그 이유는 프로그램 자체에서 정렬된 정보를 원하는 경우가 많고, 대부분의 알고리즘의 기초를 다질 수 (basic building block)가 있으며, 알고리즘에서 sorting 이 key subroutine으로 종종 사용되기 때문이다. insertion, merge sort 우리는 지금까지 analysis, divide and conquer 등 알고리즘에 대해 공부해 나가면서 항상 정렬 알고리즘을 다뤄왔다. 지금까지 다룬 알고리즘 중 insertion sort, merge sort는 각각의 장단점이 존재한다. 먼저 insertion sort는 $O(n^{2})$의 다소 느린 계산 속도를 가지고..

이번에는 분할 정복으로 해결할 수 있는 Maximum Subarray 문제를 알아보자. Goal 주식 시장에서 가장 큰 수익을 얻기 위해서는 낮은 가격에 사서 높은 가격에 사는 것이 중요하다. 다음 그래프를 보자. 어떤 상품의 가격을 날짜별로 나타내고 있고 Change는 그날 기준으로 전날과의 차이를 의미한다. 어떻게 이 문제를 해결할 수 있을까? 단순히 생각해 보면 주어진 표에서 가장 높은 가격과 가장 낮은 가격을 찾으면 된다. 하지만 여기에는 반례가 존재한다. 가장 높은 가격이 가장 낮은 가격보다 전에 해당하는 경우이다. 따라서 이 방법으로 모든 문제를 해결할 수 없다. Solution #1, Brute-force solution 주어진 n개의 인스턴스 중에 2개를 고르는 모든 경우의 수를 따지는 방..

Divide and conquer 대표적인 알고리즘의 갈래 중 하나인 분할 정복은, 하나의 커다란 문제를 여러 작은 문제로 나눈 후 (Divide), 작은 문제를 해결하고 나서 다시 합쳐 (Combine) 해결하는 (Conquer) 방법이다. Insertion sort 분할 정복이 주는 이점이 무엇일까? 그걸 알아보기 전에 앞서 배웠던 삽입 정렬 (Insertion sort)을 생각해보자. 삽입 정렬은 incremental approach로, 모든 요소를 순차적으로 방문하는 방식을 택한다. 그러다 보니 input instance의 (이미) 정렬된 정도에 따라 최소 Ω(n)에서 최대 O(n2)의 시간 복잡도를 지니게 된다. 그렇다면 mergesort의 시간 복잡도는 어떨까? 결론부터 말하자면 O(n lg ..

Analyzing an algorithm 알고리즘을 분석한다면 다양한 요소들을 고려해야 할 것이다. Memory, communication bandwidth, or computer hardware 등 알고리즘이 요구하는 자원을 예측하는 것도 중요하지만, 대부분의 경우 Computational time이 제일 중요하게 여겨진다. 우리는 다양한 알고리즘 중에서 가장 효율적인 알고리즘을 찾아낼 수 있고, 상대적으로 빈약한 알고리즘을 걸러낼 줄 알아야 한다. Complexity 어떤 알고리즘이 효율적인 알고리즘인지 알기 위해서 중요한 것은 바로 복잡도이다. 주어진 수 집합을 정렬하는 문제 해결의 경우를 생각해 보면, 같은 크기의 수 집합이라고 하더라도 그 구성에 따라 알고리즘의 수행 시간이 다를 것이다. 우리는..