ps:투_포인터
목차
투 포인터
- 흔히 투 포인터라고 부르기는 하는데, 정확히 뭐를 투 포인터라고 부르는지 명확하게 정의된건 아닌것 같다. 대충, 두 개의 포인터를 유지하면서 조건에 따라서 적합한 한쪽을 이동시키는 것을 반복하는 방식으로 작동하는 알고리즘이면 전부 다 투 포인터로 부를 수 있는거 같긴 하다. 일반적으로는 한개의 일차원 배열 상에서, 양쪽 끝에서 출발하는 포인터 두개를 갖고 작업하거나, 한쪽에서 출발하는 두개의 포인터를 갖고 작업하는 경우에 쓰이는것 같지만, 두개의 정렬된 배열에 대해서 두개의 포인터를 유지하면서 머지하는 것을 구현하는 문제에도 투 포인터라는 태그가 붙어있는 것을 보기도 했다.
- 대표적인 활용방법은, 주어진 수들 중에서 합이 X에 가까운 두 수를 찾을때, 또는 차가 X에 가까운 찾을때 사용하는 것이다. 주어진 수들을 정렬하고, 합이 X에 가까운 수를 찾을때는 두개의 포인터가 양쪽 끝(최소값과 최대값)에서 출발하고, 차가 X에 가까운 수를 찾을때는 두개의 포인터가 한쪽 끝에서 출발하게 된다.
- 다른 흔한 유형인, 합이 X에 가깝게 되는 부분배열을 찾는 문제는 여기에 해당이 안되는거 같아 보이기도 하는데 결국은 같은 유형이다. sum(a[i:j] 가)가 X가 되는 i,j를 찾는 것인데, 누적합 배열로 바꿔서 생각하면, p[k] = sum(a[:k]) 인 누적합 배열은 정렬된 상태이고, sum(a[i:j]) = sum(a[:j]) - sum(a[:i]) 이므로 결국 누적합 배열에서 차가 X가 되는 i,j를 찾는 문제이다. 따라서 한쪽 끝에서 두개의 포인터가 출발하게 된다.
구현
- 보통 c++ 로 짠다면, l과 r이 두개의 인덱스를 저장하고 있고, while 루프 안에서 조건에 따라서 l또는 r이 갱신되는 방식으로 구현할 것이다. 또는 인덱스 대신 포인터를 저장하는 식으로 짤 수도 있을것이다. 아무튼 이게 직관적이다
- 하지만 python에서는 배열을 인덱스로 접근하는 것이 효율성에서 좋지 못하다. 그러다보니 다른 방식을 시도하게 되는데, 예를 들면 한쪽포인터를 움직이는 것을 for 루프로 잡고, 그 안에서 다른쪽 포인터를 움직이는 while루프를 만드는 것이다. 파이썬 특성에 따르면 이게 좀더 효율적이기는 할텐데, 문제는 알고리즘이 한눈에 바로 들어오지 않는다는 것이다
- 우선 배열의 인덱스 접근을 피하는 방법은, iterator를 만들어서 next()로 움직이는 방법이 있다. 이 방법은 보기에도 깔끔하다. 이 방법을 사용하자.
- 그다음에.. while True 루프 안에서 l또는 r을 움직일것인가, 이중 루프를 쓸것인가인데.. 우선 코드 예시를 들어보자. 합이 N인 부분수열의 갯수를 구하는 코드이다
while True: try: if num_sum == N: answer += 1 if num_sum <= N: num_sum += next(right_iter) else: num_sum -= next(left_iter) except StopIteration: breakfor num in right_iter: num_sum += num while num_sum > N: num_sum -= next(left_iter) if num_sum == N: answer += 1- 전자가 코드가 좀더 길긴 하지만, 대칭적이라서 좀더 알아보기 쉬운 느낌이다. 전자의 형식으로 코딩하는걸로 결정..
- 전자의 방식으로 단일 루프로 이터레이터를 갖고서 이터레이션을 돌리는 경우, 종료조건을 정하는 것이 조금 헷갈릴수 있다.
- 양쪽 끝에서 출발하는 투 포인터의 경우, 두 포인터가 만날때까지 돌려야 한다. 이경우에는 그냥 반복 횟수가 n-1이 될때까지 반복하면 된다.
- for _ in range(N-1): 로 코딩하자
- 예제 코드는 용액 참고.
- 한쪽 끝에서 출발하는 투 포인터의 경우, 오른쪽 포인터가 끝까지 갈때까지 돌려야 한다.
- while True로 반복시키고 그냥 try-except에로 StopIteration 예외를 잡아서 빠져나올수도 있지만, 코드가 덜 예쁘다. while right is not None 으로 반복시키고, right=next(r_iter, None) 로 기본값을 넣어서 next를 호출하는 방식으로 하자.
- 예제 코드는 수 고르기 참고.
- (TODO) 생각해보니.. 리스트와 두개의 인덱스 또는 두개의 이터레이터를 갖고 다니는 방법 대신에 그냥 데이터를 deque에 저장하고 양쪽에서 pop해버리면서 처리하는것도 가능할것 같다. 코드는 더 깔끔해질거 같은데 속도가 얼마나 떨어지려나.. 한번 테스트해보자.
관련 문제 유형
- 주로 투 포인터를 사용해서 푸는 문제들이지만, 투 포인터가 아닌 방법으로도 풀리는 문제들도 많다
두 수의 합이 X가 되는 쌍의 갯수
- 정렬 후 투포인터로 풀 수 있다. O(nlogn) + O(n) = O(nlogn)
- 하지만, 그냥 딕셔너리(카운터)에 모든 수와 등장 횟수를 저장하고, 모든 a[i]에 대해서 값이 X-a[i]인 원소의 수를 찾아서 합치면 정렬 없이 O(n)에 풀린다. 이 방식을 쓰자.
- 두 수의 차가 X가 되는 쌍의 경우도 동일하다.
- 관련 문제
- 두 수의 합 - 합이 X가 되는 두 수
두 수의 차가 X에 가장 가까운 쌍 (또는 그러한 쌍의 갯수)
- 정렬 후 투 포인터로 푼다. 한쪽끝에서 두개의 포인터를 출발시킨다. O(nlogn) + O(n) = O(nlogn)
- 관련 문제
- 수 고르기 - 차가 X에 가까운 두 수
두 수의 합이 X에 가장 가까운 쌍 (또는 그러한 쌍의 갯수)
- 차가 X인 쌍을 구하는 것과 마찬가지로 정렬 후 투 포인터로 풀 수 있다. 양쪽 끝에서 포인터들을 출발시킨다. O(nlogn) + O(n) = O(nlogn)
- 하지만 정렬 기준을 바꿔서 정렬하면, 투 포인터를 안쓰고 더 간단하게 구현 가능하다. 역시 O(nlogn) + O(n) = O(nlogn). 이 방식을 쓰자.
- 미리 정렬이 된 상태로 주어진다면, 그냥 투포인터를 쓰는 것이 O(n)이므로 그때는 투포인터를 쓰자
- 관련 문제
세 수의 합이 X가 되는 쌍의 갯수
- 관련 문제
세 수의 합이 X에 가장 가까운 쌍
- 관련 문제
합이 X에 가깝게 되는 부분배열
- 맨 처음에 말했듯이, 누적합 배열을 만든 뒤에 차가 X에 가깝게 되는 두 수를 찾아도 풀이가 가능하지만, 그냥 누적합 배열을 안만들고 원래 배열에서 바로 투포인터를 돌리는 것이 간단하다.
구간내의 서로 다른 아이템의 개수
- 최대 K개의 종류의 아이템을 가지는 가장 큰 구간 (또는 구간의 개수)
- 최소 K개의 종류의 아이템을 가지는 가장 작은 구간 (또는 구간의 개수)
- 모든 종류의 아이템을 가지는 가장 작은 구간으로도 자주 나온다
슬라이딩 윈도우
- 슬라이딩 윈도우는 모든 부분구간들에 대해서 처리할때 사용되는 기법이다. 고정된 사이즈의 윈도우를 이동시키면 그 안에 포함되는 부분구간들을 처리한다는 느낌으로 붙인 이름인데. 사실상 투 포인터에서 두개의 포인터가 일정한 간격을 두고서 움직이는 것과 동일하다.
- 왼쪽 끝값과 오른쪽 끝값만을 이용해서 갱신이 가능한 값들 - 합, 평균, 조건을 만족하는 원소의 갯수 등을 처리할수 있다.
- 최댓값이나 최솟값 같은 경우는 이렇게는 처리가 안된다. monotone queue를 사용하자.
- 구현은 간단하다. 단순히 양 끝의 인덱스를 l과 l+K 로 잡고 l에 대해서만 이터레이션을 돌려도 된다. 하지만 원래 수열과 K부터 시작하는 수열을 zip으로 묶어서 처리하는 것을 선호한다.
sub_sum = sum(nums[:K]) do_something(sub_sum) for l, r in zip(nums, nums[K:]): sub_sum += r - l do_something(sub_sum)
- 관련 문제
ps/투_포인터.txt · 마지막으로 수정됨: 2024/02/26 02:32 저자 teferi
토론