알고하자/표준교육과정 (rev. 1.10)

알고하자/표준교육과정

주의! 이 과정은 알고리즘에 특화되어 있습니다. 일반적인 교육과정과는 다를 수 있습니다.
박인서가 개인적으로 필요하다고 생각되는 부분을 적은 것이므로 많은 피드백 바랍니다.

권장 커리큘럼 : C언어 -> C++ & 기초 -> 실력 -> 심화

Contents

1.1. 프로그램 세상보기
1.2. 형변환과 연산자
1.3. 조건문과 반복문
1.4. 함수와 전처리기
1.5. 포인터와 배열
1.6. 다차원 배열과 연결 리스트
1.7. 문자열과 파일 입출력

2.1. 더하기로 넘어가기
2.2. STL 1
2.3. STL 2
2.4. 클래스와 유용한 문법

3.1. 알고리즘 입문 & 수학 1
3.2. 자료구조 1
3.3. 다이나믹 프로그래밍 1
3.4. 그래프 1
3.5. 트리 1
3.6. 그래프 알고리즘 2
3.7. 트리 2
3.8. 완전 탐색 1

4.1. 그리디 알고리즘 & 분할 정복
4.2. 다이나믹 프로그래밍 2
4.3. 수학 2
4.4. 완전 탐색 2
4.5. 구간의 최소값 구하기(RMQ)
4.6. 구간의 합 구하기
4.7. 네트워크 플로우
4.8. 최소 비용 유량(MCMF)

1. C언어 ¶

1.1. 프로그램 세상보기 ¶

ZeroWiki 작성법
Hello, World! 프로그램 작성
기본적인 C 프로그램 구조
입출력과 주석
변수와 자료형
ASCII 코드

1.2. 형변환과 연산자 ¶

진법 표현
형변환
키워드와 식별자
연산자의 종류
연산자 우선 순위

1.3. 조건문과 반복문 ¶

if ~ else 와 else if
switch
배열 기초
for문
while 과 do while
break와 continue

1.4. 함수와 전처리기 ¶

함수란?
함수 정의하기
변수의 범위
main 함수에 파라미터 전달하기
재귀함수
전처리기

1.5. 포인터와 배열 ¶

포인터
메모리 주소
& 연산자
포인터 변수와 자료형
Call by value와 Call by reference
배열 다시 보기
배열과 포인터

1.6. 다차원 배열과 연결 리스트 ¶

구조체
다차원 배열
행렬
malloc과 free
linked list

1.7. 문자열과 파일 입출력 ¶

문자열이란?
문자열의 선언
문자열 함수
문자와 정수의 변환
파일 입출력 선언
파일 입출력

2. C++ ¶

2.1. 더하기로 넘어가기 ¶

헤더와 include 개념 잡기
std::cin, std::cout, std::endl
참조 형식과 값 형식
함수 오버로딩
디폴트 파라미터
동적할당 new, delete, delete[]

2.2. STL 1 ¶

pair
vector, deque
set, map
stack, queue, priority_queue
string

2.3. STL 2 ¶

reverse, swap
sort/stable_sort
binary_search
lower_bound/upper_bound
min/max
min_element/max_element

2.4. 클래스와 유용한 문법 ¶

클래스와 구조체
클래스와 인스턴스
클래스 정의 문법
public과 private
auto
range-based for loop
initalizer-list
lambda expression

3. 기초 ¶

3.1. 알고리즘 입문 & 수학 1 ¶

시간 복잡도
입/출력(단일 입력, 여러개 입력, EOF)
나머지 연산
최대 공약수와 최소공배수
소수 판별법
진법 변환
팩토리얼
에라토스테네스의 체
a^b 구하기

3.2. 자료구조 1 ¶

스택
큐
덱
O(N^2) 정렬(선택정렬, 삽입정렬, 버블정렬)

3.3. 다이나믹 프로그래밍 1 ¶

DP 입문

3.4. 그래프 1 ¶

그래프 용어
그래프 저장 방식(직접 구현, 인접 행렬, 인접 리스트)
그래프의 탐색(DFS, BFS)
연결 요소
이분 그래프
Cycle 찾기
Flood-Fill 알고리즘

3.5. 트리 1 ¶

트리 용어
트리 순회(preorder, inorder, postorder)
트리 저장 방식(직접 구현, 부모를 저장, 자식을 저장)
트리 너비와 높이

3.6. 그래프 알고리즘 2 ¶

위상 정렬
최소 스패닝 트리(프림, 크루스칼)
최단 경로(다익스트라, 플로이드 와샬, 벨만 포드)

3.7. 트리 2 ¶

Disjoint-set(Union-Find)
힙
힙정렬
이진 검색 트리(BST)
가장 가까운 공통 조상 - LCA(직접 구현, DP 이용)

3.8. 완전 탐색 1 ¶

비트 마스크
순열
부르트 포스(N중 For문, 순열, BFS, 백트래킹, 비트마스크)

4. 실력 ¶

4.1. 그리디 알고리즘 & 분할 정복 ¶

그리디 입문
분할 정복
이분 탐색 알고리즘
O(NlogN) 정렬(퀵정렬, 병합정렬)
이분 탐색으로 정답 찾기

4.2. 다이나믹 프로그래밍 2 ¶

DP 실력
비트마스크 DP

4.3. 수학 2 ¶

a^b 분할 정복 이용
a^b 이진수의 원리 이용
피사노 주기
피보나치 수의 다양한 성질
피보나치 수를 행렬을 이용해 계산
이항 계수
파스칼의 삼각형
카탈란 수
오일러 피 함수
확장 뉴클리드 알고리즘

4.4. 완전 탐색 2 ¶

일부 경우만 다 해보는 알고리즘
BFS를 덱을 사용해서 하는 방법
중간에서 만나는 알고리즘 (Meet in the Middle)

4.5. 구간의 최소값 구하기(RMQ) ¶

그냥 다 해보는 방법
이차원 배열에 이용
루트 N으로 나눔(sqrt decomposition)
다이나믹 프로그래밍을 이용해서 구하는 방법
세그먼트 트리를 이용해서 구하는 방법
슬라이딩 윈도우 알고리즘

4.6. 구간의 합 구하기 ¶

누적합을 이용
세그먼트 트리를 이용
펜윅 트리(바이너리 인덱스 트리)를 이용
세그먼트 트리 나중에 업데이트 하기 (Segment Tree Lazy Propagation)
세그먼트 트리의 활용(분할 정복에 활용, K번째를 찾는 방법)

4.7. 네트워크 플로우 ¶

네트워크 이론(이분 매칭, 민 컷, 최소 버텍스 커버, 최대 독립 집합)
최대 유량(Ford-Fulkerson, Edmond-Karp)
네트워크 모델링 연습

4.8. 최소 비용 유량(MCMF) ¶

MCMF 이론
MCMF 모델링

5. 심화 ¶

추가 예정

6. 기타 ¶

위에 적힌 것 외에 필요하다고 생각되는 알고리즘을 아래에 적어봅시다.
Dynamic Programming 2에 어떤 것을 채워야 될 지 모르겠군요.

last modified 2021-02-07 05:30:22
Processing time 0.0697 sec