알고리즘 중급 - 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

그리디 알고리즘

그리디 알고리즘 Part 200:37:48

분할 정복

분할 정복 Part 100:24:26
분할 정복 Part 200:27:07

이분 탐색으로 정답 찾기

이분 탐색으로 정답 찾기 Part 100:17:13
이분 탐색으로 정답 찾기 Part 200:13:06

완전 탐색 0

비트마스크00:15:50
순열00:11:07

완전 탐색 1

그냥 다 해보기, N중 for문00:16:54
순열 사용하기00:13:33
큐 사용하기00:23:04
재귀호출, 비트마스크00:21:31

자료구조 2

스택00:25:47
유니온 파인드00:07:42
00:08:12
이진 검색 트리00:12:22

알고리즘 중급 - Part 1/2

  • 강사:최백준
  • 수강일:결제일로부터 30일
  • 가격:198,000원
  • 할인가:99,000원
  • 난이도:중급
  • 사용 언어C++, Java
  • 교재:
  • 총시간:4시간 59분 52초
참고자료
1 - 그리디.pdf
1 - 그리디 (필기).pdf
2 - 분할 정복.pdf
2 - 분할 정복 (필기).pdf
3 - 이분 탐색으로 정답 찾기.pdf
3 - 이분 탐색으로 정답 찾기 (필기).pdf
4 - 완전 탐색 0.pdf
4 - 완전 탐색 0 (필기).pdf
5 - 완전 탐색 1.pdf
5 - 완전 탐색 1 (필기).pdf
6 - 자료구조 2.pdf
6 - 자료구조 2 (필기).pdf
이전에 들으면 좋은 강의