투포인터
코딩테스트를 보며, 시간초과 나도록 빡구현을 했다. 후기를 찾아보면 내가 주로 틀린 것은 투포인터 혹은 이진트리였다. 투포인터 알고리즘에 대해서 알고는 있지만, 명확한 이해가 없어서 다시 알아봤고 이를 활용 가능할 정도로 연습해야겠다고 생각했다.
what?
말 그대로 두개의 포인터를 사용하는 알고리즘이다.
두 점의 위치를 기록하며 처리하는 알고리즘으로, 정렬되어있는 두 리스트의 합집합에서도 사용된다.
투포인터 알고리즘은 배열이나 문자열과 같은 연속적인 자료 구조에서 부분 배열, 부분 문자열, 혹은 특정 조건을 만족하는 쌍을 찾는 문제에서 사용된다.
- 장점
시간복잡도는 어떻게 될까?
시간복잡도
포인터마다 결국 탐색하는 배열만큼 옮겨진다. 즉, 갔던 길은 되돌아가지 않는다는 것이고 하나의 포인터는 O(N)시간복잡도를 가진다.
그렇다면 2개일 때, O(2N)일텐데 2는 상수이기에 빅오표기법에 의해 무시한다.
-> O(N)을 가지기에 시간복잡도에서 매우 효율적이다.
- 단점
아무래도 그냥 빡구현 (이중포문) 보다 어렵다. 따라서 기본 문제들이 보통 백준기준 골드5정도다. 그래서 정확히 이해하고 연습을 많이 해야한다.
how?
| 사용방법은? 두개의 포인터의 위치를 저장하며 옮긴다. 특정 조건을 걸어서 s와 e 포인터를 옮기기를 반복한다.
- 동일한 index에서 pointer가 같이 시작 -> 서서히 멀어지기
- 양 끝의 index에서 pointer가 따로 시작 -> 서서히 모여지기
그렇다면 서서히 멀어뜨리는 경우는? 문제에 따라서 조금 더 알맞은 것을 고르면 된다.
에를 들어, 부분합 해당 문제는 start와 end의 포인터를 옮기면? 부분 배열을 찾는 문제이기에 동시에 같은 위치에서 부분배열을 변경해가며 특정 조건을 만족하는지 확인해야한다.
- 부분 배열 포인터 시작위치
s를 시작포인터, e를 끝포인터라고 하자.
둘다 마지막 index를 향해간다.
| s, e | |||||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 2 | 5 | 8 | 1 |
예시를 들어,
부분합을 찾는다면?
import sys
input = sys.stdin.readline
n,s = map(int, input().split())
nums = list(map(int, input().split()))
start = end = 0
sum = 0
min_len = n
flag = False
while start < n:
if sum < s: #부분합이 s이하라면 end+1
if end>=n:
break
sum += nums[end]
end+=1
else: # 부분합이 s이상이라면 s +1
flag = True
min_len = min(min_len, end-start)
sum -= nums[start]
start+=1
if flag ==False:
print(0)
else:
print(min_len)- 특정 만족하는 쌍을 찾는 경우
주로 정렬 후에 양 끝쪽에서 시작한다. 왜냐? 정렬을 하면 규칙이 있고 그 규칙 하에 양 끝쪽에서 시작하면 가치치기가 빠르게 되기 때문이다. 정렬의 특성을 활용한다.! 그리고 조건을 만족하는 쪽으로 포인터를 이동하며 찾는 것을 생각하면 양쪽 끝에서 시작하는게 올바른 선택이다.
두 수의 합 해당 문제를 풀어보면 이해할 것이다.
- 부분 배열 포인터 시작위치 (정렬의 속성을 사용)
| s | e | ||||||
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 8 | 10 |
n = int(input())
numbers = list(map(int, input().split()))
result = int(input())
s, e = 0,n-1
numbers.sort()
count=0
while s!=e:
if numbers[s] + numbers[e] <= result: # 더 작은 경우에는 더 값을 키워야하기에 s를 증가
if numbers[s] + numbers[e] == result:
count+=1
s+=1
else: # 값을 줄여야하기에 e를 -
e-=1
print(count)
문제 풀이 리스트
- 처음에 시간초과
- 나중 풀이 : 투포인터 -> O(N)으로 해결
핵심 ) start와 end 포인터를 언제, 어떤 경우에 바꿔줘야 할지 생각하는 포인트
시계, 반시계 중 작은 하나 -> dist 라고 하자. ---(1)
result는 가능한 dist 중 가장 큰 값이 된다.
- result가 update
-> end 포인터를 +1, 증가한 쪽의 거리를 합에 누적 - result가 update가 안 될 때 (result가 (1)에서 구한 dist가 아니라면 update되지 않은거다. )
-> start 포인터를 +1, 누적합에 값을 빼준다.
update될때까지만 end를 증가시키는 이유는 update되지 않았다는건 dist1이 가장 큰 값이 아니라는거고 그렇다는건 end를 또 늘려도? 그다음은 무조건 dist1이 가장 큰 값이 아니게 되기에 더 탐색할 필요없음.
n = int(input())
s_diff = [0]*(n)
for i in range(n):
s_diff[i] = int(input())
total = sum(s_diff)
start = end = 0
result = 0
min_now = 0
while start <= end and end < n:
min_dist = min(min_now, total - min_now) # 둘 중 작은게 두 점사이의 길이
result = max(min_dist, result)
if min_now == min_dist: # 현재가 가장 작은 값이였다면
min_now += s_diff[end]
end+=1
else:
min_now -= s_diff[start]
start +=1
print(result)
