Kwin's Development Diary.

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

검색 / 탐색 (Search) - 컴퓨터에 저장한 자료 중 원하는 항목을 찾는 작업 ㄴ 검색 성공 - 원하는 항목을 찾은 경우 ㄴ 검색 실패 - 원하는 항목을 찾지 못한 경우 - 탐색 키를 가진 항목을 찾는 것 ㄴ 탐색 키(search key) = 자료를 구별하여 인식할 수 있는 키 - 삽입 / 삭제 작업에서의 검색 ㄴ 원소를 삽입하거나 삭제할 위치를 찾기 위해 검색 연산 수행 방법 - 수행 위치에 따른 분류 ㄴ 내부 검색 : 메모리 내의 자료에 대해 검색 수행 ㄴ 외부 검색 : 보조 기억 장치에 있는 자료에 대해 검색 수행 - 검색 방식에 따른 분류 ㄴ 비교 검색 방식(Comparison Search method) : 검색 대상의 키를 비교하여 검색 (Ex, 순차 검색, 이진 검색, 트리 검색) ㄴ 계..

정렬(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정점으로 진입하는 간선 수 ..

힙(heap) - 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조 - 최대 힙(max heap) ㄴ 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리 ㄴ 부모 노드 키 값 ≥ 자식 노드 키 값 ㄴ 루트 노드 : 키 값이 가장 큰 노드 - 최소 힙(min heap) ㄴ 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리 ㄴ 부모 노드 키 값 ≤ 자식 노드 키 값 ㄴ 루트 노드 : 키 값이 가장 작은 노드 힙 삽입 연산 1단계 : 완전 이진트리를 유지하면서 노드를 확장하여, 삽입할 원소를 임시 저장 ㄴ 노드가 n개인 완전 이진트리에서 다음 노드의 확장 자리는 n+1번의 노드 ㄴ n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장..

이진 탐색 트리 (Binary Search Tree) - 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조 - 정의 ㄴ 모든 원소는 서로 다른 유일한 키를 가짐 ㄴ 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작음 ㄴ 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 큼 ㄴ 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리 - 연산 ㄴ 루트에서 시작 ㄴ 탐색할 키 값을 루트 노드의 키값과 비교한다 ▶ 키 값 = 루트 노드의 키 값 : 원하는 원소를 찾았으므로 탐색 연산 성공 ▶ 키 값 루트 노드의 키 값 : 루트 노드의 오른쪽 서브 트리에 대해 탐색 연산 수행 ㄴ 서브 트리에 대해 순..

수식의 표기법 - 전위 표기법 (prefix notation) : 연산자를 피연산자 앞에 표기하는 방법 (ex +AB) - 중위 표기법 (infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 (ex A+B) - 후위 표기법 (postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 (ex AB+) 중위 표기식 ㅡ변환ㅡ> 전위 표기식 ① 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현 ② 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동 ③ 괄호 제거 EX) A * B - C / D 1단계 : ((A * B) - (C / D)) 2단계 : -(*(A B) / (C D)) 3단계 : -*AB/CD 중위 표기식 ㅡ변환ㅡ> 후위 표기식 ① 수식의 각 연산..

큐 (Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다. 삭제 ← front rear 삽입 ← 큐의 연산 과정 - 삽입 : enQueue 더보기 ① 공백 큐 생성 : 큐가 생성되지 않은 최초 상태에서만 실행 Q [0] [1] [2] ↑ front == rear == -1 ↑ ② 원소 A삽입 : enQueue(Q, A); Q [0] [1] [2] A ↑ front == -1 ↑ ↑ rear == 0 ↑ ③ 원소 B삽입 : enQueue(Q, B); Q [0] [1] [2] A B ↑ front == -1 ↑ ↑ rear == 1 ↑ - 삭제 :..