Algorithm/Mitm1 MITM (Meet in the middle) 알고리즘 1. 개요이분탐색 문제를 찾아 풀다가 1450. 냅색문제에서 처음에는 투포인터로 접근해서 풀다가정답을 보니 브루트포스, 분할정복(?), 이분탐색이 한데 어울러진 듯한 느낌을 받아 정리하게 되었다. cf. MITM 기법의 핵심은 브루트포스를 분할하는 것이며, 추가적인 연산에 +a의 알고리즘 기법이 사용되었을 뿐이다. 2. MITM(Meet In The Middle): 브루트포스 알고리즘을 사용해야 할 경우, 브루트포스를 분할해서 복잡도를 최소화하는 알고리즘 기법이다. 분할정복과의 차이점?: 분할정복은 작은 문제들의 해결을 합치면서, 큰 문제의 해결로 이어져 나간다. MITM 문제를 쪼개는 것은 같지만, 중간에서 만나 결합하는 과정에서 +a의 추가적인 연산이 필요하다. 3. 문제 예시*BOJ - .. 2024. 5. 30. 이전 1 다음
