문제해결법

✏컴퓨터로 문제해결하기

✔Problem: 인풋과 아웃풋을 정확히 파악하는 것이 중요하다.

✔Strategy: 문제풀이 전략을 결정한다.

✔Algorithm: 알고리즘 디자인 - input, output, step

✔Analysis: 분석

✔Correctness (정확성), time and space, optimality(최적성 - 이것보다 더 적합한 알고리즘이 있는지)

 

✏알고리즘을 표현하는 2가지 방법

✔수도코드

✔순서도 (flow chart)

 

✏점근적 분석법

✔데이터의 개수가 n일 때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 방법이다.

✔worst case: 찾는 값이 마지막에 있거나 아예 없을 때. 최대로 수행했을 때의 경우이다 (n번).

 

✏분석에 쓰이는 수학공식

✔연속 정수의 합

✔다항급수

✔부정적분

✔멱급수 (복잡한 복잡도 계산에 한번씩 나옴)

✏Proof

✔counterexample: 반례 들기

✔contraposition: 대우법 - 원래 명제와 대우명제는 참, 거짓이 항상 같다는 것을 이용해서 증명

✔contradiction: 귀류법 - 모순을 보여줘서 증명한다.

   - ex) 실수는 유리수와 무리수로 나뉜다. 이것을 이용해서 무리수임을 추측하기 위해 유리수라 가정함.

✔mathematical induction: 수학적 귀납법