(구) 알고리즘 중급

(구) 알고리즘 중급 - Part 2/2

1. 다이나믹 프로그래밍 2

한 문제를 5가지 방법으로 접근해서 풀어보면서, 다이나믹 프로그래밍에 대한 이해를 높입니다.

그 다음, 다이나믹 프로그래밍 1에서 배운 문제보다 조금 더 어려운 문제를 풉니다.

2. 수학 2

수학 2는 알고리즘 보다는 다른 문제를 풀 때 필요한 경우가 많아서 배우는 부분입니다.

a^b 제곱 연산을 분할 정복 알고리즘을 이용해서 구하는 방법, 이진수의 원리를 이용해서 구하는 방법을 배웁니다.

그 다음은 행렬에 대한 내용을 간단히 짚고 넘어갑니다.

이제, 피보나치에 관심있는 사람들이 가장 재미있어하는 내용입니다. 바로 피보나치 수에 대해서 배웁니다. 피보나치 수를 구하는 다양한 방법, 피사노 주기, 피보나치 수의 다양한 성질, 피보나치 수를 행렬을 이용해서 구하는 방법을 배웁니다.

이제, 이항 계수를 배울 차례입니다. 이항 계수와 그 응용을 어떻게 하는 지 배웁니다. 여기에서 파스칼의 삼각형도 다루고 넘어갑니다.

카탈란 수에 대해서 들어본 적이 있나요? 이번 챕터에서 배울 수 있습니다!

오일러 피 함수가 무슨 함수인지 아나요? 이 내용도 이번 챕터에서 배울 수 있습니다.

두 수를 나눌 때, 나머지 연산을 어떻게 해야하는지 배우는 챕터가 바로 여기에 있습니다. 수학 1에서는 덧셈, 뺄셈, 곱셈에 대한 나머지 연산만 배우기 때문에, 나눗셈에서 나머지 연산을 하려면 이번 챕터를 꼭 들어야 합니다. 이 내용을 위해 확장 유클리드 알고리즘을 배웁니다.

3. 그래프 알고리즘 2

다양한 그래프 알고리즘을 배웁니다.

첫 번째로 배우는 그래프 알고리즘은 위상 정렬입니다. 위상 정렬 다음에는 최소 스패닝 트리 (MST)를 구하는 두 가지 방법인 프림과 크루스칼을 배웁니다.

우리가 어딘가로 이동할 때 사용하는 방법은 항상 최단 경로를 사용하는 방법입니다. 따라서, 최단 경로 알고리즘을 이번 챕터에서 배우게 됩니다.

첫 번째로 배우는 최단 경로 알고리즘은 벨만 포드 알고리즘이고, 두 번째로 배우는 알고리즘은 다익스트라 알고리즘, 마지막으로 배우는 알고리즘은 플로이드 와샬 알고리즘입니다. 세 알고리즘을 단순히 설명만 하는 것이 아니고, 구현도 하며, 응용하는 문제도 풀게 됩니다.

4. 트리 2

트리 2에서는 가장 가까운 공통 조상(LCA)에 대한 내용을 집중적으로 배웁니다.

직관적으로 구현하는 방법과 다이나믹 프로그래밍을 이용해서 구하는 방법을 배웁니다.

두 가지 방법을 배운 다음에는 임의의 두 정점 사이의 거리를 BFS 알고리즘보다 빠르게 구하는 방법에 대해서 배웁니다.

5. 완전 탐색 2

모든 경우를 다 해보지 않고, 정답이 될 수 있는 것만 다 해보는 일부 경우만 다 해보는 알고리즘, 완전 탐색 1에서 배운 BFS를 덱을 사용해서 하는 방법, 탐색의 규모가 너무 큰 경우에 문제의 크기를 절반으로 나누어서 푸는 중간에서 만나는 알고리즘 (Meet in the Middle) 알고리즘을 배웁니다

6. 구간의 최소값 구하기

구간의 최소값을 구하는 문제를 그냥 다 해보는 방법, 이차원 배열에 저장해서 구하는 방법, 루트 N으로 나눠서 구하는 방법 (sqrt decomposition), 다이나믹 프로그래밍을 이용해서 구하는 방법, 세그먼트 트리를 이용해서 구하는 방법으로 풀고 배웁니다.

마지막으로는 슬라이딩 윈도우 알고리즘을 배웁니다.

7. 구간의 합 구하기

구간의 합을 구하는 문제를 누적합을 이용해서 구하는 방법, 세그먼트 트리를 이용해서 구하는 방법, 펜윅 트리(바이너리 인덱스 트리)를 이용해서 구하는 방법으로 풀고 배워봅니다.

구간을 업데이트하는 경우에 사용하는 세그먼트 트리 나중에 업데이트 하기 (Segment Tree Lazy Propagation)도 여기서 배웁니다.

마지막으로, 다양한 문제를 세그먼트 트리나 BIT를 사용해서 풀어봅니다

포함되어 있는 문제

1. 다이나믹 프로그래밍 2

2. 수학 2

3. 그래프 알고리즘 2

4. 트리 2

5. 완전 탐색 2

6. 구간의 최소값 구하기

7. 구간의 합 구하기

01챕터: 다이나믹 프로그래밍 2

이동하기맛보기00:20:01

문제 풀기 100:16:32

문제 풀기 200:16:19

문제 풀기 300:20:20

문제 풀기 400:14:32

02챕터: 수학 2

수학 2-100:25:48

수학 2-200:04:27

03챕터: 그래프 2

DAG, 위상 정렬00:16:35

MST (프림, 크루스칼)00:15:44

최단거리 (벨만포드)00:12:35

최단거리 (다익스트라)00:16:15

최단거리 (플로이드)00:10:03

최단거리 (SPFA)00:02:37

04챕터: 완전 탐색 2

완전 탐색 200:17:15

05챕터: 트리 2

트리 200:18:21

06챕터: 구간의 최소값 구하기

루트 N으로 나누기, 다이나믹 프로그래밍00:12:57

세그먼트 트리00:08:06

슬라이딩 윈도우00:06:12

07챕터: 구간의 합 구하기

누적합00:10:50

세그먼트 트리00:16:25

펜윅 트리00:05:59

Problem Solving with Algorithms

(구) 알고리즘 중급 - Part 2/2