알고리즘 검색 결과

해당 글 51건
병합 정렬 : sorting 된 두 배열을 합치면서 해결한다.

병합 정렬 (merge sort)는, 분할을 하고, 정복하는 단계에서 정렬된 두 배열을 합치는 식으로 동작합니다. 추가적인 공간이, 배열 크기만큼 필요하다는 것을 생각해 본다면, 메리트가 없을 수도 있어요. 실제로, Quick이 merge보다 빠르다는 이야기도 있을 정도이니까요. 그런데, Quick이 최악의 경우에 제곱에 비례하는 시간이 걸리는 반면에, merge는 그렇지 않아요. depth가 logn이기 때문입니다. 실제로 머지는 최악이던 최선이던 O(nlogn)에 동작합니다. 버블이나, insertion, selection sort에 비하면 꽤 빠릅니다. 일단 정렬이 된 두 부분 배열이 있다고 해 봅시다. 즉, le에서 mid까지 정렬이 되어 있고, mid+1부터 ri까지 sorting이 되어 있습니..
자료알고/알고리즘 2019. 7. 30. 20:46
lower_bound, upper_bound 함수 : 정렬이 되어 있다면 쓸 수 있다.

이분 탐색을 할 때 유용한 2가지 함수를 소개해 드리고자 합니다. c++의 헤더에는 lower_bound 함수가 있어요. 그리고 upper_bound 함수가 있는데요. random 접근이 가능한 경우, O(log)에 수행하게 해 주는 함수입니다. lower_bound(first_iter,last_iter,key); upper_bound(first_iter,last_iter,key); 대충 요약하면 [first_iter, last_iter)에 대해서, key값보다 크거나 같은 최초의 위치, key 값보다 큰 최초의 위치를 리턴하는데요. iterator를 리턴해요. 위치를 리턴한다는 것입니다. 물론, Object를 lower_bound, upper_bound를 써야 할 경우도 종종 있는데요. 이러한 경우, ..
레퍼런스/예제 2019. 7. 25. 18:13
버블 정렬 알고리즘 : 인접한 원소들을 비교하면서 진행한다.

정렬 알고리즘 중, 버블 정렬은 서로 이웃한 원소들끼리 비교하면서 우선 순위가 낮은 데이터를 뒤로 보내는 정렬을 합니다. 이것도, insert, selection과 같이 시간 복잡도는 O(n^2)인데요. 따로 처리를 하지 않는 이상, 어떠한 경우에도, 제곱에 비례하기 때문에, merge나 heap에 비해서는 거의 안 쓰인다고 보시면 되어요. 배열 [2, 1, 4, 5, 3]을 오름차순으로 정렬해 볼 겁니다. 그러면 수가 작을수록 우선 순위가 높고, 수가 클수록 우선 순위가 낮다는 이야기가 되겠어요. 인접한 두 수 a와 b가 있다면, a보다 b가 더 작다면, a랑 b를 바꾸는 식으로 동작할 듯 싶습니다. 배열이 이렇게 있어요. 아직 sorting 하기 전이에요. 총 5회전을 돌 건데요. 이것은 1회전입니다..
자료알고/알고리즘 2019. 7. 23. 23:17
부분합 구하기 : 누적합만 들고 있으면 된다.

1차원, 2차원 배열에서 구간이 주어졌을 때 어떻게 부분합을 구하는지 알아봅시다. 3차원 이상인 경우에는, 포함 배제의 원리를 알고 있어야 됩니다. 그렇기 때문에, 저는 1차, 2차원 array에서 subsum, 부분합을 구하는 것만 알려드리도록 하겠습니다. 먼저 누적합을 1차원에서 어떻게 구하는지 봅시다. 배열 arr이 있습니다. 제가 보라색으로 칠해놓은 것은 더미 데이터를 넣는데요. 0을 넣습니다. 0에 x를 더해도 0이기 때문입니다. 즉, 0은 덧셈에 대한 역원이기 때문에 보통 0으로 초기화를 합니다. nj[x]를 다음과 같이 정의합시다. 구간 [0,x]에 있는 수들의 합. 그렇다면 nj[0]의 값은 0입니다. 아무것도 없으니까 합이 0일 수 밖에 없기 때문입니다. 그러면 [0,x]까지의 합은 어떻..
자료알고/알고리즘 2019. 7. 21. 23:55
계수 정렬 (counting sort) : 특정 숫자의 빈도를 센다.

2가지 정렬을 배웠습니다. insert, select. 이 두 개는 키 값들을 비교를 했습니다. 2개의 값을 compare 했습니다. 제가 오늘 설명하는 counting sort, 계수 정렬은 이 둘과 크게 다른 점이 있는데요. 두 개의 키 값을 비교하지 않는다는 것입니다. 즉, 비교 기반 정렬이 아닙니다. 그러면 어떻게 구현을 할까요? arr = [3, 6, 3, 0, 4, 1]이라고 해 봅시다. 최솟값이 양수고, 최댓값 또한 적당히 작은 수라고 해 봅시다. co[x]를, 배열에서 x가 나타난 빈도수라고 정의합시다. 그러면, arr을 순회하면서, 어떠한 값 v가 나오면 co[v]의 값을 하나씩 증가시키면 될 거에요. 먼저 co 배열은 아래와 같이 초기화가 되어 있습니다. 1번째 원소를 봅니다. 3입니다..
자료알고/알고리즘 2019. 7. 20. 01:22