[자료구조]정렬, 그래프, 최단경로, 해싱

8 .정렬

 

내부 정렬 : 정렬 작업을 주 메모리에서 처리

1) 선택 정렬 : 최솟값 또는 최댓값 탐색하여 정렬 리스트로 이동시키고 정렬 대상에서 제외하는 것 반복 O(n^2)

2) 버블 정렬 : 인접한 원소들을 비교하여 큰 값을 오른쪽으로 이동시키는 방법 O(n^2) 

선택정렬과 버블정렬은 코드 유사하지만 swap의 위치가 다름

3) 삽입 정렬: 정렬된 리스트에 새로운 원소를 추가하는 작업 -> 정렬 위치를 찾을 때까지 왼쪽으로 이동시키는 방법

                     최상의 경우 O(n) 최악의 경우 O(n^2)

4) 쉘 정렬: 삽입 정렬을 개선하기 위한 알고리즘

                 비교할 원소 간의 거리 gap을 설정하고 gap이 1에 도달하면 종료

5) 퀵 정렬 : 기준 수 선택하여 정렬할 원소들을 두 개의 세그먼트로 분할

6) 합병 정렬: 정렬된 리스트를 하나로 합치는 합병 작업

                     n개의 원소를 분할한 후 내부에서 정렬된 두 세그먼트를 합병하는 과정 반복

외부 정렬: 정렬 작업을 외부 기억장치에서 처리

 

9. 그래프

그래프 - 무방향 그래프, 방향 그래프(순환 루프는 자료구조의 학습 범위에 포함하지 않는다)

완전 그래프(complete graph) 정점 연결하는 간선이 모두 존재하는 그래프

연결 그래프(connected graph) 모든 정점의 순서쌍 간에 도달할 수 있는 경로가 존재 
컴포넌트 - 더 이상의 정점을 추가할 수 없는 연결된 서브 그래프

트리- 사이클이 없는 연결 그래프

 

무방향 그래프 

인접 행렬과 인접 리스트로 표현

일반적인 방향 그래프의 인접 리스트는 진출 간선 기준으로 작성 <-> 역 인접 리스트(진입 간선 기준으로 작성)
네트워크 - 간선에 가중치가 부여된 그래프

 

그래프의 탐색 방법

깊이 우선 탐색(dfs) : 인접 노드에 연결된 또 다른 인접 노드를 먼저 탐색 (재귀)

너비 우선 탐색(bfs) : 인접 노드부터 우선적으로 탐색 (큐:레벨 탐색과 유사)

-> dfs bfs 모두 시작 지점이 존재한다

 

최소 비용 신장 트리

신장 트리(spanning tree)를 만들기 위한 과정

최소 비용 신장 트리: 간선의 가중치 합이 최소가 되는 신장 트리

1) 간선 제거에 의한 방법 : 사이클이 존재하지 않을 때까지 과정 반복

2) 간선 선택에 의한 방법: 간선을 하나씩 선택하여 최소 비용 신장 트리를 찾는 방법

2.1 쿠르스칼 방법: 최소비용부터  선택하는 방법

2.2 프림의 방법(greedy algorithm) : 시작 정점 존재 , 인접 간선 중 최소비용 간선 선택하여 검토

2.3 솔린의 방법: 정점 하나하나의 경우 최소 비용 간선 선택하기(중복의 경우 패스)

 

10. 최단 경로와 작업네트워크

 

최단 경로 탐색

탐욕 알고리즘(greedy algorithm) - 출발지에서 최소 비용 간선만을 선택하여 미 방문 노드로 이동하는 경로 탐색 방법

출발지와 도착지 미리 설정해둠

<1개 출발 1개 도착>

 

다익스트라 알고리즘

출발 노드에서 각 노드에 이르는 모든 최단 경로 탐색

<1개 출발 n개 도착>

 

플로이드 와샬 알고리즘

a-1 a0 ~~~

A+ A*

<n개 출발 n개 도착>

 

작업 네트워크와 위상정렬

작업 네트워크 : 그래프의 정점 또는 간선에 작업을 표시하여 작업의 선수 관계 표시

-정점 작업 네트워크, 간선 작업 네트워크

 

1. 정점 작업 네트워크

위상정렬: 사이클이 없는 방향 그래프에서 작업들을 선수 관계에 의해 정렬하는 과정 -큐를 이용하여 구현 가능

-> 차수가 0인 정점 추가하는 과정 반복

2. 간선 작업 네트워크

특정 정점으로 들어오는 작업 모두 완료되어야 공정 시작 가능

임계 경로, 임계 작업: 프로젝트 시작 점에서 끝점까지 가장 긴 시간이 임계경로(작업 완료하는 데 걸리는 시간)

 

11. 탐색과 해싱

탐색 : key와 일치하는 원소를 찾는 작업

 

1. 순차 탐색 : 탐색 키를 찾을 때까지 순차적으로 반복 비교하는 방법 O(n)
2. 이진 탐색: 중간값과 탐색 키를 비교하는 방법 O(log2n)

3. 보간 탐색: 이진 탐색의 성능을 개선할 목적으로 개발

탐색 범위에서 키 값과 위치의 차이가 비례한다는 가정

 

해싱

반복적 비교 없이 저장된 장송 빠르게 접근할 수 있는 방법