1. 알고리즘 기초 용어
ㅇ 알고리즘 (Algorithm) : 문제 해결을 위한 유한하고 명확한 절차
ㅇ 입력 (Input) : 알고리즘에 주어지는 데이터
ㅇ 출력 (Output) : 알고리즘 수행 결과로 얻는 데이터
ㅇ 연산 (Operation) : 알고리즘을 구성하는 기본 처리 단위
ㅇ 의사코드 (Pseudocode) : 알고리즘의 절차를 자연어와 기호로 표현한 것
ㅇ 순서도 (Flowchart) : 알고리즘의 처리 절차를 도형과 흐름으로 표현한 것
ㅇ 종료 조건 (Termination Condition) : 알고리즘의 수행을 끝내는 조건
ㅇ 정확성 (Correctness) : 모든 유효한 입력에 대해 올바른 결과를 내는 성질
2. 알고리즘 성능
ㅇ 시간 복잡도 (Time Complexity) : 입력 크기에 따른 알고리즘의 실행 시간 증가 정도
ㅇ 공간 복잡도 (Space Complexity) : 입력 크기에 따른 알고리즘의 메모리 사용량 증가 정도
ㅇ 점근적 표기법 (Asymptotic Notation) : 입력 크기가 커질 때 알고리즘의 성능을 표현하는 방법
ㅇ 빅오 표기법 (Big-O Notation) : 알고리즘의 최악 실행시간 증가율을 나타내는 표기법
3. 탐색,정렬 알고리즘
ㅇ 이진 탐색 (Binary Search) : 정렬된 자료를 절반씩 나누어 원하는 값을 찾는 방법
ㅇ 선형 탐색 (Linear Search) : 자료를 처음부터 순차적으로 검사하여 원하는 값을 찾는 방법
ㅇ 퀵 정렬 (Quick Sort) : 기준값을 중심으로 분할하여 정렬하는 분할 정복 알고리즘
ㅇ 병합 정렬 (Merge Sort) : 자료를 분할한 뒤 정렬하여 병합하는 분할 정복 알고리즘
ㅇ 힙 정렬 (Heap Sort) : 힙 자료구조를 이용하여 정렬하는 알고리즘
4. 그래프 알고리즘
ㅇ 경로 (Path) : 그래프에서 정점들을 연결하여 이루어진 순차적인 이동 경로
ㅇ 해밀토니안 경로 (Hamiltonian Path) : 모든 정점을 정확히 한 번씩 방문하는 경로
ㅇ 해밀토니안 사이클 (Hamiltonian Cycle) : 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 사이클
ㅇ 오일러 경로 (Eulerian Path) : 모든 간선을 정확히 한 번씩 지나는 경로
ㅇ 오일러 회로 (Eulerian Circuit) : 모든 간선을 정확히 한 번씩 지나 출발점으로 돌아오는 경로
ㅇ 최단 경로 (Shortest Path) : 두 정점 사이의 경로 중 비용 또는 거리가 가장 작은 경로
ㅇ 최소 신장 트리 (MST, Minimum Spanning Tree) : 모든 정점을 연결하면서 간선 가중치 합이 최소인 트리
ㅇ 외판원 문제 (TSP, Traveling Salesman Problem) : 모든 도시를 한 번씩 방문하는 최단 순회 경로를 찾는 문제
5. 상태,해 공간 및 탐색
ㅇ 상태 공간 (State Space) : 문제에서 가능한 모든 상태들의 집합
ㅇ 상태 공간 트리 (State Space Tree) : 문제의 상태 및 탐색 과정을 트리로 표현한 것
ㅇ 해 공간 (Solution Space) : 문제에서 가능한 모든 후보 해들의 집합
ㅇ 탐색 트리 (Search Tree) : 가능한 상태 또는 해를 노드로 표현한 탐색 구조
ㅇ 백트래킹 (Backtracking) : 해가 될 수 없는 경우 이전 상태로 되돌아가 탐색하는 방법
ㅇ 가지치기 (Pruning) : 해가 될 가능성이 없는 탐색 가지를 제거하는 기법
ㅇ 한정 분기법 (Branch and Bound) : 분기와 상한,하한을 이용하여 불필요한 탐색을 제거하는 방법
ㅇ A* 알고리즘 (A* Algorithm) : 실제 비용과 목표까지의 추정 비용을 이용해 최적 경로를 탐색하는 방법
6. 알고리즘 설계 기법
ㅇ 분할 정복 (Divide and Conquer) : 문제를 작은 부분 문제로 나누어 해결한 후 결합하는 방법
ㅇ 동적 계획법 (DP, Dynamic Programming) : 부분 문제의 해를 저장하여 중복 계산을 줄이는 방법
ㅇ 탐욕 알고리즘 (Greedy Algorithm) : 매 단계에서 가장 유리한 선택을 반복하는 알고리즘
ㅇ 완전 탐색 (Brute-Force Search) : 가능한 모든 경우를 직접 조사하여 해를 찾는 방법
ㅇ 휴리스틱 알고리즘 (Heuristic Algorithm) : 경험적 기준을 이용하여 빠르게 근사해를 찾는 방법