ilway

백준 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을 int로 치환하는 과정이 어떻게 문제의 본질을 ‘조합 탐색’으로 변화시키는지 분석합니다. 또한, 파스칼의 삼각형을 이용한 DP 전처리부터 분할 정복을 이용한 ‘Skip Logic’까지, 대규모 탐색 공간을 효율적으로 제어하는 정석 패턴을 상세히 다룹니다.

DP 배낭 문제에서 ‘반복문의 순서’가 알고리즘의 성격(순열 vs 조합)을 어떻게 결정짓는지 심층 분석합니다. 백준 1106번 호텔 문제를 통해 최적화 문제에서는 두 방식이 모두 통하지만, 경우의 수 문제에서는 순서가 정답을 가르는 핵심임을 밝힙니다. 더불어 ilways.com의 심화 포스트를 통해 Unbounded Knapsack의 다양한 변형을 학습할 수 있도록 안내합니다.

단순한 자리 배치 문제가 아닌 ‘피보나치 수열’의 변형임을 간파하는 것이 핵심입니다. 초보자가 흔히 범하는 ‘상태 시뮬레이션(dp[n][3])’ 접근법이 왜 복잡도 폭발을 일으키는지 논리적으로 분석하고, ‘마지막 행동’에 집중하여 문제를 선형(Linear)으로 단순화하는 과정을 다룹니다. VIP 좌석을 ‘분할 지점’으로 활용하는 실전 테크닉까지 완벽하게 정리했습니다.