재귀 없이, 테이블 없이도 DP? 무차별적 접근에서 본능적 해결법으로의 전환

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

알고리즘, 데이터 구조

대상자

초보 알고리즘 개발자 및 DP 기법을 학습하는 프로그래머

핵심 요약

• DP는 재귀/메모화/테이블에 얽매이지 않으며, 중복 작업 최소화에 초점
• 문제 관점 전환: 윈도우 크기 대신 요소 중심 접근
• 모노톤 스택 활용: left[i], right[i] 계산으로 최적의 윈도우 크기 도출

섹션별 세부 요약

1. DP의 고정관념 깨기

• 전통적 DP 흐름: 재귀 → 메모화 → 테이블 → 공간 최적화
• 문제 풀이 시도: 슬라이딩 윈도우 + 우선순위 큐로 접근 → TLE 발생
• 고정관념의 한계: 반복적 작업 없음에도 DP적 사고 적용 가능

2. 문제 관점 전환: 요소 중심 접근

• 기존 접근: 윈도우 크기 고정 → 모든 서브배열의 최소값 탐색
• 새로운 접근: 특정 요소가 최소값이 되는 윈도우 크기 계산
• 모노톤 스택 활용: left[i] (이전 더 작은 요소), right[i] (다음 더 작은 요소) 계산

3. 모노톤 스택 기반 알고리즘

• 윈도우 크기 계산: len = right[i] - left[i] - 1
• 결과 배열 업데이트: P[len] = max(P[len], arr[i])
• 예시 배열: M = [10, 20, 30, 50, 10, 70, 30] → P = [7, 3, 2, 10, 10, 70, 30]

4. DP의 본질 재정의

• DP 핵심 원칙: 중복된 작업을 피하는 사고방식
• 실용적 팁:

- 서브배열 반복 시 프리픽스 합 또는 슬라이딩 윈도우 고려

- 범위 최소/최대 탐색 시 모노톤 스택 활용

- 중첩 루프 많을 시 문제 관점 전환 시도

결론

• DP는 재귀/테이블에 얽매이지 않고, 중복 작업 최소화를 위한 사고방식
• 모노톤 스택을 활용한 요소 중심 접근은 TLE 문제를 해결하는 효율적 방법
• 문제 풀이 시 "무엇을 반복하고 있는가?"에 대한 질문이 핵심