알고리즘설계와구조는 진짜 중요한 과목인데 내가 2학년 때 안 들었다. ;
3학년이 되고 나서야 이 강의를 수강하게 되었다.
짝수반 교수님이 다행히 내 지난 학기 SP를 가르치신 교수님이다. (학점 잘 주시는 교수님)
하~ 공부하기 싫다....
How can we solve a complicated problem efficiently using computers?
- Data Structure
- Algorithm
- Complexity (복잡도) : What is the time/space cost for executing the algorithm using particular data structures?
- Computability : Can the problem be solved by a computer?
알고리즘의 정의
- An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria:
- Input : zero or more quantities from the outisde
- Output : 최소한 하나의 output은 나와야 한다.
- Definiteness : 애매하면 안 된다.
- Finiteness : 끝나야 한다.
- Effectiveness
Post's correspondence problem
- 유한한 집합 P = {(a, baa), (ab, aa), (bba,bb)}를 고려해 보자. 이 P가 match가 존재하는가? 예를 들어, 시퀀스 (3,2,3,1)은 bbaabbbaa이므로 매치가 존재한다.
- 철수의 알고리즘은 다음과 같다. 길이가 1일 때부터 쭉 매치하며 비교한다. 매치가 존재할 경우 끝내고, 존재하지 않을 경우 길이를 1 늘린다. 이것이 알고리즘이라고 할 수 있을까? 답은 No. Finite 하지 않으므로 알고리즘이라고 할 수 없다.
Sequential Search vs. Binary Search
Algorithms and Their Time Complexities
Growth rates of some common Complexity Functions
