Development

코딩테스트를 풀다보면 투 포인터로 풀어야하는 문제들을 자주 볼 수 있습니다. 오늘은 투 포인터 알고리즘에 대해 알아봅시다. [투 포인터(Two Pointers) 알고리즘] 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 위 그림과같이 두 개의 포인터(점)의 위치를 기록하면서 처리한다. [시간복잡도] O(N) 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝난다. 각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N)이다. [예제] 백준 3237 두 수의 합이 투 포인터의 예제입니다. ht..

문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 문제 푸는 방식은 같지만 다른사람 코드가 더 깔끔하여 가져왔다. 이 문제는 start와 end를 사용하는 투 포인터를 사용해야한다. 오름차순으로 정렬을 해주고 양 끝에서 합을 구해가면서 답을 찾는 방식이다. start를 첫 인덱스, end를 마지막 인덱스로 지정하기위해 start = 0, end = n-1을 해준다. start보다 ..