[파이썬] DAY11 그래프 복습 & 정렬

< 질문 사항들 >

설날 과제는

정리용 문제 안 낼 거래..

그래프 코드 주석 달아놓기

 

넓이 우선 순위 그래프 탐색에서

우선순위 큐(늦게 들어왔더라도 우선순위 가중치를 매겨서 먼저 내보내는 큐 방식)랑

dequeue enqueue랑 헷갈리지 말것.

 

 

자료구조 스택과 스택 영역은 같다.(메모리 구조는 스택이다.)

자료구조 힙 과 힙 메모리 영역은 다르다.... 즉 힙 영역은 자료구조 힙을 쓰지 않는다. 동음이의어 같은 관계

참고로 C에서는 힙이라는 언어를 메모리에서 쓰지 않는다.

 

API 문서 안에 라이브러리가 있다. 

파이튜터는 3.6 버전을 쓴다.

 

 

코딩테스트

리스트를 주로 쓴다.

큐 스택을 직접 구현하지 않는다.

 

 

 

 동적 프로그래밍 dp(dynamic programming)

큰 문제를 소분해서 프로그래밍함으로써 풀어나간다.

나눠서 기능이 동작하도록 한다.

잘게 쪼개서 지나간 길에 대해 기억하며 계속 길을 수정한다.

 

---

 

1. 그래프 복습

깊이 우선 탐색(DFS) - 스택(이전 작업 기록해야하므로)

너비 우선 탐색(BFS) - 큐

 

그래프 탐색할 때 있어야 하는 조건 3가지

1) 그래프

2) 깊이/ 너비 우선 탐색

3) 모든 노드를 다 들렸는지 여부 체크

 

 

사이클이 없는 그래프를 트리라고 한다.

 

---

2. 최소 시간 신장 트리

신장트리 : 정점이 n개 있으면 간선이 n-1개 있는 트리

가중치를 가지고 있는 무방향 그래프

가중치: 비용, 거리, 시간을 의미하는 값

 

끊김, 사이클 둘 다 발생하면 안된다.

 

최소 시간 신장 트리는 항상 같은 결과가 나온다!

 

1. 크루스칼(Kruskal) 알고리즘1

모든 가중치를 내림차순으로 정렬

끊김이 발생할 수 있다.

가중치가 가장 높은 순으로 간선을 없앤다. 단 그래프의 끊김이 발생하면 무시하고 넘어간다.

n-1개의 간선이 될 때까지 없앤다.

코드로 구현: list에 넣는다. -> sort 오름차순 -> reverse로 내림차순 -> n-1까지 없앤다.

 

2. 크루스칼(Kruskal) 알고리즘2

모든 가중치를 오름차순으로 정렬

사이클이 발생할 수 있다.

가중치가 가장 낮은 간선으로 그린다.

방식은 다르지만 크루스칼 알고리즘 1과 같은 알고리즘이다.

n-1개의 간선이 될 때까지 그린다.

 

 

3. 프림(Prim) 알고리즘

dynamic programming(dp)를 바탕으로 메모리에 지나간 경로의 가중치 계산값을 기록하고 그린다.

그리는 것이므로 사이클을 조심해야 한다.

나아가면서 계산했던 가중치들을 모두 기억하고 있다. 

 

 

---

3. 정렬

정렬(sort) 2개 이상의 데이터를 내림차순 / 오름차순으로 재배열한다.

 

 

정렬 방법에 대한 분류

1) 실행 방법에 따른 분류

(1) 비교식 정렬: 데이터끼리 일일히 비교

(2) 분산식 정렬: 데이터를 집합으로 묶어 집합 끼리 비교

 

2) 정렬 장소에 따른 분류(주기억 장치 / 보조 기억 장치)

(1) 내부 정렬(주기억 장치인 메모리에서 정렬하는 방식)

메모리 용량에 제한된다.

내부 정렬 방식 5가지:

교환(선택 정렬, 버블, 퀵) /

삽입(삽입, 쉘) /

병합(2-way, n-way) /

분배(기수) : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식/

선택(히프, 트리) : 이진트리를 이용하여 정렬 

 

(2) 외부 정렬(보조기억장치인 하드디스크에서 정렬하는 방식)

외부 정렬 방식 1가지

병합 방식: 그룹 파일로 병합하여 정렬(2-way, n-way)

 

 

 

 

---

[1] 내부 정렬

 

1. 교환 방식 (a,b = b,a)

1) 선택 정렬

내가 만든 기준에 부합하는 데이터부터 꺼내 정렬하는 방식이다.

공간 복잡도: n개의 원소에 대해 n개의 메모리 사용

시간 복잡도: O(n^2)

2) 버블 정렬

정렬 중에 가장 느린 정렬

왼쪽 / 오른쪽을 수면으로 잡고 옆자리 데이터와 계속 대소 비교

공간 복잡도: n개의 원소에 대해 n개의 메모리 사용

시간 복잡도: O(n^2)

3) 퀵 정렬

분할과 병합을 통해서 정렬

기준인 피봇(pivot)을 잘 해야 성능이 늘어진다.

일반적으로 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다.

피봇 위치: 맨 왼쪽, 맨 오른쪽, 가운데( 데이터가 짝수개일 시에 // 을 이용하여 정한다.)

피벗을 기준으로 왼쪽은 피봇보다 작은 값, 오른쪽은 피봇보다 큰 값으로 구성한다.

왼쪽 화살표는 피봇보다 작은 값을 찾아나가고, 오른쪽 화살표는 피봇보다 큰 값을 찾아나간다.

왼쪽 화살표는 왼쪽 끝, 오른쪽 화살표는 오른쪽 끝, 피봇은 가운데를 선택한다.

데이터를 줄일 수록 시간을 짧게 만든다. 따라서 퀵 정렬은 빠르다.

공간 복잡도: n개의 원소에 대해 n개의 메모리 사용

시간 복잡도: O(n^2)

 

2. 삽입 방식

1) 삽입 정렬

벽을 세워두고 하나씩 한쪽으로 옮기면서 벽의 한쪽에서 버블 정렬처럼 정렬한다.

2) 쉘 정렬

데이터를 집합으로 묶어서 집합 별로 삽입 정렬한다.

이상적인 쉘 분할을 알아내야 된다. 잘 나눌수록 성능이 좋다.

-> 부분집합의 기준이 되는 간격인 h가 1이 될 때까지 반복한다.

일반적으로 원소 개수의 1/2로 시작하여 한 단계 수행할 때 마다 반씩 h를 감소시키면서 반복 수행한다.

공간 복잡도: n개의 원소에 대해 n개의 메모리 + h개의 메모리 사용

시간 복잡도: O(n^1.25)

 

 

 

퀵은 어느정도 정렬 되어있으면 끝에 피봇 두면 가장 비효율적이다.

이미 어느정도 정렬이 되어있다면 선택이나 삽입 정렬을 하는 게 좋다.

---

3. 병합 방식 - 머지 정렬

1) 2-way 정렬

2) n-way 정렬

분할 단계 : logn번 발생

병합 단계 : 서로 비교하면서 최대 n번 발생

공간 복잡도: n개의 원소에 대해 2n개의 메모리 사용

시간 복잡도: O(nlogn)

 

 

4. 분배 방식

기수 정렬(Radix sort)

힙이랑 비슷 ( 연산자처럼 사용)

큐(선입선출) 를 사용

원소의 키를 표현하는 기수만큼의 버킷 사용

자릿수까지 가지고 있는가(차수) 

몇 진법(표현): 한 자리수당 몇 개 쓸 수 있는가 = 버킷(버킷 하나하나 큐로 되어있다.)

데이터의 갯수

 

1의 자리 -> 10의 자리 -> 100의 자리 .....이런 식으로 기수 정렬 수행한다.

숫자나 알파벳 등 다 정렬이 가능한다.

cf) len(str(123))으로 자릿수 찾을 수 있다.

시간복잡도: O(d(n+r))

 

 

5. 선택 방식

1) 히프 정렬

힙에 넣고 뺀다.

힙의 루트에서만 빼서 결정

오름차순, 내림차순 으로 나올 수 있다.

힙 만드는 데 logn 꺼내는 데 n 

시간 복잡도: O(nlogn)

2) 트리 정렬

이진 탐색 트리를 중위순회하여 오름차순으로 정렬

시간 복잡도: O(nlogn)

 

 

 

[2] 외부 정렬

병합 방식

   2-way 정렬