Mlog

1. 해시

• 각각 데이터를 고유한 숫자 값으로 표현하여 데이터의 존재 여부를 확인하거나 또는 원본 데이터를 추출하는 과정
• 빠른 자료 탐색 ( O(1) )
• 충돌 시, 체이닝( 연결 리스트 뒤에 연결 )과 오픈 어드레싱( 테이블의 빈 곳을 찾아(선형, 제곱) 저장 )을 사용
• C++은 체이닝 사용 ( std::unordered_set, std::unordered_map 체이닝 사용 시 multi를 사용)

2. 그래프

• 한붓 그리기, 오일러 경로
• 인접 행렬( O(N^2) )과 인접 리스트( O(N+M) )를 통해서 프로그래밍 표현 ( N : 정점, M : 에지 )
• 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프일 경우, 리스트는 간선이 적은 희소 그래프일 경우 사용한다.
• 그래프 순회( DFS( 재귀함수, 스택 ), BFS( 큐 ) )
• DFS는 경로의 특징을 저장해둬야 하는 문제 BFS는 최단거리 구해야 하는 문제에 각각 유리하다.

3. 동적 계획법

• 복잡한 문제를 여러 개로 나눠서 해결하여 저장한 후, 그 값을 이용하여 전체 문제를 해결.
• 분할 정복법(ex.퀵 정렬)은 분할된 문제들이 겹치지 않지만 동적 계획법은 작은 문제가 큰 문제의 일부가 될 수 있다.
• 최적화 문제( 최적해를 구하여 전체 문제의 최적해를 구하는 경우 )와 카운팅 문제에 주로 사용한다.
• 메모이제이션(top-down) 방법과 타뷸레이션(bottom-up) 방법을 사용.
• 최소 비용 경로와 정수 삼각형 문제가 유명하다.
• 기저 위치와 탐색 범위를 조심하여 조건을 설정할 것

1. 재귀 알고리즘 

• 팩토리얼
• 피보나치 수
• 문자열 뒤집기
• 최대 공약수와 최대 공배수 ( <numeric>(c++17) gcd(), lcm() )
• 순열 ( <algorithm> next_permutation() )
• 하노이의 탑

2. 정렬 알고리즘

• 기본 (버블 정렬, 선택 정렬, 삽입 정렬)
• 분할 정복 (병합 정렬, 퀵 정렬(std::sort(), std::stable_sort()), 힙 정렬)

• std::sort() 사용법 : 연산자 오버로딩( operator< ), 내림차순( greater<T> ), 함수 객체( inline 가능 ), 람다식( [] ))

3. 탐색 알고리즘

• 선형 탐색 ( O(n) )
• 이진 탐색 ( O(logn), std::binary_search, 이미 정렬 되어있어야 함 )

4. 트리

• 이진 트리 ( 완전, 정, 포화, 균형, 편향 ) : 연결 리스트, 배열 ( 완전 이진 트리 구현에 사용(우선 순위 큐) )
• 트리 순회 ( 전위, 중위, 후위, 레벨 순서 )
• 이진 탐색 트리 ( O(logn), 크기 순서가 중위 순서, 중위 순회하면 오름차순, STL 연관 컨테이너(std::set, std::map) )

5. 힙과 우선 순위 큐

• 힙 ( 완전 이진 트리, 힙 속성에 따라 정의(최대, 최소) ) : 힙 정렬, 우선 순위 큐, 다익스트라 알고리즘

• 우선 순위 큐 ( 힙을 사용하는 것이 가장 효율적, <queue> std::priority_queue )

-. STL 컨테이너