NEMOSTAR5

라빈 카프(Rabin-Karp) 알고리즘은 특이한 문자열 매칭 알고리즘입니다. 항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘입니다. 라빈 카프 알고리즘은 해시(Hash) 기법을 사용합니다. ◆ abacaaba의 해시 값 = 97 * 2^7 + 98 * 2^6 + 97 * 2^5 + 99 * 2^4 + 97 * 2^3 + 97 * 2^2 + 98 * 2^1 + 97 * 2^0 + = 24,834 물론 해시 값이 중복되는 경우도 발생할 수 있습니다. 이것을 충돌(Collision)이라고 하는데, 보통 발생률이 높지 않기 때문에 무시하고 넘아가는 것입니다. 실제로는 충돌이 발생하는 경우 포인터(Pointer)를 이용해 연결 자료구조를 이용해 해결합니다.(해쉬 체이닝 기..

KMP 알고리즘으로 대표적인 문자열(String) 매칭 알고리즘입니다. 문자열 매칭 알고리즘이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘입니다. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 '반복되는 연산을 얼마나 줄일 수 있는지'를 판별하여 매칭할 문자열을 빠르게 점프하는 기법입니다. 우리가 구해야 할 것은 위와 같이 접두사와 접미사가 일치하는 최대 길이입니다. 길이 문자열 최대 일치 길이 1 a 0 2 ab 0 3 aba 1 4 abac 0 5 abaca 1 6 abacaa 1 7 abacaab 2 8 abacaaba 3 위와 같이 접두사와 접미사를 구하게 되면 접두사와 접미사가 일치하는 경우에 한해서는 점프(Jump)를 수행할 수 있다는 점에서 몹시 효율적입니다. 이..

이분 매칭은 네트워크 플로우 알고리즘과 연계되는 개념이다. 이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘이다. '사람'이라는 집단과 '노트북'이라는 두개의 집단이 등장합니다. 효과적으로 매칭시켜준다는 말은 다시 말해 '최대 매칭(Max matching)'을 의미하는 것입니다. 모든 사람 각각이 노트북을 선택하여 가장 많이 연결되는 경우를 찾는 문제라고 볼 수 있습니다. 그림을 한번 다음과 같이 플로우로 표현해보도록 합시다. 네크워크 플로우와 정확히 일치하게 됩니다. 위와 같이 이분 매칭 알고리즘은 네트워크 플로우로 표현할수 있습니다. 각 용량(Capactiy)를 1로 설정한 네트워크 플로우 문제를 이해할 수 있는 것입니다. 다만 우리가 이전에 공부했던 에드몬드 카프 알고리즘은 시간 복잡..

네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘이다. 이러한 알고리즘은 교통 체증, 네트워크 데이터 전송 등의 다양한 분야에 활용되고 있다. 표현 방식은 유량(Flow)/용량(Capacity)이다. 즉 1에서 2로 가는길은 12명이 갈 수 있는 용량에 실제로는 0명이 가게 되었다는 소리이다. 이제 간단하게 하나의 간선으로 용량과 용량을 표현해보면, 위와 같이 A에서 B로 갈 수 있는 용량은 8, B에서 C로 갈수 있는 용량은 6, C에서 D로 갈 수 있는 용량은 7이라고 해보자. 이때 A에서 D로 최대한 많은 용량을 보내려고 할 때 가장 합리적인 양은 얼마일까? 바로 6이다. 바로 이러한 문제를 해결하는 핵심 알고리즘이 네트워크 플로우 알고리즘이다...