2019년 1/2월 알고리즘 커리큘럼

1. 알고리즘

알고리즘이 무엇인지, 알고리즘 공부를 왜 하는지, 알고리즘 문제를 푸는 목적이 무엇인지에 대해서 배워봅니다.

여러가지 알고리즘 예시 문제를 통해 알고리즘 문제에 대한 내용을 살펴봅니다.

개발을 하다가 만날 수 있는 상황이 어떻게 알고리즘 문제로 변형이 되는지도 알아봅니다.

어떤 기준을 가지고 알고리즘을 평가해야하는지 알아봅니다. (시간 복잡도, 공간 복잡도)

2. 자료구조 1

스택, 큐, 덱, 문자열에 대해서 알아봅니다.

주로 스택에 대해서 배우게 되며, 큐와 덱은 이후의 BFS 챕터에서 다시 알아봅니다.

스택의 LIFO 성질을 어떻게 문제에 적용할 수 있는지 알아봅니다.

스택은 문제의 난이도에 따라서 두 부분으로 나누어져 있으며, 어려운 부분은 이후 "자료구조 2"에서 등장합니다.

큐와 덱은 개념에 대해서만 알아봅니다.

3. 수학 1

나머지 연산, 최대 공약수, 최소 공배수, 진법 변환, 소수, 팩토리얼에 대해서 알아봅니다.

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

다이나믹 프로그래밍에 대한 개념을 알아봅니다.

비슷한 문제를 묶어 놓은 여러가지 연습 문제를 이용해서 다이나믹 점화식을 만드는 방법을 연습합니다.

5. 브루트 포스

브루트 포스는 모든 경우의 수를 다 시도해보는 알고리즘입니다. 총 7개의 부분으로 나누어져 있습니다.

5-1. 브루트 포스 (기초)

단순 반복문을 이용해서 모든 경우의 수를 시도해보는 문제로 브루트 포스 알고리즘을 알아봅니다.

5-2. 브루트 포스 (순열)

순열을 이용해서 모든 경우의 수를 시도해보는 문제로 브루트 포스 알고리즘을 알아봅니다.

5-3. 브루트 포스 (N과 M)

재귀를 사용하는 브루트 포스를 알아보기 전에 N과 M문제를 이용해서 먼저 재귀 함수 연습을 합니다.

5-4. 브루트 포스 (재귀)

재귀 함수를 사용해서 모든 경우의 수를 만들어보는 연습을 합니다.

5-5. 브루트 포스 (비트마스크)

비트마스크를 이용해 모든 경우의 수를 만들어보는 방법을 알아봅니다.

5-6. 브루트 포스 (기타)

기타 여러가지 브루트 포스 방법 또는 그와 비슷한 방법을 알아봅니다.

5-7. 브루트 포스 (문제)

여러가지 브루트 포스 문제를 보면서, 어떤 방법으로 구현을 해야 하는지 알아봅니다.

6. 그래프 1

그래프에 대한 이론, 용어를 알아보고, 그래프를 저장하는 방법(인접 행렬, 인접 리스트, 간선 리스트)을 알아봅니다.

가장 중요한 그래프 알고리즘 DFS와 BFS를 알아봅니다

그 뒤, DFS, BFS를 응용해서 연결 요소, 이분 그래프를 알아보고, 플러드 필 알고리즘을 알아봅니다

7. BFS 1

문제의 상황을 그래프로 표현해보고, 왜 BFS로 해결할 수 있는 문제인지 알아봅니다.

8. 트리 1

트리의 용어와 저장하는 방법을 배웁니다.

트리 순회 방법(프리오더, 인오더, 포스트오더), 트리의 부모에 대한 내용, 트리의 지름을 구해봅니다.

9. 그리디 알고리즘

그리디 알고리즘을 문제와 함께 알아봅니다. 일부 문제는 증명도 합니다.

10. 문자열 알고리즘 1

문자열 매칭 알고리즘 KMP, Trie, Aho-Corasick에 대해서 알아봅니다.

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

다이나믹 프로그래밍 1에서 풀어본 문제보다 조금 더 어려운 난이도의 다이나믹 프로그래밍 문제를 풀어봅니다.

12. 분할 정복

이분 탐색, 머지 소트, 퀵 소트와 기타 분할 정복으로 풀 수 있는 문제를 풀어봅니다.

13. 시뮬레이션

문제의 상황을 그대로 구현하면 되는 시뮬레이션 알고리즘을 풀어봅니다. 큰 내용은 없으나, 코딩이 어려운 경우가 많아 중간에 배치한 챕터입니다.

14. 이분 탐색으로 정답 찾기

이분 탐색을 이용해 가능한 정답의 범위를 좁혀가면서 정답을 찾는 알고리즘에 대해서 알아봅니다.

15. 자료구조 2

자료구조 1에서 다룬 스택보다 조금 더 난이도 있는 스택의 응용을 해봅니다.

유니온 파인드, 힙, 이진 검색 트리(BST)에 대해서 알아봅니다.

16. BFS 2

BFS 1에서 다룬 문제보다 조금 더 심화된 문제를 풀어봅니다. 자료구조 2에서 배운 자료구조를 응용해보기도 합니다.

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

다이나믹 프로그래밍 2에서 풀어본 문제보다 조금 더 어려운 난이도의 문제를 풀어봅니다.

18. 그래프 2

위상 정렬, MST(프림, 크루스칼), 벨만 포드, 다익스트라, 플로이드, SPFA 알고리즘을 알아봅니다.

19. 그래프 2 - 문제

그래프 2에서 배운 알고리즘을 이용해 문제를 해결해봅니다.

20. 다이나믹 프로그래밍 4

비트마스크를 이용한 상태 다이나믹을 배워봅니다.

21. 트리 2

LCA에 대해서 알아봅니다.

22. 구간의 최소값 쿼리

세그먼트 트리, BIT에 대해서 알아봅니다.

23. 기타

분류하기 애매한 문제들을 모아놨습니다.

도움이 되었습니까?
0명 중 0명이 도움이 되었다고 했습니다.
또 다른 질문이 있으십니까? 문의 등록

댓글

댓글을 남기려면 로그인하세요.