📌 탐욕적 알고리즘 Greedy Algorithm 탐욕적 알고리즘(Greedy Algorithm)은 동적 프로그래밍(Dynamic Programming) 얘기를 빼놓고서는 할 수 없다. 동적 프로그래밍은 나중에 또 하겠지만 간단히 설명하자면 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결방법을 결합해 최종 문제를 해결하는 방법이다. 즉, 동적프로그래밍은 사실상 문제를 해결하는 모든 방법을 탐색하므로 정확하지만 속도가 느릴 수 밖에 없다. 동적 프로그래밍의 느린 속도를 보완하고자 등장한 개념이 탐욕적 알고리즘이다. 탐욕적(Greedy), 말 그대로 현재 상황에서 당장 좋은 것만을 고르는 방법이다. 그 순간에 최적이라고 생각하는 결정을 한다. (미래를 전혀 고려하지 않음) 덕분에 그리디..
버킷정렬, 기수정렬, 계수정렬은 비교에 기반하지 않는 정렬 방법으로 시간복잡도 O(nlogn)보다 빠르게 구현하고자 제안된 정렬 알고리즘이다. 오늘은 기수정렬과 계수정렬에 대해 알아보고자 한다. 간단하니까 툭툭 치고 넘어간다. 📌 기수정렬 Radix Sort 기수정렬의 핵심은 낮은 자리에서 높은 자리로 기준을 바꾸어 가며 정렬하는 것이다. stable sort가 적용된 대표적인 정렬로 이전의 정렬 순서가 바뀌지 않는다. 실제로 정렬을 한다기보다 자릿수에 맞게 0~9까지의 버킷이 있고 이 버킷에 해당하는 자릿수를 포함한 수를 넣는 방식이다. 자리를 바꿔가며 버킷에 넣는 걸 반복하면 자동적으로 정렬이 되는 원리이다. 이때 버킷은 Queue(큐, First In First Out) 방식을 사용한다. 이때 이전..
📌 힙 정렬 힙 정렬은 1등을 뽑아내고 나머지 원소에서 계속 1등을 뽑아내는 정렬 알고리즘으로, 버블정렬과 비슷하다. 버블정렬은 1등(오름차순 정렬에서 가장 큰 수)을 뽑고 나서 이전의 1등들과 비교해야 한다. 그러나 힙정렬에서는 1등이 뽑힌 순서대로 다음은 자동으로 2등, 3등, ... 이렇게 되므로 1등을 뽑고 나서 추가적인 비교가 필요 없다. 매 라운드에서 한번 1등으로 뽑히면 그 원소는 이미 순서가 정해진 것이다. 남은 원소가 없을 때까지 반복적으로 1등을 뽑아내는 것이 핵심이다. 😶 버블정렬에 더 알아보고 싶다면 2020/12/30 - [코딩테스트/알고리즘 & 자료구조] - [알고리즘] 버블정렬 Bubble Sort (C++ 구현) [알고리즘] 버블정렬 Bubble Sort (C++ 구현) 코테..
📌 퀵정렬 퀵정렬은 가장 널리 쓰이는 정렬 알고리즘으로 말 그대로 빠른 정렬이 가능하다. 퀵 정렬도 병합정렬과 마찬가지로 분할정복기법을 이용한 알고리즘이다. 퀵 정렬의 핵심 아이디어는 특정 원소를 기준으로 작은 데이터와 큰 데이터를 분류한다는 것이다. 이렇게 되면 특정 원소를 기준으로 순서가 결정되며 분류된 작은 데이터와 큰 데이터 안에서 각각 기준 원소를 다시 정해 재귀적으로 쪼개나가면서 정렬해나간다. 병합정렬과 마찬가지로 단위를 쪼개나가는 아이디어이므로 분할정복기법이라고 할 수 있다. 이때 생각해봐야 할 것은 기준이 되는 원소(pivot)를 어떻게 정하느냐 인데, 1) 첫번째 원소를 기준으로 하거나 2) 랜덤으로 원소를 선택한다 첫번째 원소를 기준으로 할 경우 이미 정렬된 리스트의 경우 피봇의 한쪽에..
📌 병합정렬 병합정렬은 오름차순으로 정렬된 두 리스트 A, B의 병합으로 정렬해나가는 방식이다. 병합정렬은 대표적인 분할정복기법(Divide-and-Conquer) 중 하나로 문제를 작은 단위로 쪼개서 풀어나가는 방식이다. 분할정복기법을 사용한 정렬 알고리즘에는 병합정렬, 퀵정렬이 있다. 병합정렬에서 중요한 아이디어는 주어진 리스트를 일단 반으로 자르고 나중에 합치자는 것이다. 다음과 같은 두 가지 단계로 생각해볼 수 있다. 1) 분할정복기법에 맞게 병합정렬도 주어진 리스트를 원소 1인 리스트 여러 개로 쪼개지도록 자른다. 자르는 기준은 이진분할이다. 2) 모두 다 분할하여 주어진 원본 리스트의 길이 N만큼의 각 원소 리스트가 생성된다. 이 각 원소를 하나의 리스트로 간주하여 두 개씩 병합해 나가며 순차..
📌 삽입정렬 삽입정렬에서는 정렬대상이 될 원소를 두 부분으로 나누는 것이 핵심이다. 이미 정렬된 부분(왼쪽)과 정렬해야 하는 부분(오른쪽)으로 나누고 정렬해야 하는 부분의 첫번째 원소를 이미 정렬이 된 부분에 하나씩 삽입해 정렬한다. 즉, 정렬할 부분의 원소를 이미 정렬된 부분에 하나씩 삽입해 전체적으로 정렬된 부분의 비율을 키우는 것이다. 이미 정렬된 부분에 하나씩 삽입한다고 해서 '삽입'정렬이라고 부른다. 이때 삽입할 때는 이미 정렬된 부분의 가장 큰 원소(가장 오른쪽 원소)부터 비교해나간다. n = 5 인 { 8, 3, 9, 7, 6 } 배열을 오름차순으로 삽입정렬해본다. 이미 오름차순으로 정렬된 부분은 왼쪽에, 정렬되지 않은 부분은 오른쪽으로 두고 3부터 하나씩 삽입한다. 총 3, 9, 7, 6 ..
코테 문제를 풀면서 꼭 필요한 알고리즘 기법 중 하나가 정렬이라고 할 수 있다. 일반적으로 문제에 따라 (시간복잡도를 고려한) 적절한 정렬 알고리즘을 공식처럼 사용한다. 그 전에 자주 쓰는 정렬 알고리즘 종류와 시간복잡도를 계산했다. 📌 버블정렬 (Bubble Sorting) 맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬방식이다. 거품정렬이라고도 하며 두 인접한 원소를 비교하는 것이 핵심이다. 시간복잡도는 O(n^2)이지만 구현이 쉬워 자주 사용된다. TMI) 양방향으로 번갈아 수행하면 칵테일 정렬이라고 한다. 이해하기 쉽도록 { 8, 3, 9, 7 6 } 배열을 오름차순 정렬하는 것을 예로 들었다. 버블정렬은 이해하기도 쉽고 구현하기도 쉬워서 자주 쓰이..
