기록공간

LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임의의 수열이 주어졌을때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장증가수열이라고 한다. 예를 들어 다음 수열이 주어졌다고 하자. 3 5 7 9 2 1 4 8 위 수열에서 몇 개의 수를 제거해 부분 수열을 만들었다고 하자. 3 7 9 1 4 8 (5, 2 제거) 7 9 1 8 (3, 5, 2, 4 제거) 3 5 7 8 (9, 2, 1, 4 제거) 1 4 8 (3, 5, 7, 9, 2 제거) 이들 중 세번째와 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다. 그리고 세번째와 같이 이러한 수열 중 가장 긴..

동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진 것이다(...). 분할정복(Divide and Conquer)과 다른 점 거의 비슷하지만 결정적인 차이점이 존재한다. 그것은 바로 나눠진 작은 문제에서 중복이 일어나는가 안일어나는가이다. 분할정복은 큰 문제를 해결하기 위해 그냥 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 동적계획법은 작은 문제들이 반복되는것(단, 바뀌지 않음)을 이용해 풀어나가는 방법이다. 동적계획법의 방법 모든 작은 문제들은 꼭 한번만 풀어야 한다. 그러므로 작은 문제의 정답은 어딘가..

너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 않은 정점을 찾아 순차적으로 방문해 나아간다. 더이상 방문할 수 없을때 까지 반복하며, 인접한 간선을 우선적으로 검사하기 위하여 Queue를 사용한다. 어떻게 진행되는지를 그림을 통해 살펴보자. 1을 방문하면서 인접한 정점인 2, 3, 그리고 7을 큐에 넣어준다. 그리고 큐에 들어간 순서대로 방문하면서 큐가 빌때까지 반복 수행해준다. 이 작업을 모든 정점이 방문되었을때까지 반복해주면 된다. 구현 위 그래프 정보를 바탕으로 깊이 탐색을 구현해보자. #include #include #includ..

깊이 우선 탐색 (Depth First Search : DFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것이다. 이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없는 경우 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색한다. 그림을 통해 한번 살펴보자. 위 그림의 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정하자. 우선, 정점 1에서 깊이 우선 탐색을 한다고 하자. 먼저, 정점 1에서 연결된 간선들을 통해 연결된 정점을 확인하면 2, 3..

그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간의 최적이라고 생각되는 것을 선택해 나가는 알고리즘이다. 하지만 그리디 알고리즘을 적용할 수 있는 예는 많지 않다. 코딩이 쉽고, 구현이 쉬운건 사실이지만, 그리디 알고리즘으로 구한게 항상 최적을 보장하는 경우는 거의 없기 때문이다. 만약에 사탕을 당장 받으면 1개만 받지만, 1분을 기다리면 2개를 받을 수 있다고 하자. 이런 경우 그리디 알고리즘을 사용하면 사탕을 1개 받는 것을 선택한다. 그래서 보통 '근사치 추정'을 위해 그리디 알고리즘을 사용한다. 적용 가능한 예 Prim Algorithm, Kruskal ..