코테 공부 [DFS/BFS]
DFS/BFS 이론 공부 및 기본 구조 구현
이재룡 Jun 30, 2025
[ 1. DFS / BFS ]
STACK (LIFO)
- DFS는 Stack 이용 [ 사실상 일반 리스트랑 동일 ]
DFS
- 시작 노드를 stack에 삽입하고 방문 처리 (visited[v] = true)
- 방문 하지 않은 인접노드를 stack에 넣는 과정을 끝까지 반복
⇒ 들어간 노드가 여러 개면 해당 인접 노드가 최고 깊이 까지 탐색이 완료된 이후의 순번 (LIFO)
QUEUE(FIFO)
- BFS는 queue 이용 [ 반드시 import deque ]
BFS
- 시작 노드를 queue에 삽입하고 방문 처리 (visited[v] = true)
- 방문 하지 않은 인접노드를 queue에 넣는 과정을 끝까지 반복
⇒ 들어간 노드가 여러 개면 해당 인접 노드가 다음 순번 (FIFO)
[ 2. 재귀함수 ]
factorial
- n이 1 이하인 경우 return 1
- 그렇지 않은 경우 return n* f(n-1)
유클리드 호제법 (GCD)
- 최대공약수 구하는 문제에서 (A>B)
- A를 B로 나눈 나머지가 R이면 GCD(A,B)는 GCD(B,R)
결과적으로 A%B = 0이면 return B
그렇지 않은 경우 GCD(B, A%B)
+ 추가로 두 수가 서로소 라면 최대 공약수 = 1
이는 결국 해당 코드에서 a%b가 1인 값이 도출되서 자동으로 해당 코드에서 b % 1 =0으로 자동 진행
