기술사 - 알고리즘
· 8 min read
- 정보통신분야 기술사 훑어보기
- 정보통신분야 기술사 출제기준
- 기술사: IT경영
- 기술사: 융합 IT
- 기술사: 프로젝트관리
- 기술사: 소프트웨어 공학
- 기술사: 정보보안
- 기술사: 데이터베이스
- 기술사: 네트워크
- 기술사: 알고리즘
- 기술사: 에세이
알고리즘
트리
이진탐색트리
- Binary search
균형이진탐색트리
- AVL Tree: Adelson-Velskii-Landis Tree
- Balance Factor: = T의 왼쪽 서브트리 높이 - T의 오른쪽 서브트리의 높이
- BF(T)가
-1, 0, 1
중 하나를 만족해야함. - LL, LR, RR, RL 용어를 보기보단 그림을 보고 이해해야함.
- 최적화되어 탐색 시간 보장
m-원 탐색트리
- m-way Search Tree, Multiway Search Tree
B- 트리
B* 트리
- B애스터 트리
B+ 트리
- 모든 키의 값이 단말 노드에 순차 나열된다, 링크드 리스트로
Red Black 트리
T 트리
- AVL Tree + B tree
그래프
- Node: 정점, Edge: 간선
- 신장트리: Spanning Tree
- 그래프의 모든 정점과 일부 간선을 포함한 트리로 표현
최소 신장 트리
- Minimal Spanning Tree
- 가장 적은 비용/거리로 그래프의 모든 정점을 연결할 수 있는 구조
프림 알고리즘
- Prim
- 노드 기준
크루스칼 알고리즘
- Kruscal
- 엣지 기준
- 간선 최소 개수:
- 간선 최대 개수:
최단경로 문제
- Shortest Path
다익스트라
- Dijkstra
- 노드 수가 n이라면 n-1개의 목적지가 모두 확정될 때까지 반복
- 다익스트라를 노드마다 반복한게 프림 알고리즘
벨만포드
- 가중치가 음수일 경우, 불이익이 있는 경우 다익스트라 알고리즘으로 최단 경로가 계속 갱신되므로 이를 방어하기 위한 방법
정렬
선택 정렬
- Selection Sort
- 가장 작은 값을 순서대로 찾아내어 첫 번째 배열부터 채워나가며 정렬
버블 정렬
- Bubble Sort
- 왼쪽에서 오른쪽으로 비교해가며 오름차순으로 자리를 교환하여 정렬
합병 정렬
- Merge Sort
- 분할 정복
- 데이터 분포의 영향을 덜 받는다, 최악의 경우에도 효율적.
퀵 정렬
- Quick Sort
- 피봇을 정한다. 전체 값을 읽어 중간값이나 몇 개의 값의 평균을 피봇으로 정함.
- 프로그래밍 랭기지에서는 왼쪽에서 큰 값, 오른쪽에서 작은 값을 찾는 방식으로 구현.
삽입 정렬
- Insert Sort
- 추가적인 메모리를 안 씀: in-place sort
힙 정렬
- Heap Sort
Max Heap
Min Heap
Min-Max Heap
Deap
- 왼쪽은 Min Heap, 루트는 비어있음, 오른쪽은 Max Heap
- 왼쪽 서브트리의 임의 노드는 오른쪽 서브트리 같은 위치에 있는 노드와 대응된다.
기수 정렬
- Radix Sort
MSD
- Most Significant Digit
LSD
- Least Significant Digit