본문 바로가기

CS

 (27)
[Lecture] Greedy Algorithms, Minimum Spanning Tree Greedy Algorithm 답을 찾기 위해 선택을 반복하는 알고리즘들 중 비교적 간단한 방법으로 선택하고, 선택한 후 바꾸지 않는 알고리즘이다 selection sort도 가장 작은 숫자를 맨 앞으로 보내고 뒤돌아보지 않기 때문에 greedy이다 shortest path는 보통 greedy algorithm으로 문제를 해결한다 (edge weight = 비용) 노드가 n개이면, edge는 n-1개이다 shortest path는 결국 edge n-1개를 구하는 문제이다 Greedy Algorithm은 항상 해결 가능한 알고리즘인가? Minimum Spanning Tree 모든 노드를 포함하는(span:덮다) 트리를 찾는데 비용이 최소화되도록(minimum) 하는 것이다 Prim Algorithm 1. ..
[Lecture] Sum, Binary Search, Selection Sort A Simple Code & A Simpler Code 첫번째 그림: 일반적으로 누적합을 구할 수 있는 코드 두번째 그림 : 재귀로 누적합을 구할 수 있는 코드 두번째 그림의 코드가 맞는지 증명해보자 수학적 귀납법 : sum(x)는 1+2+...+x를 항상 리턴한다 base: P(1) 즉, 코드에 1을 넣었을 때 return값은 1이다 따라서 sum(1)이 리턴하는 값은 1임을 알 수 있다 step: 코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴한다 sum(x-1)의 리턴값은 1+2+...(x-1)와 같다고 할 때, sum(x)는 1+2+....+x를 리턴한다는 것을 확인할 수 있다 Binary Search & Recursive Binary Search 시간 복잡도 : O(n) (첫번째 코드..
[Lecture] The Halting Problem, 수학적 귀납법 Halting Problem Q : 프로그램 M과 입력 X가 있을때, M에 입력 X를 주고 수행시키면 종료할 것인가? A : 특수한 경우는 알 수 있으나, 모두 알 수 있다고 확신할 수 없다 돌려봤을 때, 언제 끝날지 모르기 때문에 '무한루프'가 절대로 안끝난다는 것을 확신할 수 없기 때문이다 어떤 프로그램이 종료하는지 알 수 있는 방법이 있을까? D(M,X)은 프로그램 M에 X를 입력했을 때 멈추면(exit) Yes, 멈추지 않으면(loop) No 중 하나를 출력하고 항상 멈추는 프로그램이라고 가정하자 이해하기 쉽도록 exit - yes, loop - no를 사용한다 D라는 프로그램이 있으면, D' ,S 프로그램을 만들 수 있다 D'은 입력값에 의해 종료하면 프로그램을 실행하고, 종료하지 않을 경우 프..

티스토리툴바