Backtracking 되추적 알고리즘이라고 한다. 결과를 찾는 도중 막히면 다시 되돌아가서 다시 결과를 찾음. 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS vs Backtracking DFS는 모든 노드를 탐색한다. Backtracking은 모든 노드를 탐색하지만, 특정 조건을 설정해서 이 경로가 해가 안될 거라고 판단이 되면 경로를 이탈하고 다시 되돌아간다. --> 이것을 가지치기라고 한다. 가지치기를 통해서 불필요한 경로를 차단해서 효율성을 높일 수 있다. Promising 유망성 검사 - 이 경로가 특정조건을 걸어서 해가 될 것인지 안될 것인지 판단함. nonpromising 하다면, 그 경로는 끝까지 갈 필요가 없으므로, 다시 되돌아감. promising 하다면 계속 진행함. Prun..
●허프만 코드란? 데이터를 효율적으로 압축하기 위해서 만들어진 알고리즘. 탐욕법을 사용함. 데이터 파일은 통상적으로 이진 코드(binary code)로 표현한다. 각 문자는 코드 워드(code word)라고 하는 유일한 이진 문자열로 표현한다. ●fixed length binary code 각 문자를 표현하는 bit의 개수가 일정하다. 예를 들어 문자의 집합이 {a,b,c}라면 bit 2개만으로 문자를 코드화 할 수 있다. bit 2개로는 4개의 문자를 bit 3개로는 8개의 문자를 표현할 수 있다. a : 00 b:01 c:11 이라고 가정하자. 만약 File이 ababcbbbc라면 결과 코드는 000100011001010110일것이다. ->18비트를 사용한다. ●variable-length binar..
Knapsack Problem(배낭문제) 1)Fractional Knapsack Problem 보석의 무게를 쪼갤 수 있다는 가정을 둔다. 예를 들어 보석이 10kg라도 내가 들고가고싶은 만큼 담아서 가방에 넣을 수 있다. ->greedy를 이용해서 해결 2)0-1 Knapsack Problem 보석의 무게를 쪼 갤 수없다. 예를 들어 보석이 10kg라면 10kg 그대로 가방에 담아야 한다. ->dynamic programming을 이용해서 해결 배낭문제의 목표는 가방에 담는 보석들의 가치 합이 최대가 되야한다. ●Greedy Approach 탐욕법을 통한 전략은 다음과 같다. 단위 무게당 가치가 가장 큰 보석을 담는다. 가방에 최대 무게가 넘지않을때까지 보석을 담는다. 이러한 접근법은 보석을 쪼갤수있는..
Scheduling problem은 운영체제에서 다루는 개념이다. 최대한 적은 시간을 사용하면서 많은 작업을 해야 효율적이다 어떻게 하면 효율적으로 배치할 수 있을까? ●FCFS(First-come , First served) 들어온 순서대로 일을 시작한다. 도착 순서는 P1->P2->P3이라고 가정하자. FCFS의 방식은 p1이 먼저 도착했으니까 p1의 일을 다 끝내기 전까지 p2, p3는 일을 시작하지 못한다. P1, P2, P3의 모든 작업이 끝나는데 소요되는 시간은 30이지만, P1, P2, P3가 기다리는 시간은 24+27 = 51이다. p2, p3는 p1에 비해 굉장히 적은 시간을 사용하는 작업임에도 불구하고 p1이 끝날 때까지 기다려야 한다. 이러한 알고리즘은 굉장히 효율적이지 못하다. ●S..
알고리즘의 효율성을 분석 할때 시간복잡도를 많이 사용한다. 일반적으로, 알고리즘의 실행시간은 1.입력의 크기(input size)가 커지면 증가하고 2.총 실행시간은 단위연산(+,-,x,/)이 몇번 수행되는가에 비례한다. ● inputsize에만 영향을 받는 경우 #include using namespace std; int main() { int n, sum = 0; cin >> n; for (int i = 0; i n; for (int i = 0; i < n; i++) { F.push_back(i); } cout n; for (int i = 0; i < n; i++) { F.push_back(i); } cout
피보나치수열: 첫째항은 0 둘째 항이 1이며 그다음 항부터는 바로 앞 두항의 합이다. ex) 0,1,1,2,3,5,8,13,21,34,55,89 ㆍㆍㆍㆍㆍㆍ #include #include using namespace std; int fibo(int n); int main() { int n; cin >> n; cout > n; cout
