이분 탐색 알고리즘 (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인 것은 바로 이러한 이유에서..

네트워크 플로우 (Network Flow) - 에드몬드 카프 알고리즘 (Edmonds-Karp) 네트워크 플로우(Network Flow)는 한 정점에서 다른 정점까지 흐를 수 있는 데이터의 최대 크기가 어느 정도인지를 확인하는 알고리즘입니다. 유향 그래프에서 각 간선은 데이터가 흐를 수 있는 정해진 용량으로 제한되어 있으며 이를 최대한의 양으로 얼마나 흐르게 할 수 있는 지를 확인합니다. 이것을 최대 유량 문제(Max Flow)로 정의하며 해결하기 위한 알고리즘으로 에드몬드 카프 알고리즘(Edmonds-Karp)을 적용합니다. 또한 네트워크 플로우는 도로망의 교통 흐름을 분석하거나 전자 회로의 전류, 배수관을 흐르는 유체, 유량 등을 연구하는데 적용됩니다. 현재 흐르고 있는 데이터의 양을 유량, 간선에 ..