Algorithm (31) 썸네일형 리스트형 해싱 (Hashing) 해싱 (Hashing) 해시 함수와 해시 테이블을 이용하여 데이터를 빠르게 저장하고 탐색하는 방법 데이터를 해시 테이블이라는 배열에 저장 -> 데이터의 키 값으로 해시 함수를 통해 테이블의 주소를 반환 -> 원하는 데이터를 찾음 해시 테이블 값의 연산에 의해 직접 접근 가능한 구조 해시 함수 해시 테이블에서 키 값을 주소로 변환하는데 사용되는 함수 계산이 빠르고 간단해야 함 다른 키 값이 같은 주소를 산출하는 경우가 적어야 함 해시 함수 종류 나눗셈법 중간 제곱법 폴딩법 기수 변환법 자리수 분석법 나눗셈법 키 값을 정수로 보고 이를 적당한 양의 정수(주소, 해시 테이블의 크기 등)로 나누어서 그 나머지를 해시 주소로 하는 방법 h(k) = k mod N h() : 해시 함수 k : 키 값 N : 나누는 .. 탐색 (Search) - 순차 / 이진 / 보간 / 이진 트리 탐색 탐색 (Search) 데이터의 집단 내에서 특정 데이터를 찾아내는 구조 탐색 알고리즘의 효율성은 탐색 집단의 구조가 어떻게 구성되어 있느냐에 따라 영향을 받음 컴퓨터가 가장 많이 하는 작업 중의 하나 탐색에 사용되는 자료 구조 배열 연결 리스트 트리 그래프 등 탐색 방법 순차 탐색 이진 탐색 보간 탐색 이진 트리 탐색 순차 탐색 (Sequential Search) 정렬되지 않은 데이터의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 가장 간단하고 직접적인 탐색 방법 크기가 적은 리스트에서는 효율적이지만 크기가 큰 리스트에서는 매우 비효율적 하나씩 비교하기 때문에 탐색 용이 탐색 시간이 느리며 수행 시간 많이 걸림 이진 탐색 (Binary Search) 전체 데이터 집합을 두 부.. 정렬 시간복잡도 정리 ㅇㅇ 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) 원소들을 힙(heap)이라는 자료 구조를 이용하여 정렬하는 방법 힙 구조 완전 이진 트리로서 각 노드의 키 값이 자식 노드들의 키 값보다 작지 않은 트리 힙 루트는 트리 중 가장 큰 값을 나타냄 힙 정렬 수행 과정 1단계 : 주어진 데이터로 이진 트리 구성 2단계 : 힙 구조 알고리즘 수행 3단계 : 힙 정렬 알고리즘 수행 힙 구조 알고리즘 제일 늦게 구성된 트리 선택 부모 노드와 자식 노드 중 가장 큰 값 선택 부모 노드와 자식 노드 중 가장 큰 값을 비교하여 자식 노드가 크면 서로 위치 교환 (큰 값을 위로 보냄) 힙 구조가 완성될 때 까지 위 과정 반복 힙 정렬 알고리즘 근 노드의 값을 배열의 맨 마지막에 저장 (근 노드 삭제에 해당) 빈 근 노드의 자리에는 자식 노드.. 기수 정렬 (Radix Sort ) 기수 정렬 (Radix Sort ) 정렬할 원소의 키 값을 나타내는 숫자의 자리수(radix)를 기초로 정렬하는 기법 사전식 정렬 방법 정렬하고 하는 값을 버킷에 넣어 정렬 버킷으로 큐 사용 (먼저 들어온 것이 먼저 출력) 버킷의 개수 -> 키의 표현 방법과 밀접한 관계 이진법 사용 -> 버킷 2개 알파벳 문자 사용 -> 버킷 26개 십진법 사용 -> 버킷 10개 기수 정렬 방법 첫 번째 패스 (1라운드) 정렬할 키의 가장 작은 자리수를 기준으로 분배 정렬 두 번째 패스 두 번째 작은 자리수를 기준으로 분배 정렬 키 값이 같은 경우 이전 정렬에서의 순서를 그대로 유지 키의 가장 큰 자리수까지 반복 수행 한 자리 수의 기수 정렬 수행 단순히 자리 수에 따라 버킷에 넣었다가 꺼내면 정렬됨 두 자리 수의 기수.. 2원 합병 정렬 2원 합병 정렬 정렬된 2개의 리스틀 혼합하여 완전히 정렬된 하나의 리스트로 합하는 정렬 방식 쉘 정렬 (Shell Sort) 쉘 정렬 (Shell Sort) 원소의 비교 연산과 먼 거리의 이동을 줄이기 위해 몇 개의 서브 리스트로 나누어 삽입 정렬을 반복 수행 삽입 정렬의 개념을 확대하여 일반화 시킨 정렬 방법 삽입 정렬의 최대 문제점 : 요소들이 이동할 때, 이웃한 위치로만 이동하는 것 쉘 정렬 -> 요소들이 멀리 떨어진 위치로도 이동할 수 있기 때문에 쉘 정렬이 삽입 정렬보다 정렬 속도 빠름 쉘 정렬 방법 정렬에서 사용할 간격(interval) 결정 전체 원소 수 n의 1/3, 다시 이것의 1/3, … 간격이 작아질수록 짧은 거리를 이동하고 원소 이동이 적음 첫 번째 간격에 따라 서브 리스트로 분할 각 서브 리스트에 대해 삽입 정렬 수행 두 번째 간격에 따라 서브 리스트로 분할 각 서브 리스트에 대해 삽입 정렬 수행 리스트.. 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 레코드가 순서대로 되어 있지 않으면 인접한 항목 교환 버블 정렬 과정 a[0]과 a[1]을 비교하여 정렬 순서에 맞도록 교환 a[1]과 a[2]을 비교하여 정렬 순서에 맞도록 교환 … a[n-2] 와 a[n-1]을 비교하여 정렬 순서에 맞도록 교환 제일 큰 원소가 배열의 n-1 위치로 이동 (1라운드) 배열의 처음부터 다시 비교 정렬 버블 정렬 비교 횟수 항목의 개수 N이면 (N-1) + (N-2) + … + 1 수학 공식 : N(N-1) / 2 버블 정렬 구현 예시 package sort; public class BubbleSortEx { public static void main(String[] args) { int[] arr = {5, 2, 8, 3, 1}; bu.. 정렬 (Sort) 정렬 (Sort) 일련의 자료들을 자료 중에 포함된 몇 가지 항목을 우선 순서대로 지정하여 그 순서에 따라 모든 자료를 배열(나열)하는 방법 컴퓨터 공학분야에서 가장 기본적이고 중요한 알고리즘 중의 하나 자료 탐색에 있어서 필수적 모든 경우에 최적인 알고리즘은 없음 적용하고자 하는 문제 상황에 따라 적절히 선택하여 사용 정렬 알고리즘 종류 버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion 쉘 정렬 (Shell Sort) 퀵 정렬 (Quick Sort) 2원 합병 정렬 (Two-way merge Sort) 기수 정렬 (Radix Sort) 힙 정렬 (Heap Sort) 정렬 알고리즘의 평가 기준 비교횟수와 이동횟수 단순하지만 비효율적인 방법 : 삽입.. 이전 1 2 3 4 다음