Class3

풀이 순서

---

1단계: 웜업 및 자료구조

• Hash, Set, Heap

  • 알고리즘을 본격적으로 풀기 전에, 데이터를 효율적으로 다루는 방법을 익히는 단계
  • 여기서는 시간 초과를 피하는 법을 배움

• 1620번 - 나는야 포켓몬 마스터 이다솜 ✅

  • 목표: 해시 맵(Dictionary)을 사용해 $O(1)$의 시간 복잡도로 데이터를 탐색하는 방법 숙지.

• 1764번 - 듣보잡 ✅

  • 목표: 셋(Set) 자료구조를 활용한 교집합 찾기.

• 11279번 - 최대 힙 / 1927번 - 최소 힙 ✅

  • 목표: 우선순위 큐(Priority Queue)의 개념 이해.
  • heapq 모듈을 사용하여 삽입/삭제를 $O(\log N)$에 처리하기.

---

2단계: 그래프 탐색의 기초

• DFS & BFS

  • Class 3의 가장 핵심적인 부분 / 반드시 완벽하게 이해하고 넘어가야 함

• 1260번 - DFS와 BFS ✅

  • 목표: 그래프 탐색의 교과서. 스택/재귀를 이용한 DFS와 큐를 이용한 BFS를 기본적으로 구현해 보기.

• 2606번 - 바이러스

  • 목표: 연결된 노드의 개수를 세는 문제. DFS나 BFS 중 편한 것으로 풀어보며 감 잡기.

• 2667번 - 단지번호붙이기 / 1012번 - 유기농 배추

  • 목표: 2차원 배열(Grid)에서의 탐색. 상하좌우를 탐색하며 그룹(컴포넌트)의 개수와 크기를 구하는 패턴 익히기.

---

3단계: BFS 심화

• 최단 거리 탐색

  • BFS가 왜 '최단 거리'를 보장하는지 깨닫게 되는 아주 중요한 단계

• 2178번 - 미로 탐색

  • 목표: 2차원 맵에서 시작점부터 도착점까지의 최단 칸 수 구하기. (BFS의 특징 활용)

• 1697번 - 숨바꼭질

  • 목표: 1차원 수직선 상에서의 BFS. 상태(State)를 노드로 생각하고 그래프 탐색을 적용하는 사고방식 전환.

• 7576번 - 토마토

  • 목표: '시작점이 여러 개'인 BFS. 큐에 시작점들을 미리 다 넣어두고 탐색을 시작하는 테크닉 배우기.

---

4단계: 동적 계획법

• DP

  • 기초점화식을 세우는 논리적 사고를 기르는 단계 / 작은 문제의 답으로 큰 문제의 답을 구함

• 1003번 - 피보나치 함수

  • 목표: 재귀호출의 중복을 확인하고, 배열에 값을 저장(Memoization)하여 $O(N)$으로 최적화하기.

• 1463번 - 1로 만들기

  • 목표: DP의 바이블. 브루트 포스나 그리디로 접근하면 왜 틀리는지 고민해 보고, 상향식(Bottom-up) DP로 풀어보기.

• 9095번 - 1, 2, 3 더하기

  • 목표: 경우의 수를 구하는 DP 점화식 세우기.

• 2579번 - 계단 오르기

  • 목표: '연속 3개 밟기 불가'와 같은 특정 제약 조건이 있을 때 상태를 어떻게 정의하고 점화식을 세우는지 연습.

---

5단계: 이분 탐색 및 매개변수 탐색

• Parametric Search

  • 탐색 범위가 어마어마하게 클 때(예: 10억 이상) 사용해야 하는 최적화 기법

• 1654번 - 랜선 자르기

  • 목표: "랜선의 길이가 $X$일 때, $N$개를 만들 수 있는가?"라는 결정 문제로 바꾸어 이분 탐색 적용하기.

• 2805번 - 나무 자르기

  • 목표: 랜선 자르기와 유사한 문제로, 매개변수 탐색을 확실하게 복습.

---

풀이 기록

3월

• 2026/03/16

  • 1620번 - 나는야 포켓몬 마스터 이다솜

• 2026/02/18

  • 1764번 - 듣보잡

• 2026/03/28

  • 11279번 - 최대 힙 / 1927번 - 최소 힙

• 2026/03/29

  1260번 - DFS와 BFS

---