728x90
반응형

📌 관련 코테 풀이 모음집 (계속 업데이트 해보자고요)

 

📌 DFS가 유리한 경우 

  1. 재귀적인 특징과 백트래킹을 이용해 모든 경우를 하나씩 전부 탐색하는 경우 
  2. 그래프의 크기가 클 경우 
  3. 최적화된 답을 찾는 것이 아닐 경우 
  4. 경로의 특징을 저장해야 하는 경우 ex. 경로의 가중치

 

📌 BFS가 유리한 경우 

  1. 최단 거리 or 최단 횟수 구하는 경우 
  2. 최적화된 답을 찾는 경우 => BFS는 가장 처음 발견되는 해답이 최단 거리이다. 
  3. 탐색의 횟수를 구해야 하는 경우

 

⭐ 길찾기 문제 = DFS/BFS 단골 문제 
1. dx, dy, (dz)를 정의한다. (상하좌우 움직이는 거 계산 가능함) 
2. visited = [[0] * N for _ in range(N)] 방문한 곳은 체크표시한다. 
3. for문으로 nx, ny = x + dx[i], y + dy[i] 를 계산해 (1) 범위 내인지 (2) 방문 안한곳인지 체크하면 된다. 

 

 

📌 백트래킹

  • 기본적으로 완전 탐색 알고리즘이다. 
  • DFS나 BFS와 같은 방식으로 진행되지만, 진행 과정에서 답이 아닌 분기를 만나면 탐색을 진행하지 않고 돌아가 다른 분기로 감으로써 가지치기를 한다. 
  • => 결론: DFS, BFS 풀 때 if (): return 이럴 때가 백트래킹에 해당한다고 보면 됨. 

 

 

728x90
반응형
저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[알고리즘 전략] 완전탐색  (0) 2024.10.26
[알고리즘 전략] python 기본 자료구조 정리  (0) 2024.10.25
[알고리즘/Python] 힙(Heap)  (0) 2024.10.18
[알고리즘/Python] 스택(Stack) /큐(Queue)  (1) 2024.10.18
[알고리즘 전략] 탐욕법(Greedy)/ DP(동적 계획법)  (2) 2024.10.16

티스토리툴바