슬라이딩 윈도우는 일정한 길이의 범위를 이동하여 조건에 맞는 값을 찾는 알고리즘이다. 한 칸씩 이동 하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다.
n,m=map(int,input().split()) # n: 입력받을 정수의 개수, m: 연속된 구간의 크기 (10, 5)
arr=list(map(int,input().split()))
Max,sum=0,0
for i in range(m): # 처음 m개의 구간 (0번 인덱스부터 4번인덱스)의 합 구하기
sum+=arr[i]
for i in range(n-m+1):
if sum>Max:
Max=sum
if i==n-m: break
sum+=arr[i+m] # i+m: 5~10
sum-=arr[i] # i: 0~5
print(Max)
# 비효율적인 방법
def minArray(nums, k):
result = sum(nums[0:k])
for i in range(1, len(nums)-(k-1)):
r = sum(nums[i:i+k])
if r < result:
result = r
return result
# 슬라이딩 윈도우
def minSlidingWindow(nums, k):
min_sum = 9999
window_sum = 0
start = 0
for end in range(len(nums)):
window_sum += nums[end]
if end >= k - 1:
# 0~k-1 까지 더한 값이 최소값보다 작다면, 최소값을 갱신
if window_sum <= min_sum:
min_sum = window_sum
# 윈도우에 포함된 맨 앞자리 수를 제거
window_sum -= nums[start]
# 윈도우 시작 인덱스를 하나 증가
start += 1
return min_sum
투 포인터는 데이터에 순차적으로 접근해야 할 때 두 개의 점 위치를 조절하여 조건에 부합하는지 판단하는 알고리즘이다. 공통 부분을 제외하고 포인터로 이동하는 원소의 처리만 하면 되므로 유용하게 쓰일 수 있다.
n, target = map(int,input().split())
arr = list(map(int,input().split()))
cnt, sum = 0, 0
high, low = 0, 0
while(1):
if sum > target: # 합이 타겟보다 크면
sum -= arr[low] # sum에서 뺴고
low += 1 # low 의 index를 1증가
elif high == n: break
else:
sum+=arr[high] # 합이 타겟보다 작거나 같다면
high+=1 # sum에 더하고 high의 인덱스를 1증가
if sum==target:
cnt+=1
print(cnt)
범위가 매우 크기 때문에 2중 포문으로 풀면 런타임 에러가 난다. 그러므로 투 포인터를 활용하여 풀이해야 한다.
# 시간 초과가 나는 코드
def not_tow_pointer(nums):
count = 0
for i in range(N):
for j in range(i, N):
r = sum(nums[i:j+1])
if r == M:
count += 1
print(count)
# 투포인터
def two_pointer(nums):
count = 0
start, end = 0, 0
window_sum = nums[start]
while start < N:
if window_sum == M:
count += 1
window_sum -= nums[start]
start += 1
elif window_sum < M:
end += 1
if end >= N:
break
window_sum += nums[end]
else:
window_sum -= nums[start]
start += 1
print(f'start = {start} / end = {end}')