백준 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 구조(카탈란 수)**의 도출 과정을 증명합니다. 또한, 구현 단계에서 흔히 범하는 모듈러 연산의 누적 실수까지 상세히 다룹니다.
DP 배낭 문제에서 ‘반복문의 순서’가 알고리즘의 성격(순열 vs 조합)을 어떻게 결정짓는지 심층 분석합니다. 백준 1106번 호텔 문제를 통해 최적화 문제에서는 두 방식이 모두 통하지만, 경우의 수 문제에서는 순서가 정답을 가르는 핵심임을 밝힙니다. 더불어 ilways.com의 심화 포스트를 통해 Unbounded Knapsack의 다양한 변형을 학습할 수 있도록 안내합니다.
단순한 자리 배치 문제가 아닌 ‘피보나치 수열’의 변형임을 간파하는 것이 핵심입니다. 초보자가 흔히 범하는 ‘상태 시뮬레이션(dp[n][3])’ 접근법이 왜 복잡도 폭발을 일으키는지 논리적으로 분석하고, ‘마지막 행동’에 집중하여 문제를 선형(Linear)으로 단순화하는 과정을 다룹니다. VIP 좌석을 ‘분할 지점’으로 활용하는 실전 테크닉까지 완벽하게 정리했습니다.
“이걸 먼저 해야 저걸 할 수 있다?” 순서가 꼬인 코딩 테스트 문제, 위상정렬(Topological Sort)로 단번에 해결하세요! 난해한 개념을 게임 스킬 트리에 빗대어 쉽게 풀고, 필수 기출문제 백준 1005번(ACM Craft)의 완벽한 공략법을 다룹니다. 특히 복잡한 코드를 직관적으로 바꿔주는 ‘역방향 DFS’ 시크릿 팁까지 담았으니, 이 글 하나로 위상정렬을 확실하게 정복해 보세요.
이 문제, DP일까 그리디일까?” 헷갈리는 순간을 명쾌하게 정리해 드립니다. 코딩 테스트에 빈출 되는 5대 DP 유형(배낭 문제, LIS 등)을 완벽 해부하고, 문제를 보자마자 DP임을 알아채는 4가지 판별법을 공개합니다. 특히 그리디 알고리즘의 함정에 빠지지 않는 노하우와 IndexOutOfBounds 등 초보자가 자주 겪는 실수까지, 실전 점수를 올리는 비법을 확인하세요.
복잡한 문제는 작게 쪼개고, 정답은 기억해둔다!” 코딩 테스트의 난관 DP(다이나믹 프로그래밍)를 완벽하게 정복하는 가이드 1부입니다. DP의 핵심 원리인 메모이제이션(Memoization)을 시험 공부에 빗대어 쉽게 설명하고, 재귀를 쓰는 Top-Down과 반복문을 쓰는 Bottom-Up 구현 방식을 코드와 함께 비교합니다. 이 글을 통해 DP의 기초 개념과 구현의 뼈대를 확실하게 잡아보세요.