백준 2169번(로봇 조종하기)은 단순한 DP처럼 보이지만, 한 행에서 양방향 이동이 가능하다는 조건 때문에 순환 참조(Circular Dependency) 문제가 발생합니다. 본 리포트에서는 O(NM²)의 비효율적인 접근이 왜 운 좋게 통과되었는지 분석하고, 이를 O(NM)으로 최적화하기 위한 ‘Directional Split DP(방향 분리 DP)’ 기법을 심층적으로 다룹니다. 좌/우 스캔을 통해 DP의 핵심 전제인 DAG(Directed Acyclic Graph)를 어떻게 복원하는지 상세히 설명합니다.
올바른 괄호 문자열의 개수를 구하는 백준 10422번 문제는 단순한 규칙 찾기로 접근하면 ‘중복 카운팅’의 늪에 빠지기 쉽습니다. 본 리포트에서는 *2 연산이나 단순 분할(dp[j]*dp[i-j])이 왜 실패하는지 분석하고, ‘첫 번째 괄호’를 기준으로 중복을 원천 차단하는 **(A)B 구조(카탈란 수)**의 도출 과정을 증명합니다. 또한, 구현 단계에서 흔히 범하는 모듈러 연산의 누적 실수까지 상세히 다룹니다.
‘K번째 문자열 찾기’는 알고리즘 문제해결에서 ‘생성(Generation)’과 ‘계수(Counting)’의 차이를 극명하게 보여주는 대표적인 유형입니다. 본 리포트에서는 백준 1256번을 예시로, 문자열을 직접 생성하려는 시도가 왜 메모리 초과를 유발하는지, 그리고 List
DP 배낭 문제에서 ‘반복문의 순서’가 알고리즘의 성격(순열 vs 조합)을 어떻게 결정짓는지 심층 분석합니다. 백준 1106번 호텔 문제를 통해 최적화 문제에서는 두 방식이 모두 통하지만, 경우의 수 문제에서는 순서가 정답을 가르는 핵심임을 밝힙니다. 더불어 ilways.com의 심화 포스트를 통해 Unbounded Knapsack의 다양한 변형을 학습할 수 있도록 안내합니다.
단순한 자리 배치 문제가 아닌 ‘피보나치 수열’의 변형임을 간파하는 것이 핵심입니다. 초보자가 흔히 범하는 ‘상태 시뮬레이션(dp[n][3])’ 접근법이 왜 복잡도 폭발을 일으키는지 논리적으로 분석하고, ‘마지막 행동’에 집중하여 문제를 선형(Linear)으로 단순화하는 과정을 다룹니다. VIP 좌석을 ‘분할 지점’으로 활용하는 실전 테크닉까지 완벽하게 정리했습니다.
백준 2533번 ‘사회망 서비스’ 문제를 통해 Tree DP의 핵심 원리를 분석합니다. 트리의 레벨별 접근이 실패하는 이유와 함께, ‘부모의 상태가 자식의 선택을 제약한다’는 관계성을 이용해 dp[node][state] 점화식을 유도하는 과정을 설명합니다. 특히 DFS의 후위 순회(Post-order)를 활용한 ‘방문-위임-결정’의 3단계 구현 공식을 제시하고, 이를 적용한 O(N) 자바 코드를 상세히 해설합니다.
백준 11049번 ‘행렬 곱셈 순서’를 통해 구간 DP(Interval DP)의 핵심 원리를 분석합니다. 선형 DP와의 구조적 차이를 설명하고, 문제 해결을 위한 3가지 식별 힌트(인접 결합, 상태 의존성, N=500)를 제시합니다. 특히 구간 DP의 필수 구현 패턴인 ‘길이-시작점-분할점’ 3중 루프 공식을 상세히 해설하며, 이를 적용한 Java 모범 코드를 제공합니다.
백준 7579번 ‘앱’ 문제를 통해 0/1 Knapsack 알고리즘의 핵심을 분석합니다. 목표 값(메모리)의 범위가 클 때 ‘비용’을 기준으로 DP 테이블을 설계하는 발상의 전환 과정을 3단계(인덱스 선정, 제약 검증, 정의 뒤집기)로 체계화했습니다. 또한, 1차원 배열 최적화 시 필수적인 ‘역순 순회’의 논리적 근거를 설명하며, 제공된 자바 코드가 왜 최적의 해법인지 기술적으로 해설합니다.
백준 1915번 문제는 O(N5)에 달하는 완전 탐색의 비효율성을 극복하기 위해 DP를 도입해야 하는 대표적 사례입니다. 본 리포트는 현재 좌표를 ‘우측 하단 끝점’으로 재정의하여 O(NM)으로 최적화하는 과정을 상세히 분석합니다. 특히 min(위, 왼쪽, 대각선) + 1 점화식이 성립하는 기하학적 필연성을 증명하고, 많은 개발자가 범하는 ‘참조 순서(Dependency) 오류’를 케이스 스터디로 다루어 2차원 DP 설계의 핵심 원리를 깊이 있게 전달합니다.
백준 17070번 ‘파이프 옮기기 1’을 통해 격자 탐색 문제에서 DFS와 DP의 차이를 심층 분석합니다. N이 작을 때는 직관적인 DFS가 유효하지만, 입력 크기가 커질수록 발생하는 ‘중복 연산’의 한계를 지적합니다. 이를 극복하기 위해 (행, 열, 방향)을 상태로 갖는 3차원 DP 점화식을 설계하고 구현하는 과정을 보여주며, 문제 조건에 따라 최적의 알고리즘을 선택하는 기준을 제시합니다.