CVillain

다음 숫자들을 오름차순으로 정렬하시오. 2, 4, 5, 1, 3 앞의 선택 정렬과 버블 정렬은 시간 복잡도 O(N2)을 가지는 정렬 알고리즘이었다. 그렇다면 삽입 정렬의 시간 복잡도는 어떻게 될까? 우선, 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 동작한다. 선택 정렬, 버블 정렬은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 필요할 때만 위치를 바꾸게 된다. 그럼 앞선 정렬 방식보다 효율적일까? 정답은 NO! 삽입 정렬은 기본적으로 '정렬이 되어있다고 가정'을 한다는 점에서 특정한 경우에 따라 굉장히 빠른 속도를 낼 수 있다. 하지만 반복문이 두 번 들어가있기 때문에 최악의 경우 시간 복잡도가 O(N2)이 될 수 있다. 그림으로 살펴보자! 처음 두 수 2, 5는 2가 더 앞에 있으므로 ..

다음 숫자들을 오름차순으로 정렬하시오. 2, 5, 4, 1, 3 버블 정렬 또한 선택 정렬과 마찬가지로 몹시 직관적인 정렬 방법이다! 바로 옆에 있는 숫자를 비교해서 더 작은 숫자를 앞으로 보내는 방법으로 동작한다. ※ 버블 정렬은 정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘 그림으로 살펴보자! 먼저 첫 번째 자리를 구하는 방법이다. 바로 옆에 있는 숫자와 비교해서 더 작은 숫자를 앞으로 보냈다. 두 번째 자리 숫자를 구하는 방법도 같다. 첫 번째 자리는 구했으므로 두 번째까지만 비교를 한다. 계속해서 세 번째 자리를 구해보면 다음과 같다. 이미 정렬이 되었으므로 네 번째 자리는 바꿀 필요가 없다. 코드로 확인해보면 다음과 같다. public class Main { public st..

다음 숫자들을 오름차순으로 정렬하시오. 2, 5, 4, 1, 3 선택 정렬은 가장 직관적인 정렬 방법이다. 숫자들 중 가장 작은 수를 제일 앞으로 보내는 방법으로 동작한다. 그림으로 살펴보자! 숫자들 중 가장 작은 1을 제일 앞의 2와 자리를 바꿨다. 가장 작은 자리를 찾았으니 다음으로 작은 숫자를 찾는다. 남은 숫자들 중에 가장 작은 2를 5와 교체한다. 다음 작은 수인 3과 4를 바꾼다. 마지막으로 4와 5의 자리를 바꾸면 오름차순으로 정렬된 것을 알 수 있다. 코드로 확인해보면, public class Main { public static void main(String[] args) { int[] arr = {2, 5, 4, 1, 3}; int min; for(int i=0; i

정의 및 응용 n번째 카탈란 수(Catalan number) Cn이란 아래의 점화식을 만족하는 수열의 n번째 항을 말한다. $$ C_0 = 1, \quad C_n = \sum_{i=0}^{n} C_i C_{n-i}, \ n \geq 0. \tag{1.1} $$ 이 수열의 첫 10개 항을 나열하면 다음과 같다. (C0부터 C9까지) 1, 1, 2, 5, 14, 43, 132, 429, 1430, 4862, ··· 카탈란 수는 조합론(Combinatorics)에서 빈번하게 등장하는 수 중의 하나로, 아래와 같은 문제들의 해답이 모두 n번째 카탈란 수 Cn으로 주어진다. 먼저 C4= 14 라는 사실을 기억하자. Cn은 n쌍의 여는 괄호와 닫는 괄호로 만들 수 있는 올바른 괄호 구조의 가짓수와 같다. 예를 들어..