1. 그래프
1. 너비 우선 탐색
•
시작 정점에 인접한 정점을 모두 차례로 방문 → 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문
•
가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법
•
인접한 정점에 대해 차례대로 다시 너비 우선 탐색을 반복 → Queue 자료구조 사용
알고리즘 동작 방식
1.
시작 노드를 큐에 삽입
2.
큐에서 노드를 하나씩 꺼내기 → 해당 노드의 인접 노드를 큐에 삽입
3.
큐가 빌 때까지 반복
2. 깊이 우선 탐색
•
시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
•
더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와
다른 방향의 간선으로 탐색을 계속해 모든 정점을 방문하는 방법
•
Stack 자료구조 사용 
재귀함수로 구현
재귀함수로 구현알고리즘 동작 방식
1.
시작 노드를 스택에 삽입
2.
스택에서 노드를 하나씩 꺼내기 → 해당 노드의 인접 노드를 스택에 삽입
3.
스택이 빌 때까지 반복
3. 다익스트라 알고리즘
가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘
너비우선탐색(BFS)과 유사한 형태를 갖는 알고리즘이지만, 가중치가 있기 때문에 Queue 자료구조를 그대로 사용하는 것이 아닌, 우선순위 큐 를 사용
알고리즘 동작 방식
1.
시작 노드의 거리를 0으로 설정 + 나머지 노드의 거리를 무한대로 설정
2.
시작 노드를 우선순위 큐에 넣기
3.
우선순위 큐에서 노드를 하나씩 꺼내면서, 해당 노드의 인접 노드 거리를 갱신
a.
우선순위 큐는, 현재까지 발견된 가장 짧은 간선 거리에 따라 정렬 수행
4.
우선순위 큐가 빌 때까지 반복
결과
시작 노드로부터 각 노드까지의 최단 거리가 계산됨
2. 트리
1. 프림 알고리즘
최소 신장 트리를 찾는 알고리즘 중 하나
모든 노드가 연결된 상태에서, 최소 비용으로 모든 노드를 연결하는 경로를 찾음
우선순위 큐 를 이용한 최소힙으로 구현
핵심
•
트리 집합을 단계적으로 확장하는 것
•
새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가
알고리즘 동작 방식
1.
임의 노드를 선택해서 시작
2.
선택 노드와 연결된 간선 중에서 최소 비용 간선을 선택
3.
선택 간선의 끝 노드를 추가 → 해당 노드와 연결된 간선 중 최소 비용 간선 선택
4.
모든 노드가 연결될 때까지 반복
2. 크루스칼 알고리즘
최소 신장 트리를 찾는 알고리즘 중 하나
간선을 하나씩 선택하여 최소 비용의 간선을 추가하는 방식
핵심
•
모든 간선을 가중치 기준으로 오름차순으로 정렬
•
간선들을 순서대로 모든 정점이 연결될 때까지 연결
알고리즘 동작 방식
1.
모든 간선을 비용 순으로 정렬(오름차순)
2.
최소 비용 간선 선택하여 추가 → 정점들을 연결
a.
정점 연결에 Union-find 알고리즘 사용
Union-find 알고리즘에 대해서…
대표적인 그래프 알고리즘
1. 정점 연결 및 사이클 형성 여부 확인하는 데에 사용되는 알고리즘
2. Disjoint-Set : 서로소 집합 알고리즘 : 여러 개의 노드가 존재할때, 두 개의 노드를 택해서 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
3.
추가한 간선이 사이클을 형성하지 않으면, 최소 신장 트리에 추가
4.
모든 노드가 연결될 때까지 반복
3. 허프만 알고리즘
데이터 압축을 위해 사용하는 알고리즘
자주 사용되는 문자는 짧은 코드로,
덜 사용되는 문자는 긴 코드로 변환하여 전체 데이터의 크기를 줄이는 방식
알고리즘 동작 방식
•
빈도 분석
◦
입력 데이터에서 각 문자의 빈도를 계산
•
우선순위 큐 초기화
◦
각 문자를 빈도와 함께 우선순위 큐에 노드로 삽입 : 빈도가 낮은 순서대로 정렬
•
트리 구축
◦
우선순위 큐에서 빈도가 가장 낮은 두 노드를 꺼내어 하나의 부모 노드로 결합
▪
부모 노드의 빈도는 두 자식 노드의 빈도의 합
◦
새로 생성된 부모 노드를 다시 우선순위 큐에 삽입
◦
우선순위 큐에 노드가 하나만 남을 때까지 반복
▪
마지막 하나 남은 노드(문자)는, 허프만 트리의 루트노드
•
코드 생성
◦
트리의 루트에서 각 문자까지의 경로를 따라 0과 1로 구성된 코드워드를 생성
▪
왼쪽으로 가면 0, 오른쪽으로 가면 1을 추가
•
인코딩 및 디코딩
◦
각 문자를 대응하는 허프만 코드로 변환하여 데이터 압축을 수행
◦
압축된 데이터를 디코딩할 때는 허프만 트리를 사용하여 각 코드워드를 원래의 문자로 변환