[Algorithm] 코딩 테스트 대비 알고리즘 정리 (1/2)

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 컨테이너