컴퓨터과학
선택 알고리즘
n개의 원소로 이루어진 집합에서 최소/최대 원소를 찾기 위해서는 선형시간 O(n)이 필요하다 적어도 모든원소를 한번씩은 봐야하는 것이다. 그렇다면 최소(혹은 최대) 원소가 아닌 2번째로 작은(혹은 큰) 원소를 찾기 위해서는 최소(최대)원소를 구하는 기본 과정에 2번째로 작은 원소를 저장하고 이를 갱신하는 과정을 추가 하면 된다. 위 과정은 최소/최대 원소를 구하는 과정보다 시간이 더 걸리긴 하지만 마찬가지로 선형시간내에 구할 수 있다. 하지만 n개의 원소로 이루어진 집합에서 중앙값을 구한다고 하면 위 과정에서 n/2번째 원소까지를 저장하며 갱신해야 하므로 이런 경우에는 O(n^2)의 시간이 걸리게 된다. 이런 경우에는 위와같은 방법을 사용하기보단 O(nlogn)시간이 소요되는 정렬 알고리즘을 통해 배열을..
상태 공간 트리 (State-Space Tree)
문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리를 상태 공간 트리(State-Space Tree)라고 한다. 이러한 상태 공간 트리를 탐색하는 방식들에 대해서 이야기 하고자 한다. 1. 백트래킹 (Backtracking) 백트래킹은 주어진 상태 공간 트리를 트리의 루트에서 시작해서 DFS 방식으로 탐색을 해 나가는 것이다. 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었다고 한다. 대표적으로 미로 찾기 문제와 색칠 문제가 있다. 미로 찾기 문제 만약 우리가 미로에 갇히게 되면 어떻게 탈출해야할까? 갈 수 있는곳을 일단 가보고, 막다른길이 있다면 왔던길을 되돌아와 가보지 않은 길을 선택하는 행동을 출구가 나올때 까지 반복할 것이다. 미로 -> 상태 ..
동적 프로그래밍 (Dynamic Programming)
동적 프로그래밍은 재귀적으로 구현한 알고리즘에서 중복 호출이 일어나 심각한 비효율이 발생할 때 이를 해결하는 방법이다 예를들어 피보나치 수를 아래와 같이 정의할 때 f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 * n은 자연수 n번째 피보나치 수 f(n)(n>2)은 피보나치 수 f(n-1)와 피보나치 수 f(n-2) 를 포함한다. 이와같이 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있을 때 최적 부분 구조(Optimal Substructure)를 가졌다고 하고, 아래와 같은 재귀호출로 자연스럽게 구현할 수 있다. def fibo(n) if n==1 or n==2: return 1 else: return fibo(n-1) + fibo(n-2) 중복호출로 인한 비효율이 있는..