다항 시간 내에 해결이 가능한 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?그렇다면 이분 탐색 트리란 무엇일까? 이분 탐색은 이분 트..