Computer Science
-
퀵 정렬(quick sort)Computer Science/Data_Structure 2020. 1. 8. 22:36
퀵 정렬의 개념 퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵정렬도 분할-정복(divide and conqure)에 근거한다. 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다. 그러나 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 처음에 리스트의 첫 번째 요소인 5를 피벗(pivot)으로 정하였다. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 ..
-
합병 정렬(merge sort) 란?Computer Science/Data_Structure 2020. 1. 7. 16:45
합병 정렬의 개념 합병 정렬(merge sort)는 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. 합병 정렬은 분할 정복(divide and conquer) 기법에 바탕을 두고 있다. 분할 정복 기법은 대게 순환 호출을 이용하여 구현된다. 분할(divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다. 위의 과정을 그림으로 보면서 이해해보자. 다시 말하면, 위와..
-
버블 정렬(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)의 시간안에 탐색을..
-
그래프(graph)의 구현 2가지Computer Science/Data_Structure 2020. 1. 4. 06:05
그래프를 구현하는 방법은 책을 보거나, 구글링을 해보아도 전부 인접행렬 or 인접리스트를 이용하여 구현을 한다. 상황에 맞게 시간복잡도를 고려하여 더 효율적인 것을 사용하면 된다. 그래서 각각의 장단점을 공부하려 글을 쓰려 한다. https://kosaf04pyh.tistory.com/131 [자료구조] 그래프(Graph) 이번시간에는 그래프에 대해 공부해 보겠습니다. 그래프란 ? 그래프는 정점(Vertex)간의 관계를 표현하는 자료구조 입니다. 그래프 G = (V,E)로 정의하는데, V(Vertex)는 그래프에 있는 정점들의 집합을 의미하고.. kosaf04pyh.tistory.com https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html ..
-
너비 우선 탐색(BFS) 란?Computer Science/Data_Structure 2020. 1. 4. 05:30
그래프 탐색에는 2가지가 있다고 했는데 그 중에 하나인 BFS 탐색에 대해서 정리하려고 한다. 너비 우선 탐색(breath first search : BFS) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 위와 같은 그래프에서 화살표의 방향대로 탐색을 한다. (시작 정점에서 가까운 노드부터 탐색하는 것을 알 수 있다) 너비 우선 탐색을 위해서는? 가까운 거리에 있는 정점들을 차례로 정한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함 무조건 큐에서 정점을 꺼내서 정점을 반물하고 인접 정점들을 큐에 추가한다.(큐가 소진될 때 까지 반복) 너비 우선 탐색 과정 다시한번 정리하자면 다음과 같다. 위의 과정을 큐가 공백 상태가 될 때 까지 계속한다...