슬라이딩 윈도우 기법
창틀에 붙어있는 창문을 밀듯이 특정 범위를 이동시키며(밀면서) 변화하는 내부 값들을 처리하는 기법
위와 같은 [1,3,2,6,-1,4,1,8,2]의 배열에서 연속된 수 5개의 합의 최댓값을 구한다고 할 때 슬라이딩 윈도우 기법을 이용하면 효율적으로 처리할 수 있다.
첫번째 window 1+3+2+6+(-1) = 11 에서 두번째 window로 넘어 갈 때는 1을 빼주고 4를 더해주기만 하면 되므로 3+2+6+(-1)+4를 쌩으로 할 때보다 들어가는 연산의 수가 적어 훨씬 효율적으로 최댓값을 구할 수 있다.
boj_2096 : 내려가기
문제
숫자표가 주어져 있을때, 얻을 수 있는 최대 점수, 최소 점수를 구할 수 있는 프로그램을 작성하시오, 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 N이 주어진다, 다음 N개의 줄에는 숫자가 세 개씩 주어진다.
숫자는 0,1,2,3,4,5,6,7,8,9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
풀이 1
graph와 dp-table 모두 Nx3 만큼의 메모리를 할당해 놓고 채워넣기
메모리 초과가 발생
import sys
n = int(input())
graph = [[0 for _ in range(3)]]
dMax = [[0 for _ in range(3)] for _ in range(n+1)]
dMin = [[0 for _ in range(3)] for _ in range(n+1)]
for _ in range(n):
graph.append(list(map(int,sys.stdin.readline().split())))
for j in range(3):
dMax[1][j] = graph[1][j]
dMin[1][j] = graph[1][j]
for i in range(2,n+1):
dMax[i][0] = dMax[i-1][0]+max(graph[i][0], graph[i][1])
dMin[i][0] = dMin[i-1][0]+min(graph[i][0], graph[i][1])
dMax[i][1] = dMax[i-1][1]+max(graph[i][0], graph[i][1], graph[i][2])
dMin[i][1] = dMin[i-1][1]+min(graph[i][0], graph[i][1], graph[i][2])
dMax[i][2] = dMax[i-1][2]+max(graph[i][2], graph[i][1])
dMin[i][2] = dMin[i-1][2]+min(graph[i][2], graph[i][1])
print(max(dMax[n]), min(dMin[n]))
풀이 2
graph와 dp-table 모두 1x3의 메모리만 사용하는 방식으로,
숫자를 입력받으면서 기존의 dp-table과 새로 입력받은 값을 이용해서 dp-table을 갱신하는 방식
dp문제에서 슬라이딩 윈도우 기법 활용
import sys
n = int(input())
graph = list(map(int,sys.stdin.readline().split()))
dMax = [graph[0],graph[1],graph[2]]
dMin = [graph[0],graph[1],graph[2]]
for i in range(1,n):
graph = list(map(int,sys.stdin.readline().split()))
dMax = [graph[0]+max(dMax[0], dMax[1]), graph[1]+max(dMax[0], dMax[1], dMax[2]), graph[2]+max(dMax[2], dMax[1])]
dMin = [graph[0]+min(dMin[0], dMin[1]), graph[1]+min(dMin[0], dMin[1], dMin[2]), graph[2]+min(dMin[2], dMin[1])]
print(max(dMax), min(dMin))
a = a + 1이란 코드에서 첫번째 a를 A, 두번째 a를 B라고 하자,
B는 연산 수행 이전의 기존 a값이고, A는 연산 수행 이후 결과가 저장된 값이다.
이처럼 값이 갱신되는 과정에서도 순서가 있으므로, 굳이 A와 B를 구분하기 위해 새로 메모리를 할당해 처리할 필요가 없다.