[알고리즘 이론] 10. 투포인터

투포인터

• 선형 시간으로 알고리즘을 풀 수 있게 만들어주는 알고리즘이다.
• 연속적인 값들을 이용해 푸는 문제에 적합하다.

원리

1. 배열의 하나의 인덱스를 가리키는 start 점과 end 점 두 개를 만든다.
2. 처음 start 와 end 는 0으로 초기화.
3. start 부터 end까지 합을 구해서 sum에 저장한다. -> 처음엔 0이 저장
4. 배열을 도는데 세 가지 조건으로 돈다
   1. sum == 찾고자 하는 값 -> 찾고자 하는 값이 나왔으니 count를 1 늘려주고, sum 값에서 start 인덱스 값을 빼주고 1을 늘려준다. 그리고 end 값을 1 더한 후 그 인덱스의 값을 sum에 더해준다. -> 문제를 풀어보면 이해할 수 있다.
   2. sum < 찾고자 하는 값 -> sum이 더 작으니까 start값은 그대로 두고, end 값을 1 늘려준 후 그 end 인덱스의 값을 sum에 더해준다.
   3. sum > 찾고자 하는 값 -> sum이 더 크니까 end값은 그대로 두고 start 인덱슥 값을 sum에서 빼주고 start 값을 1 늘려서 갱신해준다.
5. 루프를 탈출하는 경우는 start 값이나 end 값이 배열의 인덱스를 초과하면 예외처리를 통해 탈출한다.

알고리즘 문제 추천

1. 수들의 합 2 (실버 4)

• https://www.acmicpc.net/problem/2003

2. N번쨰 큰 수 (실버 2)

• https://www.acmicpc.net/problem/2075

3. 내려가기 (골드 5)

• https://www.acmicpc.net/problem/2096

4. 부분합 (골드 4)

• https://www.acmicpc.net/problem/1806

참고 자료

https://gaybee.tistory.com/36