알고리듬 - 투 포인터

투 포인터

2개의 포인터를 활용해 문제를 푸는 방식이다.

일반적으로

• 두 개의 포인터가 모두 앞에서 시작하는 경우

• 하나는 앞, 하나는 뒤에서 시작하는 경우

로 구분된다.

 

이를 활용하는 문제를 바로 보자.

백준: 수들의 합 5
https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

해당 문제는 정수 N이 주어질 때 N 미만의 연속된 자연수의 합으로 N을 나타낼 수 있는 경우의 수를 구해야 한다.

 

만약 N이 6이라면 답은 2(1+2+3, 6)이다.

이 문제는 투 포인터를 이용하면 쉽게 풀 수 있는데,

 

N = 6일 때 과정은 아래와 같다.

• 더한 값(sum)이 N보다 작으면 L을 움직이고 값을 더한다.
• sum이 N보다 크면 R을 움직이고 값을 뺀다.
• sum이 6일 때 answer를 1씩 증가해 배열의 마지막까지 탐색하면 종료한다.

 

투 포인터를 떠올린다면 쉽게 풀 수 있다.

 

 

 

이와 달리 L은 왼쪽, R은 오른쪽에서 시작하는 경우의 문제도 있다. 

아래 문제가 그것으로 투 포인터를 이용하면 쉽게 풀 수 있다.

백준: 주몽
https://www.acmicpc.net/problem/1940

1940번: 주몽