11월 코테 준비 기록| 코테 바짝 준비! 핵심 문제들 모음

출처: Gemini
dfs, bfs 추가문제

2D 격자(지도) 탐색 응용

• (10월 30일 목요일 풀이완료) 4963번: 섬의 개수 (실버 2)
  • 이유: 유기농 배추(1012)와 99% 똑같은 문제입니다. 유일한 차이점은 '상하좌우' 4방향이 아니라, '대각선까지 포함한 8방향'을 탐색해야 한다는 것입니다. 2D 탐색의 기본기를 다지기에 완벽한 문제입니다.
• (10월 30일 목요일 풀이완료)  2468번: 안전 영역 (실버 1)
  • 이유: '연결 요소 개수 세기(11724, 1012)'의 '종합 응용' 문제입니다.
  • "비가 1만큼 왔을 때의 안전 영역(그룹) 개수", "비가 2만큼 왔을 때의 개수"... 이렇게 비의 양 h를 for문으로 1부터 100까지 돌리면서, DFS/BFS를 총 100번 실행해보는 문제입니다. DFS/BFS 로직을 언제 실행시켜야 하는지 확실히 알게 해줍니다.

---

11월 6일! 실버 5.

 

11월 3일 월요일	11월 4일 화요일	11월 5일 수요일	11월 6일 목요일	11월 7일 금요일
푼 문제: 유형(번호, 난이도)			BFS(1697, 실버1)
나의 레벨			실버5 → 실버4

11월 10일 월요일	11월 11일 화요일
	DFS(10026, 골드5)
	실버4

BFS 최단 거리 응용

• [필수] 1697번: 숨바꼭질 (실버 1)
  • 이유: "미로 탐색"이 2D에서의 최단 거리였다면, 이 문제는 1D(수직선)에서의 최단 거리 문제입니다.
  • '상하좌우'로 움직이는 대신, x-1, x+1, 2*x라는 3가지 방식으로 움직입니다. BFS로 '최소 시간'을 구하는 가장 대표적인 문제이며, 코테에 정말 자주 나옵니다.

• [추천] 10026번: 적록색약 (골드 5)
  • 이유: 2D 격자 탐색(DFS/BFS)을 똑같은 로직으로 '두 번' 돌려보는 문제입니다.
  • (1) 일반인이 보는 지도(R, G, B)로 그룹 개수를 세고, (2) 적록색약이 보는 지도(R과 G를 같은 것으로 취급)로 그룹 개수를 셉니다. '방문 처리'(visited)를 어떻게 관리해야 하는지 감을 잡기 좋습니다.
• [도전] 7569번: 토마토 (골드 5)
  • 이유: 님이 푸신 7576번 토마토의 3D 버전입니다.
  • (x, y) 2차원이 아니라 (z, x, y) 3차원으로 바뀌었을 뿐, BFS 로직은 100% 동일합니다. 내가 BFS의 '상태'(queue에 넣는 값)를 정확히 이해했는지 확인하기 좋습니다.

 

---

1순위. 해시맵/자료구조 (Python의 dict, set)

목표: list로 돌리면 시간 초과 나는 문제를 dict를 써서 효율적으로 푸는 감을 익힙니다.

• [필수] 1620번: 나는야 포켓몬 마스터 이다솜 (실버 4)
  • 이유: dict를 왜 써야 하는지 가장 직관적으로 알려주는 문제입니다. "이름 -> 번호"와 "번호 -> 이름"을 모두 빠르게 찾아야 해서 dict를 두 개 만들면 편합니다.
• [필수] 10816번: 숫자 카드 2 (실버 4)
  • 이유: 특정 숫자가 몇 개 있는지 세는, 가장 전형적인 해시맵(카운팅) 문제입니다. Python의 Counter를 쓰면 한 줄에도 풀리지만, dict로 직접 세어보는 연습을 하세요.
• [추천] 1764번: 듣보잡 (실버 4)
  • 이유: "두 리스트에 공통으로 존재하는 요소 찾기" 문제입니다. set 자료구조의 교집합(&) 연산을 쓰면 매우 간단하게 풀 수 있습니다.

---

2순위. 구현 (시뮬레이션)

목표: 특별한 알고리즘 없이, 문제에서 시키는 복잡한 조건을 논리적으로 꼼꼼하게 코드로 옮기는 연습을 합니다.

• [필수] 14719번: 빗물 (골드 5)
  • 이유: '구현' 문제의 대표격입니다. "현재 위치를 기준으로 왼쪽에서 가장 높은 벽과, 오른쪽에서 가장 높은 벽을 찾아서" 물이 고이는 양을 계산하는 문제입니다. 논리만 잘 세우면 풀 수 있습니다.
• [추천] 2615번: 오목 (실버 1)
  • 이유: 2차원 배열을 8방향으로 탐색하며 "5알이 연속으로 놓였는지" 확인하는 전형적인 구현 문제입니다. DFS/BFS로도 풀 수 있지만, 단순 for문으로도 가능합니다.
• [추천] 14503번: 로봇 청소기 (골드 5)
  • 이유: (시간이 남는다면) '삼성 코테' 스타일의 전형적인 시뮬레이션입니다. 로봇의 이동과 방향 전환 규칙을 실수 없이 코드로 옮겨야 합니다.

---

3순위. 백트래킹 (DFS의 응용)

목표: DFS를 이용해 "모든 조합을 다 만들어보는" 방법을 배웁니다.

• [필수] "N과 M" 시리즈 (실버 3 ~ 실버 1)
  • 이유: 백트래킹의 '교과서'입니다. 이 시리즈 1번~4번만 풀어도 백트래킹의 기본 감을 잡을 수 있습니다.
  • 15649번: N과 M (1): (순열) 1~N 중 중복 없이 M개 고르기.
  • 15650번: N과 M (2): (조합) 1~N 중 중복 없이 오름차순으로 M개 고르기.
• [추천] 9663번: N-Queen (골드 4)
  • 이유: (N과 M이 익숙해졌다면) 백트래킹의 꽃입니다. 퀸을 놓을 수 있는지 체크하면서 DFS를 돌리는, 가장 유명한 백트래킹 문제입니다.

요약: 님이 지금 DFS/BFS를 풀고 계시니, 바로 "N과 M" 시리즈로 넘어가면 백트래킹까지 자연스럽게 연결됩니다. 그 후에 해시맵(1620번, 10816번) 문제를 풀어서 '시간 초과' 줄이는 감을 익히시는 것을 추천합니다.