Algorithm (10) 썸네일형 리스트형 탐욕 알고리즘 (Greedy algorithm) 탐욕 알고리즘은 주어진 순간에 가장 최적의 경우를 선택하는 알고리즘이다.다시 말해, 현재 단계 관점에서 최선의 결정을 선택하는 것이다.따라서 지역적으로 최적을 선택하는 것이기 때문에, 문제에 따라, 최선의 접근법이 아닐 수도 있다. 만약 탐욕 알고리즘은 최선의 해를 내놓는다면, 보통 동적 프로그래밍(dynamic programming)이나 완전 탐색보다 빠르다.반대로, 최선의 해를 내놓지 못한다면, 동적 프로그래밍이나 완전 탐색이 최적의 접근법이 될 수 있다. 예시) 동전 교환문제주어진 동전을 가지고, 주어진 금액을 지불할 수 있는 최소 동전 개수를 찾는 문제.동전: [1, 2, 5]지불 금액: 6결과: 동전(1) 1개, 동전(5) 1개 이 문제는 동전이 어떻게 주어지냐에 따라, 그리디 알고리즘이 최적.. 이진 탐색 (Binary Search Algorithm) 검색 범위를 줄여나가면서, 원하는 데이터를 찾는 전체 탐색 알고리즘이다.시간복잡도는 log2N 으로 매우 빠르다.단점으로는 이미 정렬된 자료에 대해서만 사용할 수 있다. 예시) 16을 찾아보자. 1단계left index: 0right index: 14mid index: (0 + 14) / 2 = 7A[mid] 값이 찾고자 하는 값(17)보다 큰 지 작은지 확인한다. · · · · · · · · · · ①① 결과에 따라 검색 범위를 조정한다.만약 A[mid] 값이 찾고자 하는 값 보다 크다면, 찾고자 하는 값이 mid 보다 왼쪽에 있으므로,right 값을 수정한다. (right = mid - 1)만약 A[mid] 값이 찾고자 하는 값 보다 작다면, 찾고자 하는 값이 mid 보다 오른쪽.. 너비 우선 탐색 (BFS, Breadth First Search) 전체 탐색 방법 중 하나이다.너비 우선 탐색을 구현하기 위해서는 큐(Queue)를 사용해야 한다. Queue선입선출(FIFO, First In First Out) 자료구조.먼저 들어온 데이터가 먼저 나간다. 너비 우선 탐색시작 위치에서부터 차례로 인접한 노드를 탐색하는 방법이다. (이하 생략)이러한 탐색을 계속 반복하여, 모든 노드를 가까운 순서대로 탐색하는 방법이, 너비 우선 탐색이다. 최대공약수 구하기 (Binary Euclidean algorithm) 유클리드 알고리즘의 변형이다.스테인 알고리즘(Stein's Algorithm)이라고도 한다. 어째든 최대공약수를 찾는 알고리즘이다.매우 큰 정수를 다룰 때, 나머지 연산자를 이용한 유클리드 호제법보다 빠르다. 기본 원리모든 짝수는 2로 나눌 수 있다.경우의 수 표현(식)설명A, B 모두 짝수 일 때GCD(A, B) = 2 x GCD(A / 2, B / 2) 2를 공통인수로 가진다A만 짝수일 때GCD(A, B) = GCD(A / 2, B)한쪽이 홀수라면, 2는 공통인수가 될 수 없다. 따라서 짝수인 수만 2로 나누어도 GCD는 변하지 않는다B만 짝수일 때GCD(A, B) = GCD(A, B / 2) 두 수가 모두 홀수인 경우A(홀수) - B(홀수)는 반드시 짝수가 된다.유클리드 호제법의 원리와 동일하게 .. 최대공약수 구하기 (유클리드 호제법) 수학적 이론은 여기로 1. 뺄셈을 이용한 구현최악의 경우의 수: gcd(x, 1)시간복잡도: log(max(a,b))int gcd(int a, int b){ if (a == b) return a; if (a > b) return gcd(a - b, b); else return gcd(a, b - a);} 2. 나머지 연산자를 이용한 구현시간복잡도: log(a+b)int gcd(int a, int b){ if (a % b == 0) return b; else gcd(b, a % b);} 인수분해 (에라토스테네스의 체) 에라토스테스의 체는 소수를 찾는데 사용되지만, 약간의 변형을 통해, 합성수를 소인수분해 하는데 사용할 수 있다. 에라토스테네스의 체(Sieve of Eratosthenes)에 대한 내용은 여기로소수 찾기 C++ 코드는 여기로합성수 N의 소인수 중 하나가 P이면,N의 모든 소인수는 P와 NP의 분해로 이루어져 있다. 에라토스테네스의 체를 활용하면 최소 소인수를 기록해 두고, 활용할 수 있다. 예시) 123456789101112131415161718192000020202320202320202 1행은 숫자(N)을 의미한다.2행은 숫자(N)의 최소 소인수를 의미한다. 합성수 4의 최소 소인수는 2이다.합성수 6의 최소 소인수는 2이다.합성수 8의 최소 소인수는 2이다.합성수 9의 최소.. 소수 찾기 (에라토스테네스의 체) 소수 판별 알고리즘과 유사하지만, 목적이 다르다.소수 판별은 특정 수가 소수인지 아닌지 찾아내는 알고리즘이라면,소수 찾기는 주어진 범위 (0 ~ N)에 존재하는 소수를 찾아내는 알고리즘이다. 에라토스테네스의 체(Sieve of Eratosthenes)에 대한 내용은 여기로 위의 내용을 기반으로 작성된 코드이긴 하나, 약간의 최적화 과정을 거쳤다.#include #include using namespace std;int main(){ const int N = 30; vector A(N + 1, true); A[0] = A[1] = false; for(int i = 2; (i * i) 약수의 개수 구하기 수학적 이론은 여기로 int count_divisors(int n){ int i = 1; int result = 0; while(i * i 이전 1 2 다음 1/2
