Kwin's Development Diary.

이진 검색(Binary Search, 이분 검색, 보간 검색(Interpolation Search)) - 자료의 가운데 있는 항목을 키 값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방법 ㄴ 찾는 키 값 > 원소의 키 값 : 오른쪽 부분에 대해 검색 실행 ㄴ 찾는 키 값 = 원소의 키 값 : 검색 성공 ㄴ 찾는 키 값 23 1 3 10 23 29 33 45 50 오른쪽 검색 기준값 ◀ 검색 범위 ▶ ② 29 < 33 1 3 10 23 29 33 45 50 왼쪽 검색 ◀ 검색 범위 ▶ 기준값 ③ 29 = 29 1 3 10 23 29 33 45 50 검색 성공 기준값 ANS = 4 (검색 성공) 2. 11 검색 = 검색 실패 ① 11 < 23 1 3 10 23 29 33 45 50 왼쪽 검색 ◀ ..

순차 검색 (Sequential Search, 선형 탐색 (Linear Search)) - 일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법 - 가장 간단하고 직접적인 검색 방법 - 배열이나 연결 리스트로 구현된 순차 자료 구조에서 원하는 항목을 찾는 방법 - 검색 대상 자료가 많은 경우에 비효율적이지만 알고리즘이 단순하여 구현이 용이함 정렬되지 않은 순차 자료구조에서의 순차 검색 - 검색 방법 : 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지 비교하여 찾음 ㄴ 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지 반환 = 검색 성공 ㄴ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없음 = 찾은 원소가 없다 = 검색 실패 EX) List = {..

병합 정렬(Merge Sort) - 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법 - 부분 집합으로 분할(divide)하고, 각 부분 집합에 대해 정렬 작업을 완성(conquer)한 수에 정렬된 부분 집합들을 다시 결합(combine)하는 분할 정복(Divide And Conquer)기법 사용 - 종류 ㄴ 2-way 병합: 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법 ⑴ 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할 ⑵ 정복(conquer) : 부분집합의 원소들을 정렬 : 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법 적용 ⑶ 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 통..

삽입 정렬(Insert Sort) - 정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법 - 정렬할 자료를 두 개의 부분집합 S와 U로 가정 ㄴ 부분집합 S : 정렬된 앞부분의 원소들 ㄴ 부분집합 U : 아직 정렬되지 않은 나머지 원소들 ㄴ 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입 ㄴ 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. ㄴ 부분집합 U가 공집합이 되면 삽입 정렬이 완성 - 수행 과정 정렬되지 않은 배열 L = {69, 10, 30, 2, 16, 8, 61, 22} 초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고 나..

퀵 정렬(Quick Sort) - 정렬할 전체 원소에 대해 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬 ㄴ 왼쪽 부분 집합에는 기준 값보다 작은 원소들 / 오른쪽 부분 집합에는 기준 값보다 큰 원소들 ㄴ 기준 값 : 피봇(pivot) : 일반적으로 전체 원소 중 가운데 위치한 원소 선택 - 퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성 ㄴ 분할(divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할 ㄴ 정복(conquer) : 부분 집합의 원소들 중 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분 집합으로 정렬, 부분 집합의 크기가 1 이하로 충분치 않으면 순환 호출을 이용하여 재분할..

버블 정렬(Bubble Sort) - 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식 ㄴ 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬 ㄴ 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(Bubble) 정렬이라고 함. - 수행 과정 정렬되지 않은 배열 L = {69, 30, 16, 22} 69 30 16 22 ① 69 30 16 22 ② 30 16 22 69 30 69 16 22 16 30 22 69 30 16 69 22 16 22 30 69 30 16 22 69 ③ 16 22 30 69 ④ 버블 정렬 완성 16 22 30 69 16 22 30 69..

선택 정렬(Selection Sort) - 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 - 수행 방법 1. 전체 원소 중 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리 교환 .... 2. n 번째로 작은 원소를 찾아 선택하여 n 번째 원소와 자리 교환 3. 위 과정 반복하며 정렬 완성 - 수행 과정 정렬되지 않은 배열 L = {69, 10, 30, 2, 8, 22} 69 10 30 2 8 22 ① 기준 : 첫 번째 자리 2 10 30 69 8 22 정렬된 원소 정렬되지 않은 원소 ② 기준 : 두 번째 자리 2 8 30 69 10 22 정렬된 원소 정렬되지 않은 원소 ③ 기준 : 세 번째 자리 2 8 10 69 30 22 정렬된 원소 정렬되지 않은 원소 ④ 기..

Kruskal 알고리즘 : 최소 비용 신장 부분 트리를 찾는 알고리즘 최소 비용 신장 트리(MST, Minimum Cost Spanning Tree)의 의미를 모른다면 다음 게시물을 참고하길 바란다. [자료구조] 최소 비용 신장 트리 (Minimum Cost Spanning Tree) [자료구조] 신장 트리 (Spanning Tree : ST) 와 최소 비용 신장 트리 (Minimum Cost Spanning Tree : MST) 신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) / 너비 우선 신장 트리(Bre.. kwin0825.tisto..

프림 알고리즘(Prim Algorithm) : 가중치가 있는 무향(방향X) 그래프의 최소 비용 신장 트리(MST)를 찾는 알고리즘 최소 비용 신장 트리(MST, Minimum Cost Spanning Tree)의 의미를 모른다면 다음 게시물을 참고하길 바란다. [자료구조] 최소 비용 신장 트리 (Minimum Cost Spanning Tree) [자료구조] 신장 트리 (Spanning Tree : ST) 와 최소 비용 신장 트리 (Minimum Cost Spanning Tree : MST) 신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) ..