2016 SW 역량 테스트 대비

SW 역량 테스트에 주로 나오는 BFS/DFS/다이나믹 프로그래밍 관련 강의입니다.

1. 알고리즘과 입/출력

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

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

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

2. 완전 탐색 0 (모든 경우 다 해보기 전에)

완전 탐색 1에 필요한 두 가지 내용을 먼저 다루는 부분입니다.

이번 챕터에서 비트마스크를 배우네요!

마지막으로 순열을 배웁니다.

다음 순열과 이전 순열, 그리고 모든 순열에 대해서 배우며, 순열의 순서에 대해서도 배웁니다.

3. 완전 탐색 1 (모든 경우 다 해보기)

여섯 가지의 다양한 알고리즘이 모여있는 챕터입니다.

먼저, 그냥 다 해보는 방법인 부르트 포스(Brute Force)에 대해서 배웁니다. 그 다음, N중 for문을 이용해서 문제를 푸는 방법을 배웁니다. N중 for문은 친구에게 자랑할 때 이외에는 쓸 일이 없기 때문에, 5분만에 다음 챕터로 넘어갑니다.

N개의 일이 있고, 그 일은 모두 해야합니다. 그런데, 순서를 바꿀 수 있습니다. 이런 경우에는 순열을 사용해서 모든 경우를 다 해봐야 합니다. 순열을 이용해서 모든 경우를 중복 없이 다 해보는 방법을 배웁니다.

네 번째로 배우는 알고리즘을 가장 중요한 알고리즘 중의 하나인 바로 BFS를 이용해서 모든 경우를 다 해보는 방법입니다.

다섯 번째로는 재귀 호출을 이용해서 백트래킹을 배우고, 여섯 번째로 비트마스크를 이용해서 모든 경우를 중복 없이 다 해보는 방법을 배웁니다.

4. 완전 탐색 2

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

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

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

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

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

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

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

포함되어 있는 문제

1. 알고리즘과 입/출력

2. 완전 탐색 0

3. 완전 탐색 1

4. 완전 탐색 2

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

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

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

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

02챕터: 완전 탐색 0

비트마스크00:15:50

순열00:11:07

03챕터: 완전 탐색 1

그냥 다 해보기, N중 for문00:16:54

순열 사용하기00:13:33

큐 사용하기00:23:04

재귀호출, 비트마스크00:21:31

04챕터: 완전 탐색 2

완전 탐색 200:17:15

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

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

문제 풀이 100:27:55

문제 풀이 200:27:59

문제 풀이 300:25:30

문제 풀이 400:17:10

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

이동하기00:20:01

문제 풀기 100:16:32

문제 풀기 200:16:19

문제 풀기 300:20:20

문제 풀기 400:14:32

Problem Solving with Algorithms

2016 SW 역량 테스트 대비