2016 SW 역량 테스트 대비
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. 알고리즘과 입/출력
- Hello World
- A+B
- A+B - 2
- A+B - 3
- A+B - 4
- A+B - 5
- A+B - 6
- A+B - 7
- A+B - 8
- 그대로 출력하기
- 그대로 출력하기 2
- 숫자의 합
- 열 개씩 끊어 출력하기
2. 완전 탐색 0
3. 완전 탐색 1
4. 완전 탐색 2
5. 다이나믹 프로그래밍 1
- 1로 만들기
- 2×n 타일링
- 2×n 타일링 2
- 1, 2, 3 더하기
- 붕어빵 판매하기
- 쉬운 계단 수
- 오르막 수
- 이친수
- 스티커
- 포도주 시식
- 가장 긴 증가하는 부분 수열
- 가장 큰 증가 부분 수열
- 가장 긴 감소하는 부분 수열
- 가장 긴 바이토닉 부분 수열
- 연속합
- 계단 오르기
- 제곱수의 합
- 타일 채우기
- 파도반 수열
- 합분해
- 암호코드
6. 다이나믹 프로그래밍 2
- 이동하기
- 점프
- 팰린드롬?
- 팰린드롬 분할
- 동전 1
- 동전 2
- 내리막 길
- 파일 합치기
- 행렬 곱셈 순서
- 구간 나누기
- 자두나무
- 고층 빌딩
- 타일 코드
- 기타리스트
- 1학년
- 올바른 괄호 문자열
- 같은 탑
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
