Developer Cafe

비교 검색 방식 - 검색 대상의 키를 비교하여 검색하는 방법 (순차 검색, 이진 검색, 이진 트리 검색) 계산 검색 방식 - 키를 비교하지 않고 계수적인 성질을 이용한 계산으로 검색 하는 방법 (해싱) 해싱 해싱은 계수적인 성질을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다. 해싱 검색은 키값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 가서 항목이 있으면 검색 성공이 되고 없으면 검색 실패가 된다. 해싱 함수 조건 ○ 해싱 함수는 계산이 쉬워야 한다. 비교 검색 방법을 사용하여 키값의 비교 연산을 수행하는 시간보다 해싱 함수를 사용하여 계산 하는 시간이 빨라야 해싱 검색을 사용하는 의미가 있다. ○ 행싱 함수는 충돌이 적어야 한다. 충..

비교 검색 방식 - 검색 대상의 키를 비교하여 검색하는 방법 (순차 검색, 이진 검색, 이진 트리 검색) 계산 검색 방식 - 키를 비교하지 않고 계수적인 성질을 이용한 계산으로 검색 하는 방법 (해싱) 순차 검색(순차 검색, 색인 순차 검색) 순차검색은 일렬로 되어있는 자료를 처음부터 마지막까지 순서대로 비교하여 검색하는 방법으로, 가장 간단하고 직접적인 방법으로서 배열이나 연결 리스트로 구현된 순차 자료구조에서 원하는 항목을 찾는 방법이다. 색인 순차 검색은 인덱스 테이블을 추가로 사용하여 탐색의 효율을 높이는 검색 방법이다. 찾고자 하는 키값을 인덱스 테이블에서 검색하여 indexTable[i].key

정렬 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다. 내부 정렬 1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵) 2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸) 3. 병합 방식 - 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합) 4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수) 5. 선택 방..

정렬 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다. 내부 정렬 1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵) 2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸) 3. 병합 방식- 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합) 4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수) 5. 선택 방식..

정렬 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다. 내부 정렬 1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵) 2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸) 3. 병합 방식 - 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합) 4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수) 5. 선택 방..

정렬 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다. 내부 정렬 1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵) 2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸) 3. 병합 방식- 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합) 4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수) 5. 선택 방식..

정렬 순서 없이 배열되어 있는 자료들을 작은 것부터 큰 것 순서의 오름차순이나 큰 것부터 작은 것 순서의 내림차순으로 재배열하는 것이다. 정렬 방법은 수행되는 위치에 따라서 컴퓨터 메모리 내부에서 수행하는 내부 정렬과 메모리의 외부인 보조 기억 장치에서 수행하는 외부 정렬로 분류할 수 있고, 수행 방법에 따라 비교식 정렬과 분산식 정렬로 구분할 수 있다. 내부 정렬 1. 교환 방식 - 키를 비교하고 교환하여 정렬하는 방식(선택, 버블, 퀵) 2. 삽입 방식 - 키를 비교하고 삽입하여 정렬하는 방식(삽입, 셸) 3. 병합 방식- 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합) 4. 분배 방식 - 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식(기수) 5. 선택 방식..

신장 트리 n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어져 사이클이 없는 단순 연결 그래프를 신장 트리라고 한다. 깊이 우선 탐색을 이용하여 생성된 깊이 우선 신장 트리와 너비 우선 탐색을 이용하여 생성된 너비 우선 신장 트리가 있다. 최소 비용 신장 트리 무방향 가중치 그래프에서 가중치의 합이 쵯소인 신장 트리를 최소 비용 신장 트리라고 한다. 최소 비용 신장 트리를 만들기 위해 Kruskal이 만든 알고리즘과 Prime이 만든 알고리즘을 사용한다. Kruskal Kruskal 알고리즘은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 Kruskal 알고리즘1 과 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 Kruskal 알..

그래프 순회 - 하나의 정점에서 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색 이라고 한다. - 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색이 있다. 1. 깊이 우선 탐색 깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 함으로써 모든 정점을 방문하는 쉰회 방법이다. 스택을 사용한다. (1) 시작 정점 v를 결정하여 방문한다. (2) 정점 v에 인접한 정점 중에서 ⓐ 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 w를 방문한다. 그리고 w를 v로 설정하고 (2) 반복. ⓑ 방문하지 않은 ..

연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성된 그래프 G를 G=(V, E)로 정의한다. 그래프는 간선의 방향성 유무에 따라서 방향 그래프와 무방향 그래프가 있고, 연결정도에 따라서 연결 그래프와 단절 그래프, 완전 그래프가 있다. 그리고 가중치를 가진 간선으로 이루어진 가중치 그래프가 있다. 그래프를 구현하기 위해서 표현하는 방법은 순차 자료구조 방식을 이용하는 2차원 배열의 인접 행렬 방법과 연결 자료구조 방식인 연결 리스트를 사용하는 인접 리스트 방법이 있다. 1. 인접 행렬 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다. 인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있습니다. A B C D A 0 1 0 1 B ..