4Legs_Archives

정렬(Sorting)이란? 정렬은 원소(element)들을 일정한 기준을 통해 순서대로 나열하는 것이다. 정렬은 탐색(Search), 병합(Merge) 등 정렬된 상태에서 올바르게 동작하는 다른 알고리즘을 최적화하는 데 중요한 역할을 한다. 정렬 알고리즘은 이러한 정렬을 진행하는 방식을 정의한 알고리즘을 말한다. 이번 포스팅에서는 기본적인 정렬 알고리즘 5가지에 대해 알아보자. 최악의 경우 (Worst case) Worst case는 정렬 알고리즘에 대해 일반적으로 시간복잡도에 대한 최악의 경우는 그 알고리즘이 최대 실행시간으로 동작하는 경우를 말한다. 공간 복잡도에 대해서는 알고리즘이 최대 메모리를 사용하며 동작하는 경우를 의미한다. 안정성 (Stability) 정렬 알고리즘이 안전성을 가진다는 것은 ..

문제 링크 : www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보�� www.acmicpc.net 예전에 풀었던 DP 문제인 '방번호' 문제와 비슷한 맥락의 문제이다. 가장 큰 수를 만들기 위해선, 각 숫자들을 최소 한 번씩 사용해야 하므로 숫자의 앞자리가 큰 순으로 붙여나간다. 각 숫자들을 최소 한 번씩 사용하고 난 뒤, 추가로 사용할 숫자는 가장 큰 수가 될 것이다. 즉, 입력으로 들어오는 숫자들을 어떻게 정렬할 것인지가 문제의 핵심이 된다. 추가로 사용할 숫..