2개의 포인터를 이용해 알고리즘의 시간복잡도를 최적화하는 방법으로 간단한 알고리즘을 사용한다.
주로 n의 최댓값이 크게 잡혀있고 O(nlog n)의 시간복잡도로 해결이 힘들 때, O(n)의 시간복잡도로 구현해야 한다. 이때, 자주 사용되는 것이 바로 투 포인터 알고리즘이다.
투 포인터 알고리즘은 시작 인덱스와 종료 인덱스를 지정해 서로 조건에 따라 접근하도록 하는 것이다.
🧐슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 후 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 알고리즘이다.
투포인터 알고리즘과 매우 비슷하다.
🧐 백준 17609 (회문) Gold V
🤫solution_17609(시간초과)
string_list = [input() for _ inrange(int(input()))]
defpalindrome(string):# 회문인 경우if string == string[::-1]:
print(0)
# 회문이 아닌경우else:
ans = 2for i inrange(len(string)):
new_string = string[:i] + string[i+1:]
if new_string == new_string[::-1]:
ans = 1print(ans)
for i in string_list:
palindrome(i)
🤫solution_17609
# 유사 회문 판단 함수
def palindrome_like(string, left, right):
while left<right:
if string[left] == string[right]:
left+=1right-=1else:
returnFalsereturnTrue
# 회문 함수
def palindrome(string, left, right):
while left<right:
if string[left] == string[right]:
left+=1right-=1else:
pseudo1 = palindrome_like(string, left+1, right)
pseudo2 = palindrome_like(string, left, right-1)
if pseudo1 or pseudo2:
return1else:
return2return0for string in list([input() for _ inrange(int(input()))]):
print(palindrome(string, 0, len(string) -1))
🧐 백준 1253 (Good Number) Gold IV
🤫 Algorithm
# 해당 원소를 제외한 리스트에서 투 포인터(Two-Pointer)를 통해 # 두 원소의 합이 선택한 원소와 같은지 비교하는 방식으로 해결할 수 있다.1.num리스트를정렬한다.2.0부터N-1까지반복문을통해특정원소(num[i])를선택하고,해당원소를제외한except_num리스트를생성3.except_num리스트에서투포인터를통해두원소의합(sum)이num[i]인지비교한다.t<num[i]이면left를증가t>num[i]이면right를감소4.2,3과정을반복한다.
🤫solution_1253
N = int(input())
num = list(map(int, input().split()))
num.sort()
cnt = 0for i inrange(N):
except_num = num[:i] + num[i + 1:]
left, right = 0, len(except_num) - 1while left < right:
sum = except_num[left] + except_num[right]
ifsum == num[i]:
cnt += 1breakifsum < num[i]:
left += 1# t 를 증가시켜야 하므로 left 증가else:
right -= 1# t 를 감소시켜야 하므로 right 감소print(cnt)
🧐 백준 11003 (최솟값 찾기, 슬라이딩 윈도우 이용) Platinum V
🤫Algorithm
특정 새로운 원소가 추가될 때 이 원소보다 큰 값은 유지될 필요가 없다.
(인덱스로 볼 때에도 새로 추가되는 원소가 가장 오래 남기 때문.)
덱으로 구성하고 덱의 앞에 항상 최소값이 오도록하기 위해
삽입은 append를 이용해 값과 인덱스로 진행한다.
1. 삽입하기전에 덱을 뒤에서 while로 삽입하려는 요소보다 큰값을 모두 제거.
(삽입한다면 덱은 항상 오름차순으로 정렬된 상태를 자동적으로 유지할 것이다.)
(이는 정렬로 인한 시간복잡도를 없애줘 시간초과가 발생하지 않게 할 수 있다.)
2. 추가적으로 슬라이딩 범위를 벗어난 요소들을 생각하면 아래와 같다.
삽입하기전에 덱을 앞에서부터 보며 인덱스 범위가 벗어난 요소들을 빼준다.
i) 뒤에서부터 확인하며 삽입하려는 요소보다 큰 값들을 제거
ii) 앞에서부터 보며 슬라이딩 범위를 벗어난 요소들을 제거
iii) 현재 요소 삽입
모든 연산이 O(1)으로 전체 배열을 확인하는데 O(n)으로 해결가능하다.
🤫solution_11003
from collections import deque
N, L = map(int, input().split())
A = list(map(int, input().split()))
dq = deque()
for i inrange(N):
first, end = i - L, i
# 현재 들어온 값보다 큰 값들을 제거하여 시간복잡도를 줄임while dq and dq[-1][0] > A[end]: # 덱의 마지막 위치에서 현재값보다 큰 값 제거
dq.pop()
dq.append((A[end], end)) # A, A_idx, 마지막 위치에 현재값 저장if dq[0][1] <= first:
dq.popleft()
print(dq[0][0], end = " ")
