CS 썸네일형 리스트형 [Introduction to Algorithms] 4. 분할정복 이번 장은 재귀를 통한 분할정복(Divide and conquer)을 다룬다. 재귀와 분할정복은 다른 포스팅에서 간략하게 다룬 적이 있다. 재귀 : https://codecpr.tistory.com/4 10/29 : 자료구조 Recursion 교재 : Data Structures and Abstraction with Java 챕터 : Chap 7 - Recursion Recursion : 문제를 풀기 위해서 문제를 작게 분리했는데, 반복적으로 이뤄지는 작업이라면 Recursion을 이용할 수 있다. Recursion.. codecpr.tistory.com 분할정복 [2.3 알고리즘의 설계 참고] : https://codecpr.tistory.com/24?category=516456 [Introductio.. 더보기 [Introduction to Algorithms] 3. 함수의 증가 3. 함수의 증가 앞서 배운 삽입정렬과 병합정렬의 수행시간을 생각해보자. 삽입정렬의 worst case는 $\mathsf{\Theta}(n^2)$이고, 병합정렬의 worst case는 $\mathsf{\Theta}(n \ lg \ n)$이었다. 그렇다면 병합정렬이 언제나 삽입정렬보다 우수한 알고리즘일까? 그것은 아니다. 이 표기는 상수와 저차항을 무시하여 표현된 것이기 때문이다. 만약 입력 n의 크기가 충분히 작다면, 상수와 저차항의 영향으로 오히려 삽입정렬이 더 우수한 결과를 내놓을 수도 있다. 반대로 입력의 크기가 충분히 커진다면, 상수와 저차항은 n에 묻혀버린다. 이렇듯 n의 크기에 따라 수행시간 표기가 역전되기도 한다. 그러나 역전이 가능한 경우의 수는 너무나도 적다. 또한, n이 작았을 때 얻을.. 더보기 [Introduction to Algorithms] 2. 시작하기 2. 시작하기 많은 알고리즘에서는 루프를 사용하여 문제를 해결하곤 한다. 우리는 코드가 문제없이 작성 되었다면, 그 루프가 정상적으로 작동하여 문제를 해결할 것을 알고 있다. 그러나 이를 논리적으로 증명하기는 어려웠다. 이때 사용할 수 있는 것이 루프 불변성(Loop Invariant)이다. 루프 불변성은 루프를 사용한 알고리즘이 타당(correct)한지 증명하기 위해 사용된다. 루프 불변성임을 확인하기 위해서는 세 가지 특성이 만족되어야 한다. 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면, 다음 반복이 시작되기 전까지도 계속 참이어야 한다. 종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을.. 더보기 [Introduction to Algorithms] 1. 알고리즘의 역할 1. 알고리즘의 역할 1.1 알고리즘 이 장에서는 우리가 알고리즘을 배우는 이유와 배워서 어떻게 사용할 수 있는지에 대해 간략하게 설명해준다. 먼저, 알고리즘이란 한 값을 입력받아 다른 값으로 출력하는 계산 절차라고 한다. 가장 대표적으로는 임의의 수열을 정렬시키는 정렬 기법이 있다. 여러 알고리즘을 익히고, 사용할 수 있게 된다면 더 훌륭한 프로그래머가 될 수 있을 것이다. 마치 요리사 지망생이 요리사가 되기 위해 많은 레시피를 배워가는 것처럼. 1.2 기술로서의 알고리즘 어떤 문제를 풀기 위해서 여러 개의 알고리즘을 구현했다고 했을 때, 가장 최적의 알고리즘을 선택하는 기준은 무엇이 있을까? 나는 효율성이 대표적인 기준이 될 수 있다고 생각한다. 효율이라는 것은 시간과 메모리 두 차원에서 생각해볼 수.. 더보기 유클리드 알고리즘 (Euclid’s algorithm) 유클리드 알고리즘 (혹은 유클리드 호제법)이란? 두 양의 정수 A, B에 대한 최대공약수를 구하는 알고리즘이다. 이는 O(log N) 으로 가장 효율적으로 GCD를 구한다. * 최대공약수(Greatest common divisor, GCD)란, A, B를 나누는 자연수 중에서 가장 큰 자연수를 말한다. * 호제법이란, 두 수가 서로 상대의 수를 나누어 원하는 수를 얻는 알고리즘을 말한다. 최대공약수는 다음과 같은 성질을 갖는다. 식에서 mod는 나머지를 구하는 모듈러 연산(%) 이다. 성질을 이용한 예시는 다음과 같다. 다음은 C++로 구현한 코드이다. int gcd(int a, int b) { if (b > 0) return gcd(b, a % b); return a; } 더보기 이전 1 다음
