[알고리즘] 투 포인터

개념

• 각 원소마다 모든 값을 순회해야 할 때, O(N^2)
• 연속하다는 특성을 이용해서 처리, O(N)
• 두 개의 포인터(커서)가 움직이면서 계산
• 처음부터 생각하기 어려움, 쉬운 방법부터 생각하자

 

팁

• 처음에는 일일이 손으로 계산 -> 시간복잡도 초과? -> 연속한가? -> 투 포인터
• for 내부의 투 포인터로 계산하는 값의 최대값이 자료형에 맞는지 확인 필수(int 초과 여부, 파이썬음 해당 안 함)
• 투 포인터의 문제 종류
  • 두 개 다 왼쪽에서 시작
  • 각각 왼쪽, 오른쪽에서 시작 -> 범위가 줄어듦
  • 다른 배열에서 시작
• 일반: O(N) / 정렬 후 투 포인터: O(NlgN)

 

예: N개의 원소를 가지는 배열에서 연속된 k개의 수가 가장 큰 값을 가지는 인덱스를 구해라

• for 문
• N개의 각 원소에 대해 k번씩 순회
• O(N*k)

 

• 투 포인터
• N개의 원소에서 이전 원소 제거 후 다음 원소 더함
• O(2N) = O(N)

 

Idea

• 투 포인터를 활용
• for 문으로 처음의 k개 값을 저장
• 다음 인덱스 더해주고 이전 인덱스 빼줌
• 이때마다 최대값 갱신

시간복잡도

• O(N)

자료구조

• 전체 정수 배열: numeric[]
• 합한 수: numeric