meet in the middle (1) 썸네일형 리스트형 브루트 포스[4]:두포인터, 중간에서 만나기 (Brute Force[4]:Two Pointers, Meet in the Middle(MITM)) 브루트 포스(brute force) 이러한 브루트 포스방법 중에서 투포인터, 중간에서 만나기에 관해서 소개를 하려고 한다. 두 포인터(Two Pointers) 배열에서 전체의 경우의 수를 반복문을 통해서 찾는 것이 아니라 두개의 포인터를 조작하여 원하는 결과를 얻는 방법이다. 여기서 두개의 포인터를 이용하여 기존보다 시간복잡도가 줄어드는 구조를 만들 수 있다. 두 포인터 예제 2003 - 수들의 합2 https://www.acmicpc.net/problem/2003 A[i]+...+A[j] = M이 되는 i,j 쌍의 개수를 찾는 문제와 같다. 가장 기본적으로 생각 할 수 있는 방법은 반복문을 만드는 것이다. 반복문으로 i와 j를 선택하고 i부터 j까지의 합을 구한다. (i선택 x j선택 x 합더하기 = .. 이전 1 다음