분할 정복으로 정렬을 완성해가는 알고리즘이다. 알고리즘은 분할, 병합의 두 단계를 재귀 호출하는 것으로 완성되어 꽤 단순하게 구현할 수 있다. 그 유명한 폰 노이만 박사가 만든 알고리즘이다. 1. 병합 정렬(Merge sort)의 개념 원리는 앞서 말한 분할 정복(Divide and Conquer)이다. 문제 전체를 부분으로 쪼개서 하위 문제의 해를 찾아 상위 문제의 해를 얻는 방식으로 정렬에 적용하면 전체 길이의 배열을 절반, 다시 절반, 반복하여 나눌 수 없는 상태의 크기로 만들고 정렬이 끝난 부분들을 합쳐 정렬을 점차적으로 완성해나간다. 이 일을 진행할 때 코드에서 구현해야 하는 것은 두 가지다. 먼저 "분할"하는 것이고 분할된 것을 바르게 "병합"하는 것이다. 언제 분할하며 언제 병합하는지도 중요..

n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다. sum = 0 for i in range(1, k+1): sum += arr[i] print(sum) i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데? 그런데 배열 길이가 106, 테스트 케이스가 103개가 된다면 어떨까. 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicp..

해시 함수는 말 그대로 입력을 변환하는 함수다. 목적은 임의의 데이터를 정해진 크기의 데이터로 바꾸는 것이다. 어떤 크기의 값을 넣어도 정해진 크기로 바뀌니 데이터 관리에 유리한 면이 있다. 하지만 정보의 크기를 한정하는 함수이기 때문에 정보 손실은 불가피하고 이것 때문에 이 함수는 단방향 함수다. 해시 함수인 결과(해시 값)만을 가지고 원래 값이 무엇이었는지는 확실히 알 수 없다. 본문에서는 자료구조로서의 해시 함수를 다룬다. 1. 키(Key)와 해시(Hash) 키는 해시 함수에 입력되는 기존 값을, 해시는 그 결과 값을 말한다. 이름(3글자)을 키로 받아 각 글자의 획수로 바꿔보자. 이 방법으로 이름이 거의 대부분 3자리의 숫자로 반환된다. 이 과정에서 이름은 키, 반환된 3자리 숫자는 해시이다. 수..

배낭 문제는 정해진 비용 내에서 최적의 가치를 갖는 해를 찾는 문제다. 처음 이 문제를 접하는 사람들 대부분이 그리디로 접근하지만 그리디 알고리즘만으로는 해결할 수 없는 배낭 문제도 있다. 배낭 문제는 크게 두 유형으로 분류되는데 먼저 그리디 알고리즘을 적용할 수 있는 분할 가능한 배낭 문제와 그리디 알고리즘으로는 해결하기 어려운 0-1 배낭 문제가 있다. 1. 분할 가능한 배낭 문제 분할 가능한 배낭 문제는 말 그대로 가치와 비용을 분할해 가져올 수 있다. 예를 들어 10kg의 제한을 두고 배낭을 싸는데 5kg에 75의 가치를 가진 A와 4kg에 120의 가치를 가진 B, 7kg에 140의 가치를 가진 C가 있다고 해보자. 여기서 A, B, C 모두 원하는 만큼 쪼개서 가져갈 수 있는 물건이라고 가정하..

이진 탐색은 배열 속에 내가 원하는 자료가 있는지 찾는 방법이다. 탐색 구간을 둘로 나누어 실행하며 이를 반복해나가기 때문에 이진 탐색이라고 부른다. 책을 펼쳐서 내가 원하는 페이지를 찾는 과정과 아주 비슷하다. 우선 길이가 10인 arr이라는 배열이 아래와 같이 있다고 해보자. 배열이 정렬되어있지 않기 때문에 내가 원하는 값이 어디에 어떤 규칙으로 있는지 알 수 없다. 이 배열에서 자료를 찾으려면 앞에서부터 순차적으로 찾아야 한다. 이걸 선형 탐색(Linear Search)라고 한다. 8을 찾는다면 적당히 5번의 비교로 끝나겠지만 5를 찾는 경우 최악의 상황으로 배열 내 모든 데이터를 확인해야 한다. 따라서 이 방법은 시간 복잡도가 O(n)이다. 사실 이 정도의 시간복잡도가 그리 나쁘지는 않지만 배열의..

BFS는 그래프나 트리의 자료구조에 적용할 수 있는 맹목적 탐색 알고리즘이다. 맹목적 탐색은 주어진 정보에 따라 효율적인 탐색을 실시하는 것이 아닌 이미 정해진 순서로 탐색을 실시하는 방법으로 실용적으로 따져볼 때 매우 비효율적인 알고리즘이지만 구현이 쉽고 간단한 문제에 한해 아주 유용하다. 이름 그대로 트리에서 노드를 깊게 파고드는 것보다 한 계층을 순차적으로 모두 살펴보는 것을 우선하는 알고리즘이다. BFS는 Queue로 구현할 수 있다. 1. 탐색을 시작할 정점을 Queue에 삽입한다. 2. Queue가 비었다면 '9'로 이동한다. 3. Queue의 가장 위에 있는 정점이 현재 탐색 중인 정점이다. 4. 탐색 중인 정점이 찾으려는 자료이면 '8'로 이동한다. 5. 탐색 중인 정점과 연결된 정점을 Q..