Kwin's Development Diary.

해싱(Hashing) : 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식 - 검색 방법 : 키 값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동 => 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패 - 해싱 함수(hashing function) : 키 값을 원소의 위치로 변환하는 함수 - 해시 테이블(hash table) : 해싱 함수에 의해서 계산된 주소의 위치에 항목을 저장한 표 - 해싱 용어 ㄴ 충돌 : 서로 다른 키 값에 대해 해싱 함수에 의해 주어진 버킷 주소가 같은 경우 해결 방법 : 충돌이 발생한 경우 비어있는 슬롯에 동거자 관계로 키 값 저장 ㄴ 동거자 : 서로 다른 키 값을 가지지만 해싱 함수에..

병합 정렬(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 정렬된 원소 정렬되지 않은 원소 ④ 기..

정렬(Sort) - 2개 이상의 자료를 작은 것부터 큰 순서(오름차순, Ascending)로 정렬 또는 큰 것부터 작은 것 순서(내림차순, Descending)로 재배열하는 것. - 키(key) : 자료를 정렬하는 데 사용하는 기준 값 정렬 방법의 분류 - 실행 방법에 따른 분류 ㄴ 비교식 정렬(Comparative Sort) : 비교하고자 하는 각 키 값들을 한 번에 두 개씩 비교하여 교환하여 정렬하는 방식 ㄴ 분산식 정렬(Distribute Sort) : 키 값을 기준으로 자료를 여러 개의 부분 집합으로 분해, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식 - 정렬 장소에 따른 분류 ㄴ 내부 정렬(Internal Sort) : 정렬할 자료를 메인 메모리에 올려 정렬 - 장) 정렬 속도 빠름 / 단..

신장 트리(Spanning Tree : ST) - n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 깊이 우선 신장 트리(Depth First Spanning Tree) / 너비 우선 신장 트리(Breadth First Spanning Tree) 최소 비용 신장 트리(Minimum Cost Spanning Tree : MST) - 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 - 최소 비용 신장 트리를 만드는 알고리즘 ㄴ Kruskal 알고리즘 [알고리즘] 크루스칼 알고리즘(Kruskal Algorithm) - JAVA / 자바 ㄴ Prime 알고리즘 [알고리즘] 프림 알고리즘(Prim Algorithm) - JAVA ..

그래프 순회(graph traversal), 그래프 탐색(graph search) - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 - 그래프 탐색 방법 ㄴ 깊이 우선 탐색 (Depth First Search : DFS) ㄴ 너비 우선 탐색 (Breadth First Search : BFS) 깊이 우선 탐색(Depth First Search : DFS) >>> A - B - D - G - E - C - F ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정..

그래프 (graph) - 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多관계를 가지는 원소를 표현하기 위한 자료구조 - 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합 ☞ G = (V, E) ㄴ V : 그래프에 있는 정점들의 집합 ㄴ E : 정점을 연결하는 간선들의 집합 - 인접, 부속 ㄴ 그래프에서 두 정점 Vi와 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다고 표현 ㄴ 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 표현 - 차수(degree) ㄴ 무방향 그래프의 Vn정점의 차수 = Vn정점에 부속되어 있는 간선 수 ㄴ 방향 그래프의 Vn정점의 차수 = Vn정점으로 진입하는 간선 수 ..