다이나믹 프로그래밍 (Dynamic Programming) 기본 개념 최적화 문제를 해결하는 알고리즘 기술이다. 전체 문제의 최적 해가 부분 문제의 최적 해를 포함함을 활용한다. 이전에 계산한 값을 저장함으로써 동일 계산의 반복을 제거한다. 재귀적 구조 - 큰 문제 안에 닮음꼴의 작은 문제가 들어있는 구조다. - 관계중심으로 문제를 간명하게 파악 가능하다. 재귀적 해법 - 잘 쓰면 보약, 잘못 쓰면 맹독이다. - 심각한 중복 호출이 일어나는 경우가 있다. > 재귀적 해법이 바람직한 예 - 퀵 정렬, 병합 정렬 등의 정렬 알고리즘 - 계승(factorial) 구하기 - 그래프의 DFS > 재귀적 해법이 치명적인 예 - 피보나치수 구하기 - 행렬곱셈 최적순서 구하기 대표 문제 : 피보나치 수 아주 간단한 문..

이분 탐색 알고리즘 (Binary Search) 이분 탐색(Binary Search)은 정렬된 데이터에 한하여 탐색 범위를 두 범위로 나누어 특정 데이터를 탐색하는 방식입니다. 이분 탐색을 왜 쓰는지에 대해 알려면 먼저 선형 탐색에 대해 이해해야 합니다. 선형 탐색(Linear Search)은 말그대로 정렬 여부에 관계없이 앞부터 혹은 뒤부터 순차적으로 데이터를 탐색하는 방식입니다. 아래와 같은 정수 데이터가 나열되어 있다고 가정해봅시다. 1 2 3 4 5 6 7 8 9 10 이 데이터 배열에서 정수 2를 찾고자 합니다. 선형 탐색을 사용해 1부터 탐색하면 단 3번의 탐색 시도로 데이터를 찾아낼 수 있습니다. 하지만 만약 정수 7을 찾고자 한다면 선형 탐색을 사용하는 것은 너무나 비효율적으로 보입니다. ..

그리디 알고리즘 (Greedy Algorithm) 같은 말로 탐욕 알고리즘으로 불리는 그리디 알고리즘(Greedy Algorithm)은 매 선택마다 지금 당장 최적의 해를 선택해 적합한 결과를 도출하는 알고리즘입니다. 예를 들어 서울에서 전주까지 거쳐가는 도시를 서울-수원-천안-대전-전주 라고 할 때 각각의 도시에서 출발할 때 마다 다음 도시로 갈 수 있는 도로 중 가장 짧은 도로를 선택하여 이동하는 방법입니다. 그리디 알고리즘을 적용하여 매 순간 최적의 해를 구할 수 있지만 그것을 전체 결과로 보았을 때 최적의 결과로 보기는 어렵습니다. 왜냐하면 이 알고리즘 대로 최적의 해를 구하여 (예를 들어) 10 - 10 - 10 - 300 의 경로(총 330)를 지정할 수 있지만 10 - 10 - 30 - 10..

라빈-카프 알고리즘 (Rabin-Karp) 라빈-카프 알고리즘은 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘입니다. 간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 됩니다. 이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 됩니다. 예를 들어 ABCD와 ABED라는 문자열이 있을 때 ABCD의 해시 값은 65 * 3^3 + 66 * 3^2 + 67 * 3^1 + 68 * 3^0 = 2618 ABED의 해시 값은 65 * 3^3 + 66 * 3^2 + 69 * 3^1 + 68 * 3^0 = 2624 이므로 ABCD와 ABED 두 문자열은 서로 일치하지 않는다는 결과가 됩니다. ..

KMP 알고리즘 (Knuth-Morris-Pratt) 일반적으로 어떤 문서나 파일에서 특정 문자열을 찾기 위해 Ctrl + F를 활용해 찾기를 시도합니다. 이러한 행위가 바로 문자열 탐색, 혹은 문자열 검색입니다. 문자열 검색은 다음과 같은 알고리즘에 의해 수행됩니다. A B C D E C D 결과 : 실패 검색을 당하는 문자열은 ABCDE 이며 검색하려는 문자열은 CD 입니다. ABCDE의 앞자리부터 검색할 문자열 CD를 하나씩 대조하며 탐색을 시작합니다. 일치하지 않으므로 한칸 이동합니다 A B C D E C D 결과 : 실패 역시 일치하지 않으므로 한칸 이동합니다. A B C D E C D 결과 : 일치 문자열이 일치하여 검색에 성공합니다. 만약 검색 당한 문자열이 ABCDEABCDE 처럼 길다면 ..

이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다. 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 매칭을 한다는 것은 어떤 정점이 그것이 가리키는 위치의 다른 정점을 점유한 상태를 말하며 각 정점은 한 개씩만 점유 가능하고 여러개의 정점을 점유할 수 없습니다. 간선의 용량이 1인 것은 바로 이러한 이유에서..