목록알고리즘/투 포인터 (Two Pointer) (1)

프로그래밍에 대한 고찰 및 생각

[투 포인터 알고리즘][1] - 개요 및 백준1806번

투 포인터 알고리즘(Two Pointer Algorithm) 투 포인터 알고리즘은 선형자료구조에서 특정부분집합을 빠르게 찾아낼때 사용된다. 예를 들어 다음 문제를 보자. 백준 1806번 - 부분합 위 문제같은 경우 N = 100000 일때 모든 부분합의 개수는 N^2 으로 많은 시간이 소요된다. 그렇다고 메모이제이션을 하기에는 부분합인 S의 범위가 1억이하이므로 메모리상으로도 초과가 발생한다. 이때 사용할 수 있는 알고리즘이 투 포인터 알고리즘 이다. 다음과 같은 배열에서 합이 10이상이되는 가장 짧은 길이를 구해보자. 먼저 우리가 찾을 부분배열의 시작 인덱스를 start, 마지막 인덱스를 end라고 하자. 처음에는 두값모두 0이다. 이후 현재 부분배열의 합이 S(10) 이상이 아니라면 end++ 하여 ..
알고리즘/투 포인터 (Two Pointer) 2021. 3. 24. 13:32
이전 Prev 1 Next 다음