1. 유클리드 호제법 (=GCD, 최대공약수)
- 최대공약수를 찾는 문제는 무조건 해당 알고리즘을 사용,
- 구현법에는, 1. 재귀함수의 사용, 2. while문 사용이 존재하는데,
개인적으로 2번이 더 쉬워보여서 2를 사용.
2. DFS (with Backtracking)
- 한 경로로 쭉 탐색하다가 특정 상황에서 다시 돌아가 다른 경로를 탐색하는 방식.
- 구현법에는, 1. 재귀함수의 사용, 2. Stack의 사용이 존재하는데,
1번을 일반적으로 많이 사용한다. - stack overflow가 발생할 수 있다는 단점이 존재.
하지만, 문제상황의 경우의 대부분은 무한루프에 빠졌을 경우에 속함. 백트래킹, 단절선 찾기, 단절점 찾기, 위상정렬, 사이클 찾기 등에 사용- 최단거리구하기와는 상성이 좋지 않다.
- 럭키 브루트포스로, 모든 경우를 다 방문해야하는 경우, 주로 사용됨.
- 방문한 노드들을 순서대로 기억해놓을 수 있다.
- DFS는 보통 visited라는 방문했는지를 파악하는 bool array를 추가로 둔다.
- 추가로, 보통 Array나 visited의 크기는, 하드코딩한다.
입력값의 최대값으로 설정해버리고 시작하는 것이 맘편하다.
DFS에 꼭 들어가야 할 6가지 요소
(순서는 상관이 없다)1. 목적지인가?
if_문을 사용
목적지라면, 재귀를 종료하도록 만듦2. 연결된 곳을 순회
for_문을 사용
갈 수 있는 가능성이 있는 모든 곳을 의미.
연결된 곳과 갈 수 있는 곳은 다르다.3. 갈 수 있는가?
if_문을 사용
연결된 곳 중에서, 갈 수 있는 곳 인지 확인한다.4. 갈 수 있으면 간다.
DFS를 호출함 (재귀함수)5. 체크인
가려고 하는 곳의 visited를 true로 만듦6. 체크아웃
갔다가 돌아오면 visited를 false로 만듦체크인과 체크아웃의 코드상의 깊이가 같아야만, 무한루프가 발생하지 않는다.
3. BFS
- 인접한 노드를 먼저 탐색하는 방식. 최단경로 문제와 상성이 좋음.
- 구현법에는, 다음경로들을 담아두기위해 Queue를 일반적으로 사용.
최단거리 구하기, 위상정렬등에 사용- 단점으로는 정답경로에서, 방문한 노드의 순서를 따로 기억할 수가 없다.
- BFS는 구현을 main 외부에 따로 할 필요가 없다. While문을 사용
- DFS와 같게, visited 배열을 선언해야하고, dist라는 최단거리배열을 추가로 선언한다.
BFS(=while문)에 꼭 들어가야 할 6가지 요소
(순서는 상관이 없다)1. Queue에서 꺼내옴
queue.pop()_을 사용
pop을 하면, 값이 사라지므로, queue.front()를 사용하여 미리 값을 담아두는 것이 필요2. 목적지인가? (굳이 사용하지 않아도 됨)
if_문을 사용
보통 최단거리를 구하는데, 목적지의 dist요소만 반환만하면 되기 때문.3. 연결된 곳을 순회
for_문을 사용4. 갈 수 있는가?
if_문을 사용5. 체크인
가려고 하는 곳의 visited를 true로 만듦6. Queue에다 넣음
queue.push()를 사용
Time Waits for No One