(구) 알고리즘 중급 - Part 1/2
(구) 알고리즘 중급 - Part 1/2
1. 그리디 알고리즘
그리디 알고리즘을 배웁니다.
많은 사람들이 착각하는 것이 그리디 알고리즘은 쉽다 입니다. 이 챕터에서는 그리디 알고리즘은 어렵지만 풀 수 있다를 배웁니다.
그리디 알고리즘은 증명이 중요하기 때문에, 일부 문제의 경우는 수업 시간에 증명을 합니다.
그리디 알고리즘을 잘하는 방법은 다이나믹 프로그래밍과 마찬가지로 다양한 문제를 푸는 것 입니다. 그리디 알고리즘 챕터도 약 10가지 문제를 통해서 연습을 하게 됩니다.
2. 분할 정복
분할 정복은 문제를 분할한 다음 합쳐서 문제를 푸는 알고리즘입니다.
대표적인 분할 정복 알고리즘인 이분 탐색 알고리즘을 배웁니다. 그 다음에는 대표적인 분할 정복 정렬 알고리즘인 머지 소트와 퀵 소트에 대한 내용을 배웁니다. 다양한 문제를 통해서 분할 정복 알고리즘을 연습합니다.
이 챕터에서 제일 재미있는 내용은 버블 소트에 대한 문제를 머지 소트를 이용해서 푼다는 것입니다.
마지막으로는 분할 정복 알고리즘의 하이라이트인 가장 가까운 두 점을 찾는 방법을 배웁니다.
3. 이분 탐색으로 정답 찾기
이분 탐색 알고리즘은 정렬된 리스트에 어떤 수가 있는지 없는지를 조사하는 알고리즘입니다.
이 원리를 이용해서 이분 탐색으로 문제를 풉니다.
주로, 정답을 구하기는 어려운데 정답을 검증하기 쉬운 경우에 이 알고리즘을 사용하게 됩니다.
4. 완전 탐색 0 (모든 경우 다 해보기 전에)
완전 탐색 1에 필요한 두 가지 내용을 먼저 다루는 부분입니다.
이번 챕터에서 비트마스크를 배우네요!
마지막으로 순열을 배웁니다.
다음 순열과 이전 순열, 그리고 모든 순열에 대해서 배우며, 순열의 순서에 대해서도 배웁니다.
5. 완전 탐색 1 (모든 경우 다 해보기)
여섯 가지의 다양한 알고리즘이 모여있는 챕터입니다.
먼저, 그냥 다 해보는 방법인 부르트 포스(Brute Force)에 대해서 배웁니다. 그 다음, N중 for문을 이용해서 문제를 푸는 방법을 배웁니다. N중 for문은 친구에게 자랑할 때 이외에는 쓸 일이 없기 때문에, 5분만에 다음 챕터로 넘어갑니다.
N개의 일이 있고, 그 일은 모두 해야합니다. 그런데, 순서를 바꿀 수 있습니다. 이런 경우에는 순열을 사용해서 모든 경우를 다 해봐야 합니다. 순열을 이용해서 모든 경우를 중복 없이 다 해보는 방법을 배웁니다.
네 번째로 배우는 알고리즘을 가장 중요한 알고리즘 중의 하나인 바로 BFS를 이용해서 모든 경우를 다 해보는 방법입니다.
다섯 번째로는 재귀 호출을 이용해서 백트래킹을 배우고, 여섯 번째로 비트마스크를 이용해서 모든 경우를 중복 없이 다 해보는 방법을 배웁니다.
6. 자료구조 2
자료구조 1에서 배웠던 스택을 조금 더 화려하게 사용해봅니다. 중요한 점은 여기에서도 계산기는 만들지 않는다는 것 입니다. 계산기, 후위 표기식은 강의에서 다루지 않습니다!
그 다음으로 배우는 자료구조는 그래프 알고리즘 중에서 크루스칼을 배울 때 필요한 Disjoint-set 입니다.
이제, 안 배운 자료구조가 뭐가 있을까요? 바로 힙입니다. 최대 힙과 최소 힙에 대해서 공부를 하고, 힙을 직접 구현해봅니다. 여기서 배우는 정렬 알고리즘이 힙 소트입니다.
마지막으로 배우는 내용은 이진 검색 트리 (BST) 입니다.
포함되어 있는 문제
1 - 그리디 알고리즘
2 - 분할 정복
3 - 이분 탐색으로 정답 찾기
4 - 완전 탐색 0
5 - 완전 탐색 1
6 - 자료구조 2
01챕터: 그리디 알고리즘
그리디 알고리즘 Part 1맛보기00:24:10
그리디 알고리즘 Part 200:37:48
02챕터: 분할 정복
분할 정복 Part 100:24:26
분할 정복 Part 200:27:07
03챕터: 이분 탐색으로 정답 찾기
이분 탐색으로 정답 찾기 Part 100:17:13
이분 탐색으로 정답 찾기 Part 200:13:06
04챕터: 완전 탐색 0
비트마스크00:15:50
순열00:11:07
05챕터: 완전 탐색 1
그냥 다 해보기, N중 for문00:16:54
순열 사용하기00:13:33
큐 사용하기00:23:04
재귀호출, 비트마스크00:21:31
06챕터: 자료구조 2
스택00:25:47
유니온 파인드00:07:42
힙00:08:12
이진 검색 트리00:12:22
