대부분의 코테는 BFS/DFS + 재귀 만 잘해도 풀 수 있다.
BFS/DFS -> 탐색!
탐색: 특정 조건을 만족하는 상태를 찾기 위한 일련의 과정
그래프에서 사용되는 탐색 방법
BFS: 너비 우선 탐색
DFS: 깊이 우선 탐색
필요한 자료 구조는?
BFS: Queue
DFS: Recursion or Stack
어떤 유형으로 코테에 나오나?
1. 구현에 초점 ★★★
- BFS/DFS, 백트래킹에 수많은 조건
- (1) 부분 상태 탐색 (위치 이동, 수)
- 상태에 대한 체크 함수
- (2) 전체 상태 탐색 (전체 map)
- n차원 배열을 조정하는 방법
- (3) 그 외
- Flood Fill
- 트리 순회
- (1) 부분 상태 탐색 (위치 이동, 수)
2. 알고리즘 지식(대기업인 경우가 많음)
- 알고리즘을 공부한 적이 있다면 이정도는 구현할 줄 알아야지
- (1) 위상정렬 (Topological Sort)
- (2) 최소신장트리 (MST)
- (3) 최단 거리