DFS – Ilway Dev

[DP] Tree DP (백준 2533)

2026. 01. 30.·Algorithm

백준 2533번 ‘사회망 서비스’ 문제를 통해 Tree DP의 핵심 원리를 분석합니다. 트리의 레벨별 접근이 실패하는 이유와 함께, ‘부모의 상태가 자식의 선택을 제약한다’는 관계성을 이용해 dp[node][state] 점화식을 유도하는 과정을 설명합니다. 특히 DFS의 후위 순회(Post-order)를 활용한 ‘방문-위임-결정’의 3단계 구현 공식을 제시하고, 이를 적용한 O(N) 자바 코드를 상세히 해설합니다.

[DP] DFS의 늪에서 3차원 DP로

2026. 01. 28.·Algorithm

백준 17070번 ‘파이프 옮기기 1’을 통해 격자 탐색 문제에서 DFS와 DP의 차이를 심층 분석합니다. N이 작을 때는 직관적인 DFS가 유효하지만, 입력 크기가 커질수록 발생하는 ‘중복 연산’의 한계를 지적합니다. 이를 극복하기 위해 (행, 열, 방향)을 상태로 갖는 3차원 DP 점화식을 설계하고 구현하는 과정을 보여주며, 문제 조건에 따라 최적의 알고리즘을 선택하는 기준을 제시합니다.