분할정복
-
알고리즘: Dynamic programming을 이용한 이항계수(Binomial Coefficient) (feat.c++)알고리즘 2020. 10. 2. 15:39
이항계수는 다음과 같이 표현되며 다음과 같은 성질을 따른다. int binomial(int n, int k) { if (k == 0 || k == n) { return 1; } return binomial(n - 1, k) + binomial(n - 1, k - 1); } 이렇게 간단하게 구현 가능하지만, 효율적이지는 않다. 알고리즘을 재귀호출하면서 이미 했던 계산을 반복해서 수행하기 때문이다 하지만 동적프로그래밍을 이용하면 중복되는 부분을 커버하여 효율적인 알고리즘을 만들 수 있다. Divide and conquer가 top-down 방식이였다면 dyna..
-
알고리즘: 큰 수의 곱셈 알고리즘(feat. c++ pseudocode )알고리즘 2020. 9. 27. 19:11
빅데이터 시대에서는 엄청나게 큰 숫자를 다루는 일이 존재한다. 하지만 자료형들은 수를 담을 수 있는 한계가 존재하고 배열로 표현함으로써 더 큰 정수를 표현할 수 있다. 예를 들어, S[5]S[4]S[3]S[2]S[1] = 92420로 표현할 수 있다. 이런 방식으로 표현한다면 표현하지 못할 수는 없다. 하지만 큰 수만 표현할 수 있으면 뭐하냐 효율적으로 연산이 가능해야 한다. 큰 수의 덧셈뺄셈은 많은 시간복잡도를 잡아먹지는 않지만, 곱셈의 경우에는 단순한 방법으로 quadratic-time algorithm(두개의 반복문)을 이용하여 곱셈으로 자릿수를 표현하면 시간복잡도는 다음과 같다. 하지만 이보다 더 좋은 큰자리수 곱셈알고리즘이 존재한다. 분할정복으로 이 보다 더 좋은 차수의 큰 정수 곱셈을 만들어보..
-
알고리즘: Divide and conquer를 이용한 quick sort 구현 (feat. c++)알고리즘 2020. 9. 27. 11:27
이름은 빠른 정렬이지만 사실상 가장빠른 정렬 알고리즘이라고 할 수는 없다. 차라리 분할교환정렬(partition exchange sort)라고 하는게 더 정확하다. 이번 포스팅은 quick sort를 분할 정복으로 구현한다. 사실상 quick sort 분할정복구현에는 가중치가 분할 > 정복이다. 즉 정복에는 별거 없다. 하지만 분할과정이 까다롭다. quick sort를 분할 정복으로 다음과 같이 나눈다. 배열의 원소 중 하나를 pivot으로 잡는다. (어떤 값을 pivot으로 잡든 상관 없다. 단지 기준을 만들어주기 위함이다) 주로 배열의 가장 끝값이나 처음 값을 기준으로 잡는다. 예를 들어 다음과 같은 배열이 있다. array = { 6, 2, 5, 3, 7, 10..
-
알고리즘: 예제를 풀어보자! (feat. 투자의 귀재 규식이)(Brute force, Divide and conquer)알고리즘 2020. 7. 13. 20:04
규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이스북과 인스타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠. 계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max를 작성해 보려고 합니다. 우선 함수 sublist_max는 파라미터로 며칠 동안의 수익이 담겨 있습니다. 예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 날에는 4달러를 벌었고, 마지막 날에는 8달러를 잃은 거죠. 먼저 이 문제를 Brute Force 방법을 이용해서 이 문제를 한 번 풀어봅시다! 1...
-
알고리즘: 분할 정복(Divide And Conquer) 예제 공부하기! (합병 정렬, 퀵 정렬)알고리즘 2020. 7. 10. 17:39
분할 정복(Divide and conquer)이란? 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식. 분할 정복은 다음과 같은 절차를 거친다. 1. Divide 2개 이상의 작은 문제들로 쪼갠다. 2. Conquer 나누어진 작은 문제들을 푼다. 3. Combine 나누어 해결한 문제들을 합친다. 1. 1부터 n까지의 합 (1 + 2 + 3 + ... + n) def consecutive_sum(start, end): if start == end: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid + 1,..