Revision as of 02:50, 9 December 2016

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

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

C언어

프로그램 세상보기

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

형변환과 연산자

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

조건문과 반복문

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

함수와 전처리기

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

포인터와 배열

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

다차원 배열과 연결 리스트

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

문자열과 파일 입출력

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

C++

더하기로 넘어가기

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

STL 1

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

STL 2

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

클래스와 유용한 문법

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

기초

알고리즘 입문 & 수학 1

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

자료구조 1

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

다이나믹 프로그래밍 1

DP 입문

그래프 1

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

트리 1

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

그래프 알고리즘 2

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

트리 2

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

완전 탐색 1

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

실력

그리디 알고리즘 & 분할 정복

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

다이나믹 프로그래밍 2

DP 실력
비트마스크 DP

수학 2

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

완전 탐색 2

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

구간의 최소값 구하기(RMQ)

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

구간의 합 구하기

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

네트워크 플로우

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

최소 비용 유량(MCMF)

MCMF 이론
MCMF 모델링

심화

추가 예정

기타

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

알고하자

@@ Line 1: / Line 1: @@
 '''주의! 이 과정은 알고리즘에 특화되어 있습니다. 일반적인 교육과정과는 다를 수 있습니다.'''
 '''[[박인서]]가 개인적으로 필요하다고 생각되는 부분을 적은 것이므로 많은 피드백 바랍니다.'''
+* 권장 커리큘럼 : C언어 -> C++ & 기초 -> 실력 -> 심화
 __TOC__
@@ Line 95: / Line 96: @@
 * lambda expression
-= 자료구조 =
+= 기초 =
-== 알고리즘 기초와 수학 ==
+== 알고리즘 입문 & 수학 1 ==
-* 알고리즘의 정의
 * 시간 복잡도
-* 최대공약수/최소공배수(유클리드 호제법)
+* 입/출력(단일 입력, 여러개 입력, EOF)
+* 나머지 연산
+* 최대 공약수와 최소공배수
 * 소수 판별법
+* 진법 변환
 * 팩토리얼
-* 피보나치 수
+* 에라토스테네스의 체
+* a^b 구하기
-== 스택 & 큐, 정렬 & 탐색 ==
+== 자료구조 1 ==
 * 스택
 * 큐
 * 덱
-* 선택/삽입/버블 정렬
+* O(N^2) 정렬(선택정렬, 삽입정렬, 버블정렬)
-* 퀵/머지 정렬
-* Binary Search
-== 그래프 & 트리 ==
+== 다이나믹 프로그래밍 1 ==
-* 그래프(정의, 용어)
+* DP 입문
-* 인접 행렬과 인접 리스트
-* 트리(정의, 순회)
-* 트리 저장법(직접 구현, 배열 이용)
-* 힙(정의, 정렬)
-= 기초 알고리즘 =
+== 그래프 1 ==
-== 탐색 ==
+* 그래프 용어
-* Brute force
+* 그래프 저장 방식(직접 구현, 인접 행렬, 인접 리스트)
-* BFS
+* 그래프의 탐색(DFS, BFS)
-* DFS
+* 연결 요소
-* 백트래킹
+* 이분 그래프
+* Cycle 찾기
+* Flood-Fill 알고리즘
-== 분할 정복 & 그리디 알고리즘 ==
+== 트리 1 ==
-* 이분 탐색 알고리즘
+* 트리 용어
-* Parametric Search(Bisection)
+* 트리 순회(preorder, inorder, postorder)
-* 그리디 알고리즘
+* 트리 저장 방식(직접 구현, 부모를 저장, 자식을 저장)
+* 트리 너비와 높이
-== 다이나믹 프로그래밍 1 ==
+== 그래프 알고리즘 2 ==
-* 다이나믹 개념
+* 위상 정렬
-* 부분 집합
+* 최소 스패닝 트리(프림, 크루스칼)
-* 업 시퀀스
+* 최단 경로(다익스트라, 플로이드 와샬, 벨만 포드)
-* knapsack
-== 트리 응용 1  ==
+== 트리 2 ==
-* 트리 응용(트리의 부모, 트리의 폭)
+* Disjoint-set(Union-Find)
+* 힙
+* 힙정렬
 * 이진 검색 트리(BST)
-* 가장 가까운 공통 조상(LCA)
+* 가장 가까운 공통 조상 - LCA(직접 구현, DP 이용)
+== 완전 탐색 1 ==
+* 비트 마스크
+* 순열
+* 부르트 포스(N중 For문, 순열, BFS, 백트래킹, 비트마스크)
-== 그래프 알고리즘 ==
+= 실력 =
-* 최소 스패닝 트리(위상 정렬, 프림/크루스칼)
+== 그리디 알고리즘 & 분할 정복 ==
-* 최단 경로(다익스트라, 플로이드 와샬)
+* 그리디 입문
-* Flood Fill 알고리즘
+* 분할 정복
+* 이분 탐색 알고리즘
+* O(NlogN) 정렬(퀵정렬, 병합정렬)
+* 이분 탐색으로 정답 찾기
-= 심화 알고리즘 =
 == 다이나믹 프로그래밍 2 ==
-* 추가 예정
+* DP 실력
+* 비트마스크 DP
+== 수학 2 ==
+* a^b 분할 정복 이용
+* a^b 이진수의 원리 이용
+* 피사노 주기
+* 피보나치 수의 다양한 성질
+* 피보나치 수를 행렬을 이용해 계산
+* 이항 계수
+* 파스칼의 삼각형
+* 카탈란 수
+* 오일러 피 함수
+* 확장 뉴클리드 알고리즘
+== 완전 탐색 2 ==
+* 일부 경우만 다 해보는 알고리즘
+* BFS를 덱을 사용해서 하는 방법
+* 중간에서 만나는 알고리즘 (Meet in the Middle)
-== 트리 응용 2 ==
+== 구간의 최소값 구하기(RMQ) ==
-* 세그먼트 트리
+* 그냥 다 해보는 방법
-* 바이너리 인덱스 트리
+* 이차원 배열에 이용
-* Trie
+* 루트 N으로 나눔(sqrt decomposition)
+* 다이나믹 프로그래밍을 이용해서 구하는 방법
+* 세그먼트 트리를 이용해서 구하는 방법
+* 슬라이딩 윈도우 알고리즘
-== 기하 알고리즘 ==
+== 구간의 합 구하기 ==
-* 플레인 스위핑
+* 누적합을 이용
-* Convex Hull(Graham Scan)
+* 세그먼트 트리를 이용
+* 펜윅 트리(바이너리 인덱스 트리)를 이용
+* 세그먼트 트리 나중에 업데이트 하기 (Segment Tree Lazy Propagation)
+* 분할 정복에 활용
+* K번째를 찾는 방법
 == 네트워크 플로우 ==
-* 이론(최대 유량, 이분 매칭, 민 컷)
+* 네트워크 이론(이분 매칭, 민 컷, 최소 버텍스 커버, 최대 독립 집합)
-* 최소 비용 유량(MCMF)
+* 최대 유량(Ford-Fulkerson, Edmond-Karp)
+* 네트워크 모델링 연습
-== SCC ==
+== 최소 비용 유량(MCMF) ==
-* 연결 요소
+* MCMF 이론
-* SCC(단절점, 단절선)
+* MCMF 모델링
-== 2-SAT ==
+= 심화 =
-* 이분 그래프
+* 추가 예정
-* Disjoint-set
-* 2-SAT
 = 기타 =