본문 바로가기

Data Structure & Algorithm10

Quicksort from CTCI 코딩 인터뷰 완전 분석(원제: Cracking the Coding Interview)에 소개된 Quicksort를 다시 한 번 정리 해보려고 한다. 기본적으로 퀵정렬은, 무작위로 한 원소를 정하고(이를 pivot이라 부른다), pivot보다 작은 원소들은 앞쪽에, 큰 원소들은 뒷쪽에 위치시킨다. 실행시간: 평균 O(n logn), 최악 O(n^2).메모리: O(logn)배열 분할(partition)에 사용되는 원소(pivot)가 배열의 중간값(median) 혹은 중간값에 가까운 값이라면 좋은 성능이 나오겠지만, 반드시 그러리라는 보장은 할 수 없다. 즉 퀵정렬은 pivot을 어떻게 정하느냐에 따라 느리게 동작할 수도 있으며, 최악의 경우 수행시간이 O(n^2)이 될 수 있다. 이전에 작성했던 퀵정렬(Ho.. 2019. 3. 2.
DFS(Depth-First Search; 깊이우선탐색) 그래프 탐색(Graph Search)이란?어떤 그래프에서, vertex s로부터 v까지의 path가 존재하는지 알아내는 것이다.ex) 특정 도시에서 한 도시로 갈 수 있는가? / 나와 특정 사람 간에 페이스북 친구들을 매개로 이어질 수 있는가? 등DFS(Depth-First Search; 깊이 우선 탐색)미로 찾기DFS에 대해 알아보기 전에, 여러 통행로(passage)와 교차로(intersection)들로 구성된 미로 속에서 길을 찾는 모습을 떠올려 보자. 미로에서 길 찾는 문제를 해결하는 방법으로 Tremaux exploration이라는 것이 있는데, 과정은 다음과 같다.▪︎ 아직 방문하지 않은 통행로 중 아무 곳이나 가본다. 처음으로 지나가는 통행로에는 길을 따라 선을 그어 놓는다.▪︎ 방문한 모든.. 2019. 1. 7.
그래프(Graph)란? 그래프(Graph)란, 다음의 2가지 요소로 구성된 자료구조이다. 1. vertex(혹은 node)의 집합2. vertex 쌍을 잇는 각 edge(간선)들의 모음 그래프에 V개의 vertex가 있을 때, 각 vertex는 0부터 V-1까지의 숫자로 이름 붙인다. 각 vertex를 잇는 edge는 v-w 혹은 (v,w)와 같이 표현한다. 그래프는 단지 vertex들의 집합과 edge들의 모음일 뿐이라는 것을 기억한다면, 위의 두 그래프는 완전히 동일하다는 것을 알 수 있을 것이다. 그래프 개념은 실생활의 많은 곳에서 사용되는데, 지도, 웹 상의 링크, 전자회로, 스케줄링, 전자상거래, 매칭, 컴퓨터 네트워크, 소셜 네트워크 등에 폭넓게 적용된다. 적용 분야에 대한 자세한 내용은 여기를 참고하자. 그래프를 .. 2019. 1. 6.
Counting Sort (계수 정렬) Counting Sort(계수 정렬)에서 주목할 만한 점은, 이전까지 살펴봤던 다른 정렬 알고리즘들은 특정한 data type에 대한 가정을 따로 세우지 않았다. 하지만 지금 살펴 볼 Counting Sort는 정렬할 data의 type에 대한 가정을 세우고 시작한다. 무슨 말일까? 먼저 Counting Sort가 어떻게 동작하는지 몇 가지 사항을 간단히 살펴보자. 정렬할 data의 type에 대한 가정을 세운다.값들 끼리의 비교가 없다. 정렬이 끝날 때까지, 비교는 한 번도 이루어지지 않는다. — 대부분의 정렬 알고리즘은 요소 사이의 비교를 필요로 하고(comparison-based), O(NlogN) 이상의 성능을 기대할 수 없다. Counting Sort는 비교 대신 추가적인 배열을 이용하여, 시간.. 2018. 4. 7.
Quick Sort (퀵 정렬) 퀵정렬은 임의의 한 요소(pivot이라 칭함)를 정한 뒤, pivot의 왼쪽에는 pivot보다 작은 것들만, 오른쪽에는 pivot보다 큰 것들만 오게 만드는 Divide & Conquer 알고리즘이다. Quick Sort 내부에서 divide, 즉 partition하는 과정에 있어 크게 두 가지 접근법이 있다.1) Hoare's Partition Scheme2) Lomuto's Partition Scheme 먼저 Hoare's Partition Scheme에 대해 살펴보자.전체 과정을 정리해 보면 다음과 같다. 특히 Partition 과정을 집중적으로 보도록 하자, 1. 배열의 첫 인덱스를 start로, 길이를 end로 하여 quickSort()를 호출한다. end는 배열의 마지막 index가 아닌 배열.. 2018. 4. 6.
Merge Sort (합병 정렬) merge할 때 추가적인 배열이 필요하므로, 제자리 정렬(in-place)이 아니다.시간 복잡도는 O(NlogN)이다. 절반씩 split하므로 logN에 요소의 개수만큼 비교하고 합병하므로 N을 곱한다.안정적이다(stable). 왼쪽 절반과 오른쪽 절반의 인덱스 i와 j 위치에 있는 요소를 비교하여, 같으면 위치를 바꾸지 않고 순서를 그대로 유지한다. 2018. 3. 30.
Insertion Sort (삽입 정렬) / Shell Sort (셸 정렬) Insertion Sort (삽입 정렬) 앞서 본 다른 정렬 알고리즘과 마찬가지로, 삽입 정렬도 '정렬된 부분'과 '정렬되지 않은 부분'으로 나뉘는데, 진행 방향은 왼쪽에서 오른쪽으로 가는 것으로 하자. 다음과 같은 배열이 있다. 인덱스는 0부터 시작한다. 20 35 -15 7 55 1 -22 먼저 0번째 요소는 정렬된 부분으로 가정한다. 하나 밖에 없으니까.주황색은 정렬된 부분, 초록색은 정렬되지 않은 부분이다. 2035 -15 7 55 1 -22 정렬되지 않은 부분의 맨 왼쪽 인덱스(firstUnsortedIndex; 위의 경우 1)에 위치한 요소(newElement; 위의 경우 35)를, 정렬된 부분의 맨 오른쪽 요소(i)부터 왼쪽으로 하나씩 비교한다. 비교하면서 newElement보다 큰 요소가 .. 2018. 3. 6.
Bubble Sort (버블 정렬) / Selection Sort (선택 정렬) Bubble Sort (버블 정렬) visualization의 차이: (오름차순으로 정렬)배열의 요소들을 가로로 놓은 뒤 가장 큰 값부터 오른쪽으로 몰아가는 방식혹은 가장 작은 값을 찾아 왼쪽으로 몰아가는 방식세로로 놓고 가장 작은 값을 밑으로, 큰 값을 위쪽으로 놓는 방식 등 결과는 똑같다. public class Main { public static void main(String[] args) { int[] intArray = { 20, 35, -15, 7, 55, 1, -22 }; // 버블 정렬 for (int lastUnsortedIndex = intArray.length - 1; lastUnsortedIndex > 0; lastUnsortedIndex--) { for (int i = 0; i .. 2018. 3. 5.

티스토리툴바