로그인회원가입
프로그래머스 DFS/BFS, DP 목록

2026.01.23. 17:27

✅ DFS/BFS Lv2 추천 (입문 → 응용)

0) 워밍업(DFS/BFS 감각 잡기)

  1. 타겟 넘버 (DFS 기초, 재귀/스택 감 익히기)

  2. 게임 맵 최단거리 (BFS=최단거리 공식 체득)

1) 상태공간 탐색(진짜 BFS/DFS 맛)

  1. 전력망을 둘로 나누기 (그래프 탐색 + 컴포넌트 크기)

  2. 석유 시추 (BFS/DFS + 영역 묶기 + 결과 누적)

  3. 무인도 여행 (맵에서 컴포넌트 합 구하기)

2) 백트래킹/완탐 DFS (Lv3 가기 전 필수)

  1. 피로도 (DFS 백트래킹 대표)

  2. 모음사전 (DFS/재귀식 생성)

  3. 메뉴 리뉴얼 (조합 DFS + 카운팅)

이 라인(6~8) 풀고 나면 Lv3 단어 변환/여행경로 같은 DFS 문제 훨씬 덜 아픔.

✅ DP Lv2 추천 (핵심 유형별)

A. 1차원 DP (기초)

  1. 멀리 뛰기 (피보나치 DP, mod 연산)

  2. 숫자 변환하기 (DP/BFS 사고 전환, “역방향”도 연습 가능)

B. 2차원 DP (Lv2 DP의 메인)

  1. 정수 삼각형 (정석 2D DP) * 이건 레벨 3임.

  2. 땅따먹기 (행 단위 DP, 전형적인 패턴)

C. 조금 더 생각해야 하는 DP (Lv3 입문체력)

  1. 가장 큰 정사각형 찾기 (dp[i][j] = min(좌,상,좌상)+1)

  2. 2 x n 타일링 또는 n x 2 타일링 (전형 타일 DP) * 3 x n 타일링도 있는데 점화식 찾기가 너무 어렵다.

  3. 등굣길 (격자 DP + 장애물 처리) *이것도 레벨 3임

목록