2003

[알고리즘/Java] 투 포인터(Two Pointers)

[ 1 ] 기본내용 "투 포인터"는 1차원 배열에서 각기 다른 원소를 가리키는 2개의 포인터를 활용하여 원하는 값을 얻는 알고리즘이다. 이때, 포인터는 C/C++에서의 포인터가 아닌 배열에서의 "인덱스"를 의미한다. 2개의 포인터를 적절히 이동시키며 시간 복잡도를 최적화할 수 있는 것이 투 포인터 알고리즘의 핵심이다. 투 포인터가 자주 활용되는 문제로는 (1) target 값을 미리 설정하고, 특정 배열 내에 target 값과 같은 - 유사한 부분 합이 몇 개 존재하는지 계산하는 문제 (2) 배열 내 target = arr[i] + arr[j] 를 만족하는 (i, j) 쌍이 몇 개 존재하는지 계산하는 문제 등이 있다. [ 2 ] 부분 합에서의 투 포인터 해당 내용은 대표 예제인 백준 2003번을 통해 살..