본문 바로가기

분류 전체보기

 (143)
31. Merge Sort 이번에는 $\Theta(n^2)$보다 빠른 시간복잡도를 갖는 정렬 방법을 알아보자. 그중 가장 간단하다고 할 수 있는 병합 정렬(합병 정렬, Merge Sort)은 데이터를 여러 구간으로 분할한 후 각각의 구간을 정렬한 후 합치는 방법으로 데이터를 정렬한다. 분할 정복을 이용한 정렬 방법으로 볼 수도 있다. (사실 시간복잡도가 $\Theta(n\text{ lg }n)$인 정렬 알고리즘들 대부분이 분할 정복을 기반으로 하지만 병합 정렬에서 그 특징이 가장 두드러진다고 할 수 있다.) 다음은 병합 정렬 과정을 시뮬레이션한 것이다. 그림으로 도식화하면 다음과 같다. 시뮬레이션에서도 알 수 있듯이 원소 $n$개의 정렬과 병합을 $\Theta(n)$ 시간에 수행할 수 있기 때문에 시간복잡도가 $\Theta(n\t..
30. Insertion Sort 삽입 정렬(Insertion Sort)은 각각의 원소를 이전에 정렬한 앞쪽 원소들과 비교해서 맞는 위치에 추가하는 과정을 반복한다. 원소를 앞쪽에 추가하면 이전에 정렬된 원소 중 이번 원소가 추가될 자리 뒤쪽에 있는 원소들의 위치가 하나씩 뒤로 밀리게 되므로 단순히 각각의 원소를 바로 앞 원소부터 차례로 비교하면서 비교 관계가 바뀌었다면 서로 바꾸는 식으로 구현하면 된다. 다음은 이전 글에 예시로 나온 정렬을 C++에서 삽입 정렬로 구현한 코드이다. for(k = 0; k++ 1 && a[i - 1] > a[i]; i--)swap(a[i - 1], a[i]); } 이 코드는 굉장히 간단하고, 시간복잡도가 $O(n^2)$이라서 앞의 두 코드보다 약간 더 빠른 경우가..
29. Selection Sort 선택 정렬(Selection Sort)은 버블 정렬과는 다르게 비교 관계가 바뀐 쌍을 발견해도 바로 바꾸지 않고 마지막 값까지 확인한 다음 최솟값을 찾아서 제자리에 넣는 과정을 반복한다. 맨 처음에는 $1\text{~}n$번째 원소 중 가장 앞에 오는 것을 찾아서 첫 번째 원소와 바꾸고, 다음에는 $2\text{~}n$번째 원소 중 가장 앞에 오는 것을 찾아서 두 번째 원소와 바꾸고, 같은 방법으로 $(n-1)\text{~}n$번째 원소까지 확인하게 되면 정렬이 완료된다. 다음은 이전 글에 예시로 나온 정렬을 C++에서 선택 정렬로 구현한 코드이다. for(k = 1; k < n; k++) { for(i = m = k; i
28. Bubble Sort 버블 정렬(거품 정렬, Bubble Sort)은 가장 간단한 정렬 방법의 하나로 인접한 두 원소를 비교하는 과정을 반복한다. 처음에는 $1$번째와 $2$번째 원소를 비교하고, $2$번째와 $3$번째 원소를 비교하고, 이런 식으로 계속해서 비교하며 $(n-1)$번째와 $n$번째 원소를 비교한다. 만약 비교한 두 원소의 순서가 바뀌어 있다면 두 원소를 바꾼다. 이렇게 차례대로 한 번 비교를 실행하면 $n$번째 원소를 제자리에 넣을 수 있다. 이제 정렬해야 하는 원소는 $(n-1)$개이고, 다시 앞에서부터 비교를 실행하는데 이번에는 $(n-2)$번째와 $(n-1)$번째 원소를 비교하는 것까지 하면 된다. 이런 식으로 차례대로 한 번 비교를 실행할 때마다 원소 하나의 위치가 추가로 맞게 되고 이 과정을 $(n-..
27. Sorting & Search Intro 카테고리 B에서 기본적인 문제 해결 방법들을 차례로 소개했는데, 여기서 빠진 두 가지가 있다. 정렬(Sorting)과 탐색(Search)이다. 정렬은 데이터를 특정한 기준에 따라 순서대로 나열하는 것이고, 탐색은 데이터의 집합에서 특정 기준을 만족하는 데이터를 찾는 것이다. 정렬과 탐색은 다양한 알고리즘의 기본이 되는데, 예를 들어 그리디 문제에서 특정 기준에 따라 '가장 ~한 것'부터 처리하기 위해서는 데이터들을 그 기준에 따라 정렬해야 한다. 대부분의 프로그래밍 언어에서는 내장 정렬 함수와 일부 탐색 함수를 제공하기 때문에 그것들의 사용법을 익혀서 쓰는 것이 쉽고 정확하지만, 상황에 따라 적절한 방법을 선택하기 위해서는 다양한 정렬과 탐색 방법을 이해할 필요가 있다. 카테고리 C에서는 $8$가지의 주..
26. Bitmasks 비트마스크(Bitmasks)(비트마스킹(Bitmasking)으로 불리는 경우도 있음)는 Bool 값으로 표현할 수 있는 대상이 여러 개 존재할 때 이를 정수의 비트를 이용해서 표현하는 기법이다. Bool 값으로 표현할 수 있는 대상은 대비되는 두 개의 속성만을 가지고 있어야 한다. 예를 들어 참(True)과 거짓(False), 켜진 상태(ON)와 꺼진 상태(OFF), 선택한 상태와 선택하지 않은 상태 등이 있다. 일반적으로 $8$바이트 정수 자료형으로 $64$개의 비트를 한번에 표현할 수 있고 그보다 큰 정수 자료형이 잘 쓰이지 않기 때문에 이보다 적은 비트만을 사용해서 문제를 풀 수 있는 경우에 주로 사용되지만 정수 배열을 이용해서 더 많은 비트를 사용하고 메모리와 실행 시간의 측면에서 더 성능이 좋은..
25. Divide and Conquer 분할 정복(Divide and Conquer)은 큰 문제를 여러 개의 작은 부분 문제로 분할한 다음 각각의 부분 문제를 해결하고, 그 결과를 바탕으로 큰 문제의 답을 구하는 문제 해결 방법이다. 동적 계획법과 설명이 비슷하지만 동적 계획법에서는 중복되는 부분 문제가 있었다. 분할 정복의 부분 문제들은 서로 중복되지 않는다. 분할 정복에도 기저 사례가 존재하며, 기저 사례는 더 작은 부분 문제로 분할하지 않고 바로 해결할 수 있다. 분할 정복 자체가 재귀함수를 이용하여 구현하는 경우가 많기 때문에 코드에 자연스럽게 추가되기도 한다. BOJ 1629. 곱셈 (Silver I) 지수가 큰 경우의 거듭제곱을 구하는 문제가 분할 정복을 사용하는 대표적인 예시이다. 지수가 크기 때문에 $B$번 반복되는 반복문을 쓰..
24. Dynamic Programming & Memoization 재귀를 설명한 글의 끝부분에서 입력값이 조금만 커져도 재귀호출 횟수가 급격하게 늘어나는 문제점에 대해서 언급했는데, 이렇게 되는 이유는 중복되는 부분 문제를 계산하는 횟수가 너무 많기 때문이다. 이 문제를 풀어 보면 알 수 있지만 피보나치 수를 구하기 위해서 이 글에 나온 것처럼 코드를 짜면 함수 호출의 횟수 자체가 피보나치 수만큼 증가하기 때문에 이렇게 해서는 빠른 코드를 짤 수 없다. 하지만 중복되는 부분 문제를 살펴보면 중복되는 부분 문제에 대한 답이 항상 같기 때문에, 만약 어떤 부분 문제의 답을 계산했다면 그 계산 결과를 저장한 뒤 나중에 같은 부분 문제를 풀 때 기존에 계산한 답을 사용하면 되므로 성능을 크게 향상시킬 수 있다. 이러한 방법을 메모이제이션(Memoization)이라고 한다. (..

티스토리툴바