wx776654   4년 전

문제 분류에 dp 말고도 슬라이딩윈도우가 있는데

슬라이딩 윈도우하고는 상관없는 문제인 것 같습니다.

인풋 사이즈가 n*3이 아니라 n*m이고, 선택할 수 있는 다음 칸의 x좌표는 현재 x좌표로부터 왼쪽으로 최대 몇 칸, 오른쪽으로 최대 몇 칸,비교할 숫자 갯수는 최대 m개

인 문제일 때 슬라이딩 윈도우 문제입니다.

위 문제를 슬라이딩 윈도우로 풀지 않았을 때 시간복잡도는 O(nm^2),슬라이딩 윈도우로 풀었을 때의 시간복잡도는 O(nm)입니다.

Green55   4년 전

dp에서 테이블을 재활용하면서 메모리를 아끼는 (흔히 토글링이라고도 불리는) 테크닉을 슬라이딩 윈도우라고 부르기도 합니다.

wx776654   4년 전

감사합니다.

댓글을 작성하려면 로그인해야 합니다.