3일차 강의요약 (9강 ~ 12강)

9강 (BFS)

- 너비 우선 탐색

- pair이용 (좌표)

- BFS를 돌 때 큐에 쌓이는 순서는 반드시 거리 순

- 예외처리는 continue로 넘겨버리는 것이 깔끔 → 좀 더 직관적

- visited 배열을 별도로 관리하기보다 distance배열에 -1을 저장해둠으로써 관리가 용이해지고 공간을 절약할 수 있음

(거리와 방문 여부 동시 관리 가능)

 

- [응용1] 최단경로(거리측정)

- [응용2] 시작점이 여러개일 때

- [응용3] 시작점이 두 종류일 때

→ A의 전파가 B에 영향을 주고 B의 전파가 A에 영향을 주지 않는 경우(독립적인 상황)가 아니고

상호 영향을 주는 관계라면 어느 하나를 먼저 전파시키는 것이 불가능

이러한 경우에는, 시간 순으로 A와 B를 동시에 진행시켜야 함

- [응용4] 1차원에서의 BFS

 

+ 초기화시 적극적으로 활용하기

for(int i = 0; i < n; i++){
    fill(dist1[i], dist1[i]+m, -1);

}

 

+ 경우에 따라 공백이 없는 문자들의 graph 입력

ex)

A12B2

BB1B1

BC1B1 등은 string[]으로 줄 단위로 입력을 받은 뒤 string[][]을 이용해 관리할 수 있다.

 

10강 (DFS)

- 큐 대신 스택 사용

- 깊이 우선 탐색

- 방문 순서에 큰 차이

- 인접한 칸은 거리가 1만큼 더 떨어져 있다는 것은 DFS에서는 성립하지 않음

- 다차원 배열에서 굳이 BFS대신 DFS를 써야할 필요가 없음.

- Flood Fill은 어떤 것을 사용하든 무관하지만, 거리 측정은 BFS만 할 수 있기 때문

- DFS는 그래프와 트리에서 DFS를 사용함

 

11강 (재귀)

- 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

- 수학적 귀납법

1번 도미노가 쓰러진다.

k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다

- 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition)

- 모든 입력은 base condition으로 수렴해야 함

- 재귀함수가 자기 자신을 부를 떄 스택 영역에 계속 누적이 됨

→ 스택 메모리 용량이 제한된 환경에서는 반복문으로 해결해야함

- DP를 사용하기 어려운 상황에서 DP느낌이 난다면 분할정복 고려

귀납적인 사고가 핵심 (종료조건)

idea : base condition과 2k, 2k+1이 모두 잘 구해질 것이니 모든 수에 대해서 잘 구해질 것이다

- 2^k를 나타낼때는 1<<k 를 이용하여 간결하게 표현가능

- 함수를  쪼개서 생각하지 말고 귀납적으로 생각할 것

→ 1일 때 잘 동작, k일 때 잘 동작, k+1일 때 잘 동작

→ 모든 수에 대해서 잘 동작

- n = k일 때의 결과를 가지고 n = k+1일 때 써먹을 수 있음, 재귀적인 형태\

 

12강 (백트래킹)

- 재귀 이용, bool 이용

- n제한이 작음 (완탐이므로)

- 적절한 가지치기 중요

- 가지치기를 많이해서 시간복잡도 가늠이 어렵다면 가장 최악의 경우를 넣어서 시간초과를 판별

- 2차원 그래프에서 대각선끼리는 i+j ,i-j가 같다

- STL next_permutation 

→ C++에서 순열과 조합 문제를 해결할 때 유용