[Tip] 탐색의 개념과 유형

탐색이란?

• 특정 조건을 만족하는 상태를 찾기 위한 일련의 과정이다.

자료구조

대부분 BFS에서는 큐를 이용하고, DFS에서는 재귀함수를 이용한다.
(보통 대학과정에서 DFS에서 스택을 이용한다고 배우지만, 코딩테스트에서는 재귀함수를 이용하는 것이 좋다.)

어떤 유형으로 코딩테스트에 나오나요?

1. 구현에 초점
   • BFS/DFS, 백트래킹에 수 많은 조건
2. 알고리즘 지식
   • 알고리즘을 공부한 적이 있다면 이 정도는 구현할 줄 알아야지
   • 단순 BFS/DFS 뿐만 아니라 우선순위 큐와 같은 고급 알고리즘을 포함하여 출제

1. 구현에 초점

보통은 알고리즘 지식보다는 구현에 초점을 두는 문제가 잘 나온다.

1. 부분 상태 탐색 (위치 이동, 수)
   • 상태에 대한 체크 함수
2. 전체 상태 탐색 (전체 map)
   • N차원 배열을 조정하는 방법
3. 그 외
   • Flood Fill (묶여있는 그룹을 같은 색으로 칠하는 알고리즘)
   • 트리 순회

2. 알고리즘 지식

1. 위상정렬 (Topological Sort) - 나동빈님 알고리즘 강의 수강 추천
2. 최소신장트리 (MST)
3. 최단 거리

앞으로 “어떻게 BFS와 DFS를 파이썬에서 조금더 짧고 간결하게 사용할 수 있는지” 알아보도록 하자!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기