투포인터 (Two-Pointer) 알고리즘

00 개요

• 목표: 코딩테스트 뽀개기!

01 투포인터

1. 투포인터란

• 각 원소마다 모든 값을 순회해야할 때, O(N^2)
• 연속하다는 특성을 이용해서 처리, O(N)
• 두 개의 포인터(커서)가 움직이면서 계산
• 처음부터 생각해내기 어려움, 쉬운 방법부터 생각하는 것 추천 (i.e., 일일히 다 계산해 본 후, 어떠한 패턴이 보이면 그 때 적용해보기)

2. 연습 문제: 백준 2559 수열

• 참조: https://www.acmicpc.net/problem/2559

1) 문제

• Q:
  • 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 
  • 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 
    • 3 -2 -4 -9 0 3 7 13 8 -3 
  • 모든 연속적인 이틀간의 온도의 합은 아래와 같다.
  •  

• Q (continued):
  • 이때, 온도의 합이 가장 큰 값은 21이다.
  • 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,
  •  

• Q (continued): 
  • 이때, 온도의 합이 가장 큰 값은 31이다. 
  • 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
•  입력:
  • 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 
    • 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 
    • 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다.
  • 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.
    • 이 수들은 모두 -100 이상 100 이하이다.
• 출력:
  • 첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.
• 예제 입력 1:

10 2

3 -2 -4 -9 0 3 7 13 8 -3

• 예제 출력 1

21

• 예제 입력 2:

10 5

3 -2 -4 -9 0 3 7 13 8 -3

• 예제 출력 2:

31

2) 사전 계획 수립

• 아이디어
  • 처음 아이디어:
    • for문으로 각 숫자의 위치에서 이후 K개의 수를 더함
    • 이때마다 최댓값으로 갱신
  • 수정된 아이디어 (투포인터 적용):
    
    • for문으로 처음 K개 값을 저장
    • 다음 인덱스의 값을 더하고, 앞의 값을 뺌
    • 이때마다 최댓값을 갱신
• 시간 복잡도
  • 처음 시간 복잡도:
    • for문: O(N)
    • 각 위치에서 K개의 값 더함: O(K)
    • 총: O(NK)
      • → 1e^5 x 1e^5 = 1e^10 → 2억을 넘음 (시간 초과)
  • 수정된 시간 복잡도:
    • 숫자 개수만큼 for문: O(N) = 1e^5 → 가능
      • 앞의 것을 빼주고 뒤의 것을 더해주는 계산, 즉 x 2가 되어서 사실상 O(2N)이지만, Big-O 표기법에서 N앞에 오는 상수 (i.e., 2)는 생략 가능하기 때문에 O(N)이 되는 것
• 자료 구조
  • 전체 정수 배열 (각 숫자들 N개 저장 배열): int[]
    • 수 범위: -100 ~ 100 → INT 가능
  • 합한 수 (K개의 값 저장 변수): int
    • K * 100 = 1e^5 * 100 = 1e^7 → INT 가능
  • 최댓값: int
    • 합한 수와 동일

3) 실습

# 입력이 있을 경우
# import sys
# input = sys.stdin.readline
# N, K = map(int, input().split())
# nums = list(map(int, input().split()))

N, K = 10, 5
data = '''
3 -2 -4 -9 0 3 7 13 8 -3
'''

N, K = 10, 2
data = '''
3 -2 -4 -9 0 3 7 13 8 -3
'''

nums = list(map(int, data.split()))
each = 0

# K개 온도 더해주기
for i in range(K):
    each += nums[i]
    print('nums[i]:', nums[i])
maxv = each
print('initial maxv:', maxv, '\n')

# 다음 인덱스 더해주고, 이전 인덱스 뺴주기
for i in range(K, N):
    print('original:',each)
    each += nums[i]
    print(f'add last index {nums[i]}:',each)
    each -= nums[i-K]
    print(f'subtract first index {nums[i-K]}:',each)
    maxv = max(maxv, each)
    print('new maxv:',maxv, '\n')

print('final maxv:', maxv)

Tip

• 처음부터 생각하기 어렵기 땓문에 쉬운 방법부터 생각하는 것 추천
  • O(N^2) 시간 복잡도를 초과한다면 '연속하다'는 특징을 활용할 수 있는지 확인해보기, 활용 가능 시 투포인터 적용
• for 내부 투포인터 계산하는 값의 최댓값 확인 필수(INT 초과하는지 안하는지 확인, 파이썬에는 해당 안 됨)
• 투포인터 문제 종류
  • 두 개 다 왼쪽에서 / 각각 왼쪽, 오른쪽 / 다른 배열
  • 일반 O(N) / 정렬 후 투포인터: O(NlgN)

참조

1. 개발자 장고, https://www.youtube.com/watch?v=U0TXIFiCIu0&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=6
2.