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