전체 글

Algorithm
[#2-2]분할정복-예제: 카라츠바의 빠른 곱셈 알고리즘
러시아의 Karatsuba가 만들어서 Karatsuba(이름이 너무 어려워;;) 알고리즘이라고 한다. Karatsuba의 빠른 곱셈 알고리즘이 대단한 이유는 간단히 설명하면 보통 곱하기를 코딩으로 작성할 때 이중 포문으로 곱해서 자릿수 올림을 사용하여 계산한다고 생각한다. Karatsuba는 이것보다 더 빠른 알고리즘(4번 곱할걸 3번으로!)을 작성하였다. Karatsuba의 빠른 곱셈 알고리즘은 일단 곱할려는 두 수 a, b를 둘 다 반으로 쪼갠다. 여기서 Karatsuba는 이걸 곱해서 4개의 조각으로 만들 생각을 하였다. 그렇게 나온 식이 밑에 사진이다. 그런데 이 상태에서 분할정복을 실행할 경우 시간 복잡도가 O(n^2)이 나오기 때문에 분할 정복을 사용하는 의미가 없어 Karatsuba는 고민을..
→2021.09.05
Algorithm
[#2-1]분할 정복-예제: 수열의 빠른 합과 행렬의 빠른 제곱
분할 정복의 첫 번째 예제이다. 책 앞에 분할 정복에 대한 설명은 자세히 설명되어 있으므로 생략하겠다. 첫 번째 예제인 수열의 빠른 합과 행렬의 빠른 제곱을 구하는 문제인데 우리는 이 문제를 분할 정복으로 풀기 위해서 1+2+.... N까지의 합을 반으로 쪼갤 것이다. 그러면 이렇게 보기 좋은 식이 나온다. 그런데 우리는 분할정복을 해야 하니까 기저 사례로 가서 1로 만나면 분할이 완료가 되었다고 코딩을 해야 하는데 저렇게 되어버리면 ((n/2)+1).....+ N) 부분이 a부터 b까지의 합 형식으로 표현이 되어 있어서 분할 정복으로 사용하기 불편하므로 식을 바꿔주어야 한다. 위에 나온 식을 첫 번째 사진 fastSum(x) 형식으로 바꾸어 주면? 이렇게 식이 정리되고 밑에 사진처럼 정의할 수 있다. ..
→2021.09.05
Algorithm
[#1]완전탐색-n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
일주일 만에 겨우 한 단원을 끝냈다. 말도 안 되는 공부 효율성이다. 일단 이 책을 읽는 순간 나의 두뇌에 대한 남 탓과 자괴감이 동시에 생기며 분노가 차오른다. 하지만 변태적 성향인지 이 책을 읽는 동안 재미가 없었던 순간이 없었고 끝까지 읽을 수 있을 거라는 확신이 든다. (시간에 대한 효율성은...) 이 단원에서는 완전탐색을 다루며 전체적으로 재귀 함수의 사용법과 시력을 향상한다. 사고 향상에 엄청난 도움을 주었다. 첫 번째 문제 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #inclu..
→2021.09.05

• 이전
• 1
• ···
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• ···
• 57
• 다음