거창한 시작

위상 정렬 - 순서가 있는 일을 순서대로 나열하는 정렬 - 의미 변환 * 그래프 이론에서, 순서 : 방향 그래프 * 그래프 이론에서, 일 : 노드 * 그래프 이론에서, 순서대로 나열 : 간선의 방향을 거스르지 않게 노드 나열 - 예시 * 대학교 강의에서 선행 과목을 고려해서 강의를 수강 * 스타크래프트 게임에서 높은 테크 건물을 짓기 위해서는 하위 테크 건물을 먼저 건설 동작 - 진입 차수가 0인 정점들을 선택하여 스택/큐에 삽입 - 스택/큐에서 정점을 하나 꺼내어 꺼낸 정점과 연결된 간선 제거(간선 수 감소) - 꺼낸 정점은 차례대로 나열 - 위 과정 반복 - 모든 정점이 선택/삭제되면 종료 - 예시 : 영상 ( 1:30부터 ) - 예시 : 전체 과정 구현 1 2 3 4 5 6 7 8 9 10 11 1..

힙 정렬 - 힙 알아보기 - 최대 힙/최소 힙을 구성하여 정렬 동작 - 정렬할 배열을 최대 힙으로 구성 - Root 노드를 힙의 마지막 노드와 교환 - 마지막 노드를 제외하고 다시 최대 힙 구성 - Root 노드를 힙의 두 번째 마지막 노드와 교체 - 위 과정 반복 - 예시 : 애니메이션 - 예시 : 전체 과정 * 초기 배열 * 최대 힙으로 구성 + 힙 삽입 방법과 거의 동일 * 교환과 힙 구성 반복 + 교환과 힙 구성은 힙 삭제 방법과 거의 동일 구현 - 오름차순 정렬을 위해서 최대 힙 이용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43..

퀵 정렬 - 분할 정복 알고리즘 - 배열의 요소들을 Pivot이라는 요소와 비교하여 비균등하게 2개의 배열로 분할해서 정렬 동작 - 정렬할 배열에서 첫 요소를 Pivot으로 선택 - i는 i가 가리키는 요소가 Pivot보다 크거나 같을 때까지 그리고 배열의 오른쪽 끝일 때까지 이동 - j는 j가 가리키는 요소가 Pivot보다 작거나 같을 때까지 그리고 배열의 왼쪽 끝+1일 때까지 이동 - i와 j가 멈추면, 두 요소를 교환 - i와 j가 엇갈릴 때까지 반복 - i와 j가 엇갈리면, Pivot과 j를 요소를 교환하고 Pivot을 제외한 2개의 배열에서 위 과정 반복 * Pivot이 j의 위치로 이동하고 2개의 배열이 생성 * Pivot을 기준으로 왼쪽은 Pivot보다 작은 값들이 모임 * Pivot을 기준..

병합 정렬 - 분할 정복 알고리즘으로 정렬하려는 배열을 균등하게 분할하여 정렬 동작 - 정렬할 배열을 균등하게 분할하고 - 분할된 부분 배열을 정렬하고 - 두 개의 정렬된 부분 배열을 병합하여 전체를 정렬 - 예시 : 애니메이션 - 예시 : 전체 과정 예시 - 예시 : 추가 배열이 필요한 이유 (마지막 정복 결합을 예시로) 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 // 정렬과 병합하는 함수 void merge(int list[], int ..

버블 정렬 - 두 인접한 요소를 검사하여 정렬 동작 - 오름차순으로 정렬 - 1회 * 1번째 요소와 2번째 요소를 비교하고 순서가 맞지 않으면 교환 * 2번째 요소와 3번째 요소를 비교하고 순서가 맞지 않으면 교환 * n-1번째 요소와 n번째 요소를 비교하고 순서가 맞지 않으면 교환 * n번째에 가장 큰 요소가 위치 - 2회 * 1번째 요소와 2번째 요소를 비교하고 순서가 맞지 않으면 교환 * 2번째 요소와 3번째 요소를 비교하고 순서가 맞지 않으면 교환 * n-2번째 요소와 n-1번째 요소를 비교하고 순서가 맞지 않으면 교환 * n-1번째에 두 번째로 큰 요소가 위치 - 이하 과정 동일 - 예시 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void bubb..

쉘 정렬 - 삽입 정렬의 문제점 * 삽입할 위치가 현재 삽입할 요소와 멀리 떨어져 있다면, 많은 요소들을 옮겨야 함 - 삽입 정렬의 문제점을 보완하는 정렬 - 쉘 정렬은 특정 간격(k)에 있는 요소들을 부분 배열으로 하고 삽입 정렬을 진행하여 정렬 - 쉘 정렬의 원리 * 배열의 요소들이 정렬되어 있으면 삽입 정렬의 시간복잡도 O(N) * 배열의 요소들을 어느 정도 정렬 시켜 놓으면 삽입 정렬은 빠름 * 어느 정도 정렬 시키기 위해서 배열을 간격 별로 모아서 부분 배열을 만들어 정렬 동작 - 초기 간격(k)를 구함 : 정렬할 배열의 길이 / 2 - 간격(k) 만큼 떨어진 요소들을 부분 집합으로 하고 삽입 정렬 - 위 과정으로 한 번의 정렬이 끝나면, k = k / 2 하여 위 과정 반복 - 간격(k)의 크..

선택 정렬 - 두 번째 위치부터 시작하여, 왼쪽에 정렬된 배열과 비교하여 요소의 위치를 찾아 삽입하는 정렬 동작 - 주어진 리스트 두 번째 위치부터 차례대로 요소를 선택 - 선택한 요소를 왼쪽에 정렬된 배열과 비교하여 자신의 위치를 찾고 삽입 - 위 과정 반복 - 예시 * 1번 : 요소 2를 선택하고 왼쪽에 정렬된 배열에서 들어갈 위치를 찾아 삽입 * 2번 : 요소 4를 선택하고 왼쪽에 정렬된 배열에서 들어갈 위치를 찾아 삽압 * 이하 과정 동일 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void insertionSort (int *list, int n){ // 요소가 들어갈 위치, 요소 값 int j, value; for(int i=1; i=0 &&..

선택 정렬 - 앞에서부터 어떤 값을 넣을지 선택하는 알고리즘 동작 - 주어진 리스트 중에서 최소값/최대값을 선택 - 선택한 값을 정렬되지 않은 앞의 갑과 교체 - 위 과정 반복 * 예시 + 1번 : 탐색하여 최소값 1를 찾고, 첫 번째 값과 교환 + 2번 : 탐색하여 최소값 2를 찾고, 두 번째 값과 교환 + 3번 : 탐색하여 최소값 3을 찾고, 세 번째 값과 교환 + 이하 과정 동일 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 void selectionSort(int *list, int n){ // 최소값 인덱스, 임시 변수 int idx_min, tmp; for(int i=0; i

최단 경로 문제 - 그래프 이론에서 두 정점을 잇는 가장 짧은 경로를 찾는 문제 문제 종류 - 단일-쌍 최단 경로 문제 : V에서 V'로 가는 경로들 중 최단 경로 찾기 - 단일-출발 최단 경로 문제 : V에서 출발하여 그래프 내의 모든 정점에 도착하는 최단 경로 찾기 - 단일-도착 최단 경로 문제 : 그래프 내의 모든 정점에서 출발하여 V에 도착하는 최단 경로 찾기 - 전체-쌍 최단 경로 문제 : 그래프 내의 모든 정점 사이의 최단 경로 찾기 알고리즘 종류 1) Dijkstra algorithm (다익스트라 알고리즘) - 그래프 이론에서 하나의 시작 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 알고리즘 - 동작 * 출발 노드 선택 * U노드로 이동할 때, 현재 이동해서 U까지 온 비용과 이전에 ..

신장 트리 (Spanning Tree) - 그래프 내의 모든 정점을 연결하는 트리 - 사이클은 없음 - N개의 정점과 N-1개의 간선 - 왼쪽 그래프는 오른쪽의 총 8개의 신장 트리를 가짐 최소 신장 트리 (Minimum Spanning Tree) - 신장 트리 중에서 간선들의 가중치 합이 최소인 트리 - 아래 그래프에서 굵은 간선으로 이루어진 트리가 최소 신장 트리 최소 신장 트리 알고리즘 - 최소 신장 트리를 찾을 수 있는 알고리즘 1) 크루스칼 알고리즘 (Kruskal's algorithm) - 탐욕적인 방법을 이용하여 모든 정점을 최소 비용으로 연결하는 방법 - 간선 선택 기반 - 동작 * 간선들을 가중치 오름차순으로 정렬 * 가중치가 작은 간선을 순서대로 선택하여 사이클을 이루는지 확인 * 사이..