투 포인터

💡 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

 

🚀 투 포인터 예시 1 : 연속된 자연수의 합 구하기

• 백준 2018번 : 수들의 합 5
• 자연수 N(1 <= N <= 10,000,000)을 몇 개의 연속된 자연수 합으로 나타낼 수 있는지 구하기
  • ex) N이 15 : 15, 7+8, 4+5+6, 1+2+3+4+5
• N이 커서 O(nlogn)도 안되고 O(n) 알고리즘을 사용해야 한다.
• 포인터 두 개를 각각 start와 end로 두고 둘 다 첫 인덱스로 초기화 한다.
  • start ~ end 합이 N보다 작다면, end를 +1해서 그 인덱스의 원소 값 만큼 총합에 더한다.
  • start ~ end 합이 N보다 크다면, start를 +1해서 방금 벗어난 인덱스의 원소 값 만큼 총합에서 뺀다.
  • start ~ end 합이 N과 같다면, 정답 카운트를 +1하고 start와 end 모두 +1 한다.

두 포인터 start, end의 초기화

계산 과정

🚀 투 포인터 예시 2 : 두 수의 합 구하기

• 백준 1940번 : 주몽
• 두 재료를 합쳐 M(1 <= M <= 10,000,000)이 되도록 N(1 <= N <= 15,000) 개의 재료에서 2가지를 골라야 한다.
• N이 15,000이므로 O(nlogn) 알고리즘을 사용할 수 있다. 오름차순 정렬로 문제를 쉽게 접근한다.
• 포인터 두 개를 각각 start와 end로 두고, 각각 처음과 끝 인덱스로 초기화한다.
  • start + end < M : 두 재료의 합이 M보다 작으므로, 값을 키우기 위해 start를 +1 한다.
  • start + end > M : 두 재료의 합이 M보다 크므로, 값을 줄이기 위해 end를 -1한다.
  • start + end = M : 두 재료의 합이 M이므로, 정답 카운트를 +1하고 두 포인터 모두 한 칸씩 이동시킨다.
  • start는 +1, end는 -1로만 움직인다.
  • start와 end가 만나면 반복을 종료한다.
• 양쪽 끝에서 두 인덱스가 만날 때 까지 계산을 반복하는 형태이다.

 

🚀 투 포인터 예시 3 : 두 수의 합으로 구해지는 수 구하기

• 백준 1253번 : 좋다
• N개의 수에서 다른 두 수의 합으로 표현되는 수를 '좋은 수'라고 한다.
  • N(1 <= N <= 2,000), N개의 수의 값 A (|A| <= 1,000,000,000, A는 정수)
• N이 2,000이므로 '좋은 수' 하나를 찾는 시간 복잡도는 O(N^2) 보다 작아야 한다.
  • 만약 O(N^2) 알고리즘을 사용한다면, 모든 '좋은 수'를 찾는 시간 복잡도는 O(N^3)
  • 따라서 '좋은 수' 하나를 찾는 알고리즘은 최소 O(nlogn). 정렬, 투 포인터 사용 가능.
  • 단, 자기 자신을 '좋은 수' 만들기에 사용하면 안됨.
• 먼저 N개의 수를 오름차순 정렬
• 투 포인터 i, j의이동 원칙 (K는 찾는 수)

1) A[ i ] + A[ j ] > K : j--;
2) A[ i ] + A[ j ] < K : i++;
3) A[ i ] + A[ j ] == K : i++; j--; count++;

• K가 3번째 인덱스부터 마지막 N이 될 떄까지 위 계산 반복하며 '좋은 수' 카운트

 

🚀 정리

• 투 포인터는 포인터 두 개를 사용해 문제에 제시된 계산 알고리즘 효율을 높일 수 있다.
• 포인터가 두 개라는 특징이 같지만, 세부 아이디어는 여러가지가 있는 큰 범주의 알고리즘이다.
• 백준의 태그는 두 포인터(Two-pointer)로 되어 있다.