DFS(Depth-First Search) 깊이 우선 탐색으로 불리며 BFS와 같은 그래프 탐색 알고리즘이다.목표는 주어진 방향그래프 G에서 G의 모든 정점을 탐색하고 여러 소스 정점(Source vertics)으로 구성된 포레스트(DFS Forest)를 생성한다.또한 실행후 d[v](탐색 시작 시간),f[v](탐색 종료 시간)의 두 가지 시간 배열을 출력한다.DFS Example위의 그래프에서는 a -> b -> c -> b -> f -> g -> f -> a ->d -> e -> d가 방문순서가된다.DFS를 구현하는 방법은 대표적으로 재귀 호출(Reculsive)를 이용하거나 Stack을 사용하는 법이 있다.수도코드는 다음과 같다.DFS_recursive(graph, vertex, visited): ..

Breadth-First Search BFS는 주로 무방향 그래프에서 사용되는 그래프 탐색 알고리즘으로 넓이 우선 탐색 이라고 불린다.그래프를 순회하거나 최단경로(Shortest Path)를 구할때도 사용한다.구현할때는 Queue를 사용한다.Shortest Path Problem 최단 경로를 구하는 문제이다.  예를 들어 위의 그래프에서 s에서 b까지 가는 가장 최단거리는 이다.우선 주어진 그래프 G = (V,E)에서 BFS 알고리즘의 리턴값은 d[v](s to v 까지의 거리),pred[v](전에 지나온 노드)이다.pred[v]는 최단거리를 위해 실제로 지나온 노드를 기록하기에 경로를 찾을 수 있다.따라서 BFS가 그래프 탐색을 완료하면  이를 바탕으로 최단 경로 트리(Shortest path tree..

0-1 Knapsack problem 배낭문제라고 불리며 DP로 해결할 수 있는 대표적인 문제이다.DP에 대해 상기해보자면 DP 접근법은 시간은 단축시키고 공간을 늘리는 Space-time trade off 관계이다.배낭문제는 주어진 제한 조건 내에서 특정 아이템의 가치 합을 최대화하는 방법을 찾는 문제이다.파일 i에 사이즈가 w고 소요시간이 v일때 제한 W를 만족시키는 최대의 합을 찾아내는 것이라고 하고 상황이 다음과 같은 예시라고 하자.이때 0-1 Knapsack문제에서는 각 파일을 더 작게 분할할 수 없다. W = 시간은 10이 최대값이라 할때.위의 경우 i가 2,4인경우가 답이다.이는 케이스가 적어서 직관적으로 바로 풀 수 있는 쉬운 예였지만 이 i가 매우 커지면 DP를 통해 해결해야한다.그전에 ..

Dynamic Programming  한국어로는 동적계획법이라 하며 Divide & Conquer와 같은 패러다임의 일종이다.예를 들어보면 다음과 같다.이 계단을 다 오르기 전 단계는 무조건 3가지 경우중 하나가 된다.얼핏보면 다음과 같이 재귀트리를 표현할 수 있다.얼핏보면 Divide & Conquer과 비슷하다.실제로 접근법 자체는 크게 다르지 않다.이후 더 깊이 재귀 절차를 보면 다음과 같다. 여기서 DP의 핵심은 반복되는 요소들이다.ways(n-2)는 2번 반복되는데 둘다 동일한 값이고 나머지 요소도 그렇다.즉,DP의 핵심은 이러한 반복되는 요소들을 저장해놓고 다시 계산하지 않고 불러서 사용하는 것 이다.중복되는 값을 저장하고 사용함으로써 선형 시간 복잡도를 갖는다.만일 저 문제를 DP로 해결하지..

분할 정복 알고리즘을 사용한 정렬 알고리즘이다.굉장히 유명한 알고리즘으로 현재 많은 기본 언어에서의 Sort()함수는 Quick sort를 사용한다.퀵 정렬은 "in place"정렬이다.이는 삽입정렬과 동일하며 병합정렬와는 다르다.in place는 정렬하는데 있어서 추가적인 배열을 할당하지 않는다.반면 병합정렬은 combine하는데 있어서 배열을 추가적으로 할당해야한다.따라서 속도의 차이가 존재한다.이제 알고리즘을 소개하자면 다음과 같다.Divide:배열 a를 두 개의 부분 배열로 분할하는데 이는 피봇(Pivot)이라는 기준원소를 기준으로 피봇보다 작은 원소를 모아두는 배열과 큰 원소를 모아두는 배열로 나눈다.Conquer:퀵 정렬을 재귀 호출해서 두 부분의 배열을 정렬한다.Combine:부분 배열은 이..

분할 정복으로 불리는 알고리즘으로 디자인 패러다임은 다음과 같다.문제를 여러개의 소문제로 분할한다.재귀적으로 소문제를 정복한다.소문제의 해결책을 합처서 문제를 해결한다.이미 병합 정렬과 마스터 정리를 통해 많이 접해왔다.분할 정복 알고리즘의 대표적인 예시는 다음과 같다.Merge sortBinary searchPowering a numberFibonacci numbersMatrix multiplicationStrassen's algorithmVLSI tree layout병합 정렬은 이미 알고 있기에 마스터 정리로 구한 성능만 알고 넘어가자. Binary Search(이진 탐색) 이진 탐색은 이미 정렬된 배열에서 원소를 찾는 알고리즘으로 이를 Divide conquer로 생각하면 다음과 같다.Divide:..