Ikjo's Technology blog

병합 정렬이란? 병합 정렬은 퀵 정렬과 마찬가지로 분할 정복 알고리즘으로서 주어진 데이터를 두 개의 균등한 크기로 분할하고 분할된 영역을 정렬한 후 병합해 나가는 방식으로 정렬한다. 이때 분할하고 병합하는 과정에서 기존 데이터 전체 크기와 동일한 추가적인 자료구조를 사용하므로 O(n)의 공간 복잡도를 가진다. 그림으로 병합 정렬 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 병합 정렬을 통해 오름차순으로 정렬해보자. 우선, 주어진 배열의 영역을 절반씩 분할해나가는데, 영역의 크기가 2개 이하가 될 때까지 분할해나간다. 이때 분할해나가는 과정은 마치 깊이 우선 탐색과도 같다. 분할을 해나가는 중 영역의 크기가 2개 이하가 됐을 경우 즉, 더 이상 분할할 게 없는 ..

퀵 정렬이란? 퀵 정렬은 주어진 데이터 상 특정 값(피벗)을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 옮겨 2개의 파티션(Partition)으로 분할(Divide)해 나가는 방식으로 정렬한다. 퀵 정렬에 사용되는 기법을 분할 정복 알고리즘(Divide and conquer algorithm)이라고 하는데, 이는 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 일반적으로 재귀 함수(Recursive function)를 통해 자연스럽게 구현된다. 퀵 정렬은 주어진 데이터 상 최초 피벗을 몇 번째 데이터로 정하는지에 따라 그리고 데이터 상태에 따라 다른 성능을 보일 수 있는데, 대표적으로 배열의 첫 번째 데이터를 피벗으로 정하는 호어 분할 방식이 있..

삽입 정렬이란? 삽입 정렬은 주어진 데이터들을 순회하면서 특정 데이터를 적절한 위치에 삽입하는 방식으로 정렬한다. 이때 마법의 단어 '적절한'이 들어갔는데, 이 단어가 이전에 다루었던 버블 정렬과 선택 정렬과의 차이를 낳는다. 이전에 다루었던 버블 정렬과 선택 정렬의 경우, 주어진 데이터의 정렬 상태 등에 상관없이 항상 모든 요소를 순회하면서 비교하는 비효율적인 문제가 있었다. 하지만 삽입 정렬의 경우, 순회 중 특정 데이터를 삽입할 적절한 위치를 찾으면 삽입 후 기존 순회를 중단하고 다음 순회로 넘어간다. 이로써 기존 데이터의 상태가 어느정도 정렬된 상태라면, 더욱 빠른 속도로 정렬할 수 있게 된다. 그림으로 삽입 정렬의 원리 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 ..

버블 정렬이란? 버블 정렬은 정렬 알고리즘 중에서 가장 원시적인 방법으로서 주어진 데이터들을 순회하면서 서로 붙어있는 2개의 데이터씩 비교해, 하나씩 맨 뒤에 차곡차곡 옮겨놓는 방식으로 정렬한다. 그림으로 버블 정렬의 원리 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 버블 정렬을 통해 오름차순으로 정렬해보자. 우선 맨 앞에서부터 서로 붙어있는 2개의 데이터씩 비교를 하는데, 작은 값을 왼쪽에 큰 값을 오른쪽에 옮겨나가면서 배열을 순회한다. 이때 순회의 마지막 지점에서 이루어지는 비교는 주어진 배열에서 가장 큰 값을 배열 맨 뒤에 옮겨놓는 것이 된다. 즉, 맨 마지막 요소는 정렬이 되었다고 볼 수 있으므로 맨 마지막 인덱스 직전까지 앞선 작업들을 반복해나간다. ..

이분 탐색이란? 우선 탐색이란 자료구조, 그래프 등에서 특정한 데이터를 찾는 것을 말한다. 대표적인 탐색 방법으로 '순차 탐색'이 있는데, 이는 어떤 자료구조에서 특정 데이터를 찾기 위해 첫 번째 원소부터 마지막 원소까지 차례대로 확인하는 방법으로 가장 정직한 탐색 방법이다. 하지만 이러한 순차 탐색의 시간 복잡도는 O(N)으로 데이터가 무수히 많은 경우에는 적합하지 않다. 이러한 경우에는 어떤 탐색 방법이 유용할까? 대표적으로 '이분 탐색'이 있다. 이분 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 시간 복잡도가 O(logN)으로 순차 탐색 보다 훨씬 유리한 방법이다. 다만 이분 탐색의 경우 '데이터가 정렬되어 있는 경우'에만 사용할 수 있다는 특징이 있다. 이분 탐색 구현해보기 여러 ..