U E D R , A S I H C RSS

알고하자/표준교육과정


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. 기초 자료구조

  • 스택


  • 선택정렬, 삽입정렬, 버블정렬

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

  • DP 입문

3.4. 그래프 1

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

3.5. 트리 1

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

3.6. 그래프 2

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

3.7. 트리 2


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

3.8. 완전 탐색 1

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

4. 실력

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

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

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 모델링

4.9. SCC & 2-SAT

  • 강한 연결 요소(SCC)
  • 단절점과 단절선
  • 2-SAT

4.10. 문자열과 기하

  • KMP 알고리즘
  • Trie
  • Aho-corasick
  • Suffix Array
  • CCW 알고리즘
  • Convex Hull(Graham Scan)
  • 라인 스위핑

5. 심화

  • 추가 예정

6. 기타

  • 위에 적힌 것 외에 필요하다고 생각되는 알고리즘을 아래에 적어봅시다.


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:22
Processing time 0.0510 sec