(구) 알고리즘 기초

1. 알고리즘과 입/출력

먼저 알고리즘이 무엇인지에 대해서 간략하게 배웁니다. 그 다음, 알고리즘을 공부하는 방법을 배웁니다.

알고리즘에서 가장 중요한 것은 시간이 얼마나 걸릴지 예측하는 능력이기 때문에, 시간 복잡도를 가장 첫 번재로 배웁니다.

알고리즘은 문제 풀이를 통해서 공부하는 것이 가장 효율적이기 때문에, 입/출력을 받는 방법을 배웁니다. 다양한 예제 문제 (A+B)를 통해서 다양한 입력 형식 (단일 입력, 테스트 케이스, EOF)을 처리하는 방법을 배웁니다.

2. 자료구조 1

알고리즘을 효율적으로 구현하기 위한 자료구조를 배웁니다.

첫 번째로 스택을 배웁니다. 스택이 무엇인지, 어떻게 구현하면 좋을 것인지를 배운 다음 스택을 여려가지 문제를 통해서 응용하게 됩니다. 다른 알고리즘 강의를 들으면 스택을 들은 다음 예제로 한 번 구현해보는 것은 계산기(후위표기식) 입니다. 이 강의에서는 후위 표기식을 이용한 계산기를 구현하지 않습니다. 이유는 직관적이지 않고, 스택보다 다른 구현에 더 많이 신경을 써야 합니다. 5가지 문제를 통해서 각 문제를 해결하는데 있어서 스택을 왜 사용해야 하고, 해결하기 위해 스택을 어떻게 활용하는지 배웁니다.

두 번째로 배우는 것은 큐입니다. 큐는 BFS나 완전 탐색같은 알고리즘을 구현하려면 필수적인 자료구조입니다. 큐는 스택과 다르게 간단하게 다루고 넘어갑니다. 2문제 정도를 풀게 됩니다.

세 번째로는 덱을 배웁니다. 덱은 덱이 무엇인지만 배우고 넘어갑니다.

마지막으로 배우는 것은 바로 문자열입니다. 아스키 코드가 무엇인지, 단어의 길이를 함수를 이용하지 않고 재는 방법, 문자열과 정수 사이의 변환을 배웁니다.

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

많은 사람들이 어려워 하는 다이나믹 프로그래밍을 쉽고 이해가기 쉽게 가르칩니다.

먼저, 이번 챕터에서는 다이나믹 프로그래밍이 뭔지를 배우게 되며, 약 20가지 문제 풀이를 통해서 다이나믹 프로그래밍을 연습합니다.

4. 수학 1

알고리즘을 공부하는데 왜 갑자기 수학이 필요할까요?

먼저, 알고리즘 대회나 이런 문제 풀이에서 중요한 것은 복잡한 프로그램은 구현 능력이 아니고 문제 해결 능력입니다. 당연히 복잡한 프로그램의 구현 능력도 중요합니다. 간단하고 정제되어있는 문제를 해결하지 못한다면, 복잡하고 정제되어 있지 않은 문제를 풀 수 있을까요? 따라서, 경우의 수가 매우 큰 경우에는 큰 정수의 구현 보다는 나머지 연산을 통해서 정답을 출력하라는 문제를 많이 만날 수 있습니다. 따라서, 첫 번째로 나머지 연산에 대해서 배웁니다.

그 다음은 최대 공약수와 최소 공배수에 대해서 배웁니다.

소수는 약수가 1과 자기자신 밖에 없는 수입니다. 소수는 암호학에서 매우 중요한 역할을 하고 있으며, 알고리즘에서도 소수가 매우 중요합니다. 따라서, 어떤 수가 소수인지 판별하는 방법과, 어떤 정수 범위 안에 들어있는 소수를 구하는 방법을 배웁니다.

마지막으로는 소인수분해를 하는 간단한 방법과 진법 변환, 그리고 팩토리얼에 대한 내용을 조금씩 배우고 넘어갑니다.

5. 정렬

정렬은 STL의 sort를 응용하는 방법을 배웁니다. O(N^2) 정렬 알고리즘은 다루지 않으며, 강의 때는 O(NlgN) 정렬 알고리즘만 다룹니다. 다양한 데이터를 정렬해야 하는 상황을 제시하며, 이럴 때는 sort의 비교 함수를 어떻게 작성해야 하는지를 배웁니다.

퀵 소트, 머지 소트, 힙 소트같은 유명한 소트 알고리즘은 다루지 않을까요? 아닙니다! 모두 다 강의 시간에 다룹니다. 퀵 소트와 머지 소트는 분할 정복 챕터에서, 힙 소트는 자료구조 2 챕터에서 배웁니다.

6. 그래프 1

그래프는 가장 자료구조 중의 하나입니다.

그래프가 뭔지, 그래프 용어에 대해서 배웁니다.

이제, 그래프가 무엇인지 알았기 때문에 그래프를 저장하는 방법 세 가지를 배웁니다. 그 세 가지는 바로 인접 행렬, 인접 리스트, 간선 리스트입니다.

세 가지 중에서 가장 중요하게 다루는 내용은 인접 리스트입니다. 인접 리스트를 사용하면 인접 행렬을 사용했을 때보다 시간과 공간이 더 효율적입니다. 효율적인 알고리즘 구현을 위해서 연결 리스트를 사용하지 않고 STL의 vector를 사용해서 인접 리스트를 구현하는 방법을 배웁니다.

그런데, 연결 리스트를 구현하기도 싫고, 사정상 STL을 사용할 수 없는 곳이라고요? 그런 분들을 위해 간선 리스트라는 자료구조도 준비했습니다. 간선 리스트는 그 어떤 책을 봐도 나오지 않는 신기한 자료구조입니다. 그런 분들을 위해 준비한 자료구조입니다.

이제, 그래프의 탐색에 대해서 배웁니다. 바로 DFS 알고리즘과 BFS 알고리즘입니다. 바로 전에 배운 자료구조 3가지를 이용해서 그래프를 탐색하는 방법을 배우면서 그래프를 저장하는 방법을 다시 한 번 복습하게 됩니다.

이제 DFS와 BFS를 응용할 차례입니다. 따라서, 연결 요소에 대한 내용을 배우고, 이분 그래프에 대한 내용을 배우게 됩니다.

그래프에서 가장 중요한 것은 일반 문제를 그래프로 모델링해서 푸는 것입니다.

그래프 모델링을 연습하기 위해서 사이클을 찾는 연습과 이차원 배열 상에서 플로드 필 알고리즘을 배웁니다.

7. 트리 1

그래프를 배웠으니 이제 트리를 배울 시간이지요!

트리의 용어에 대해서 배우고, 트리를 순회하는 방법인 프리 오더와 인 오더, 포스트 오더에 대해서 배웁니다.

그 다음에는 그래프와 마찬가지로 트리를 저장하는 방법 세 가지를 배웁니다.

트리를 저장하는 방법을 배웠으니 트리 문제를 통해서 트리 알고리즘을 연습할 시간이지요. 트리의 부모에 대한 내용과 트리의 지름에 대한 내용으로 트리를 복습합니다.

포함되어 있는 문제

1. 알고리즘과 입/출력

2. 자료구조 1

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

4. 수학 1

5. 정렬

6. 그래프 1

7. 트리 1

01챕터: 알고리즘과 입/출력

알고리즘과 입/출력맛보기00:25:25

02챕터: 자료구조 1

스택00:27:59

큐, 덱, 문자열00:12:16

03챕터: 다이나믹 프로그래밍 1

다이나믹 프로그래밍 100:19:39

문제 풀이 100:27:55

문제 풀이 200:27:59

문제 풀이 300:25:30

문제 풀이 400:17:10

04챕터: 수학 1

수학 100:36:34

05챕터: 정렬

정렬00:22:18

정렬 응용하기00:13:50

06챕터: 그래프 1

그래프00:10:47

그래프의 표현00:40:37

그래프 문제 풀이00:44:14

07챕터: 트리 1

트리00:11:37

트리의 순회00:24:55

Problem Solving with Algorithms

(구) 알고리즘 기초