CS/알고리즘 (4) 썸네일형 리스트형 [Sorting] 퀵 정렬 저번 포스팅에서는 분할 정복 알고리즘을 사용한 Merge Sort에 대해 알아보았다. 최악과 최선 모두 O(nlogn)의 시간 복잡도를 가지고 있어 데이터의 양이 많아도 항상 일정한 속도를 유지할 수 있다. Quick Sort 역시 분할 정복 알고리즘을 활용한 정렬방법이다. 나누는 기준점에 따라 최악의 경우 O(n^2)이 걸리기도 하지만 보통 O(nlogn)의 시간이 걸린다. 그럼에도 불구하고 퀵 정렬은 높은 효율을 보인다. 더 깊이 알아보도록 하자. Quick Sort 데이터 집합에서 하나의 Pivot(기준점 데이터)을 잡는다. 왼쪽에는 Pivot보다 작은 값을, 오른쪽에는 Pivot보다 큰 값들로 나누어 분리한다. 분리가 되었다면 Pivot의 데이터는 자신의 위치를 찾게 된다. 이후 다시 정렬이 안된.. [Sorting] 병합정렬 지난 포스팅(버블, 선택, 삽입 정렬)에 이어 오늘은 Merge Sort에 대해 알아보려고 한다. Merge Sort는 분할정복 알고리즘 중 하나로 최소 단위로 쪼개고 병합하는 과정에서 정렬이 이루어진다. Merge Sort의 시간복잡도의 경우 최악, 평균, 최선 모두 O(nlogn)의 시간복잡도를 가진다. Merge Sort 병합정렬로 최소단위까지 나눈 후 다시 결합시키면서 정렬해 가는 알고리즘으로 Merge Sort는 분할정복 알고리즘을 사용한 정렬방법이다. Not In Place Sorting : 추가적인 메모리 공간이 필요하므로 제자리 정렬이 아니다. Stable Sorting : 중복된 데이터를 순서대로 정렬 정렬 과정 데이터 집합을 N/2씩 최소 단위가 될 때까지 나눈다.(마지막 2개에서 1개.. [Sorting] 버블정렬, 선택정렬, 삽입정렬 정렬은 데이터의 집합을 특정 기준을 두고 우선 순위에 맞게 데이터를 저장하는 것이다. 대표적인 예로 오름차순과 내림차순이 있다. 정렬에도 다양한 알고리즘이 있지만 오늘은 정렬하는데 O(n^2)의 시간이 필요한 Bubble, Selection, Insertion Sorting에 알아보려고 한다. Bubble Sorting 버블 정렬은 서로 인접한 두 데이터를 비교하고 조건에 맞지 않으면 두 데이터의 위치를 바꾼다. 그러면서 모든 데이터들이 조건에 맞는 위치에 찾아가게 된다. In-place Sorting(제자리 정렬) - 추가적인 메모리 공간을 필요로 하지 않음 Stable Sorting(안정 정렬) 정렬과정 화살표는 현재 비교하려는 데이터이고 항상 자신의 오른쪽 데이터와 비교를 한다. 따라서 화살표가 가.. 하노이 탑 문제 해결하기 문제 설명 세개의 탑이 있고 반경이 서로 다른 n개의 원반이 있다. 1. 한 번에 하나의 원반만 옮길 수 있다. 2. 쌓여있는 원반은 항상 아래의 원반보다 위의 원반이 작아야한다. 3. n개의 원반을 A에서 C로 옮겨라. 원반의 이동 횟수를 최소화하면서 이동 순서를 출력하라 문제 접근 위의 조건을 만족하며 n개의 원반을 C로 이동시키기 위해서는 반복적인 동작을 필요로 한다. 원반의 개수가 짝수인 경우 첫번째 원반을 B로 이동시키고, 홀수인 경우 C로 이동시키면서 처리하게 된다. 크게 생각해보면 n번의 원반을 C로 옮기기 위해서는 1부터 n-1번까지의 원반이 B에 위치해 있어야 한다. 즉 이 부분을 재귀적으로 처리한다면 문제를 쉽게 해결할 수 있다. 문제 해결 1. n번의 원반을 목적지(C)로 옮기기 위해.. 이전 1 다음
