오늘 학습 키워드

• 투포인터 알고리즘

1. 투포인터

프로그래머스 "연속된 부분수열의 합"

• 해당 문제를 Brute Force로 이중 for문을 돌린다면 O(N^2)의 시간복잡도를 가져 시간초과가 발생함

• O(N)의 시간복잡도를 가지는 투포인터 알고리즘을 이용하여 문제 해결 가능

투포인터 알고리즘을 고려할만한 상황

1. 포인터로 구간을 나타낼 수 있을 때
   1차원 배열, 2차원 배열 등 여러 지점에서 값을 동시에 추적하는 상황

2. 문제가 부분 구간, 부분 집합 등 범위 기반
   구간합, 부분집합 합, 최장/최단 구간 찾기 등과 같이 특정 범위를 구하는 상황

3. 정렬된 배열 또는 연속된 값을 찾는 상황

해결방법

• 해당 문제는 가장 작은 부분배열만을 구하면 되므로, 투포인터 방식으로 부분배열의 시작점과 끝점을 따라가며 문제를 해결

• sequence배열의 인덱스 0번을 투포인터(L, R)로 가리키고, 해당 부분배열의 합이 k보다 작으면 R을 증가/ k보다 크면 L을 증가시킴

• 부분배열의 합이 k보다 작을 때 L을 감소시키면 해당 경우는 이미 이전에 탐색한 경우이므로 R만 증가시켜 다음 경우를 탐색

• 부분배열의 합이 k보다 큰 경우 R을 감소하는 방식으로 다른 경우를 탐색하지 않는 것이 이해되지 않았음

• 이는 귀류법으로 접근하여, R을 감소시켰을 때 해당배열(L~R-1)의 합이 k와 같은 경우가 있다 가정.
  하지만, 이전에 R-1 포인터가 R로 증가했다는 것은 k보다 부분배열의 합이 작았다는 것이므로, 이전의 가정과 모순됨.

• 따라서 위와 같은 로직으로 L과 R 2개의 포인터를 우측으로 옮기면서 O(N) 시간복잡도로 모든 경우를 탐색하여 문제를 해결할 수 있다

2. 연습 문제

쉬운 문제

• 연속된 부분합이 M 이상이 되는 가장 짧은 구간:
  • 부분합이 특정 값 이상이 되는 최소 길이 구하기
  • 백준 1806번 – 부분합
• 소수의 연속합:
  • 연속된 소수의 합이 특정 값이 되는 경우 구하기
  • 백준 1644번 – 소수의 연속합

중간 난이도

• 수 고르기:
  • 정렬된 배열에서 두 수의 차이가 M 이상이면서 가장 작은 차이 구하기
  • 백준 2230번 – 수 고르기
• 두 용액 문제:
  • 배열에서 두 원소의 합이 0과 가장 가까운 쌍 찾기
  • 백준 2470번 – 두 용액

실전/응용 난이도

• 다이어트 문제:
  • 두 수의 곱이 정수일 때, 조건을 만족하는 쌍 찾기
  • 백준 1484번 – 다이어트
• 회전 초밥:
  • 연속 구간, 중복제거, 누적합 등 여러 알고리즘 응용 문제
  • 백준 2531번 – 회전 초밥