전체 글
-
버블 정렬(bubble sort) 란?Computer Science/Data_Structure 2020. 1. 7. 04:22
버블 정렬의 원리 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이러한 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속한다. 바로 자바로 구현해보자. public class BubbleSort { public static void main(String[] args) { int[] list = {7, 4, 5, 1, 3}; int tmp = 0; // 버블 정렬 for (int i = list.length - 1; i > 0; --i) { for (int j = 0; j < i; +..
-
삽입 정렬(insertion sort) 란?Computer Science/Data_Structure 2020. 1. 7. 03:58
삽입정렬의 원리 삽입 정렬(insertion sort)은 손안의 카드를 정렬하는 방법과 유사하다. 우리는 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 삽입 정렬은 처음에 2번 째 위치의 값을 key로 정해서 시작한다. key 값을 자신의 왼쪽에 놓인 것들과 하나씩 비교하면서 자신의 위치를 찾으면 그 자리의 있는 것과 자리를 바꾸게 된다. 자바로 삽입 정렬을 구현해보자. 삽입 정렬의 복잡도 분석 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 최선의 경우는 먼저 입력자료가 이미 정렬되어 있는 경우는 가장 빠르다. 최악의 경우는 입력 자료가 역순일 경우이다. 최선의 경우 삽입 정..
-
선택 정렬(selection sort) 란?Computer Science/Data_Structure 2020. 1. 7. 02:07
선택 정렬의 원리 선택 정렬(selection sort)은 가장 이해하기가 쉬운 정렬 방법이다. 선택 정렬은 다른 추가 메모리를 요구하지 않는 정렬 방법인 제자리 정렬(in-place-sorting)을 이용한다. 초기 배열에서 최소값을 찾는다. 이 최소값을 배열의 첫번째 요소와 교환한다. 그리고 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 위의 절차를 (배열원소-1)만큼 반복하면 추가적인 배열을 사용하지 않고 정렬 가능하다. 이제 자바를 이용해서 선택 정렬을 구현해보자. 선택 정렬의 분석 선택 정렬의 성능 분석을 위하여 비교 횟수와 이동 횟수를 따로 구하여 보자. 먼저 비교 횟수를 구하기 위하여 두개의 for 루프의 실행 횟수를 계산해보자. 외부루프는..
-
해싱(Hashing) 이란?Computer Science/Data_Structure 2020. 1. 4. 16:08
오늘은 해싱의 개념에 대해서만 정리해보고자 한다 해싱(hashing) 이란? 선형 탐색이나 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 이정도만 되어도 괜찮은 응용도 있지만, 어떤 응용에서는 더 빠른 탐색 알고리즘을 요구한다. 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조 해싱(Hashing) : 해시 테이블을 이용한 탐색 더 효율적인 알고리즘은 없을까? 예를들어 O(1)의 시간안에 탐색할 수 있는건 없을까? 해싱은 O(1)의 시간안에 탐색을..