2096번 - 내려가기
문제 분류에 dp 말고도 슬라이딩윈도우가 있는데
슬라이딩 윈도우하고는 상관없는 문제인 것 같습니다.
인풋 사이즈가 n*3이 아니라 n*m이고, 선택할 수 있는 다음 칸의 x좌표는 현재 x좌표로부터 왼쪽으로 최대 몇 칸, 오른쪽으로 최대 몇 칸,비교할 숫자 갯수는 최대 m개
인 문제일 때 슬라이딩 윈도우 문제입니다.
위 문제를 슬라이딩 윈도우로 풀지 않았을 때 시간복잡도는 O(nm^2),슬라이딩 윈도우로 풀었을 때의 시간복잡도는 O(nm)입니다.
dp에서 테이블을 재활용하면서 메모리를 아끼는 (흔히 토글링이라고도 불리는) 테크닉을 슬라이딩 윈도우라고 부르기도 합니다.
감사합니다.
댓글을 작성하려면 로그인해야 합니다.
wx776654 4년 전
문제 분류에 dp 말고도 슬라이딩윈도우가 있는데
슬라이딩 윈도우하고는 상관없는 문제인 것 같습니다.
인풋 사이즈가 n*3이 아니라 n*m이고, 선택할 수 있는 다음 칸의 x좌표는 현재 x좌표로부터 왼쪽으로 최대 몇 칸, 오른쪽으로 최대 몇 칸,비교할 숫자 갯수는 최대 m개
인 문제일 때 슬라이딩 윈도우 문제입니다.
위 문제를 슬라이딩 윈도우로 풀지 않았을 때 시간복잡도는 O(nm^2),슬라이딩 윈도우로 풀었을 때의 시간복잡도는 O(nm)입니다.