C++: 투 포인터(Two Pointers)

투 포인터(Two Pointers) 기법

• 두개의 포인터를 두고 여러번 순회할 것을 한번의 순회로 처리하는 기법의 통칭
• 핵심 조건 - 단조성(Monotonicity)
  • 한방향으로만 변하는 성질
  • ex) 배열 왼쪽이 오른쪽보다 큼, 계속 증가, 계속 감소

    대표 문제 - 숫자 합 찾기

• 정렬된 배열된 숫자에서 2개선택이 특정 값인 쌍 찾기
  • 양쪽에 포인터 하나씩
  • 결과 나올때까지 반복
    • 더 커져야하면 왼쪽 포인터 증가
    • 더 작아저여하면 오른쪽 포인터 감소
  • 전체 탐색보다 훨씬 적은 시행횟수 보장
• 그럼 L이 다시 왼쪽으로 돌아갈 상황 없음?
  • 기준이 정해져있어서 키울때, 줄일 때 정해져있음 ->방향성은 일정함
• 이진탐색과 유사
  • 단조성의 서로 다른 활용
• 정렬되어있지 않으면?
  • A - 정렬하고 시도
  • B - 해쉬(unordered_set) 활용
    • x마다 target-x가 있었는지 O(1)로 확인

다른 문제 - 회문, 반대로 읽어도 같은 말

• A - 양쪽 끝에서 포인터를 움직임
  • 같은 글자면 한칸씩 안쪽으로
  • 다르면 false반
• B - 슬라이딩 윈도우도 가능

활용

• 쓸 수 있을법한 환경
  • 정렬된 배열에서의 두 원소의 관계를 확인해야될때
  • 회문/대칭같은 상황에서의 검사
  • 서로 다른 정렬된 두 배열의 합치기
  • 단조성이 있나?
    • 쌍/짝을 찾기
    • 정렬되어 있기/정렬 가능
    • 한쪽을 바꾸면 일관되게 바뀜(단조성)
• 게임
  • 사거리 안의 적 쌍 찾기
  • 두 아이템 조합 매칭
  • 정렬된 좌표 거리 비교
  • 프레임단위로 실행되야할 $O(n^2)$이면 부담일 것들을 $O(n)$ 으로 최적화
• 웹서버
  • 타임 스템프
  • DB 인덱스 범위 확인
  • 리스트 머지/교집합 연산
  • Git diff
• 일반CS
  • 인터뷰에 빈출되는 유형
  • 외부정렬
  • MapReduce
  • 효율적인 선형 사고 기법
• 두개의 정렬된 흐름 동시에 따라가며 하나로 처리.