[알고리즘] 알고리즘 시험대비 (중간, 기말 합본)

소개글

제가 손수 정리한 알고리즘 시험 대비 입니다.
풀이 과정이 상세하게 정리되어 있습니다.

목차

중간고사
Chapter 1 ~ Chapter 3
기말고사
Chapter 4 ~ Chapter 8

본문내용

Chapter 1. 효율, 분석 그리고 차수

1. non-decreasing order : 비내림차순 (같은 수가 존재하는 것을 허용한다)
2. sequential 과 binary
순차 검색을 할 경우에는 최대 n번 검색을 해야 하지만
이진 검색을 할 경우 최대 번만큼만 검사하면 된다.
3. n번째 Fibonacci 항 구하기 (재귀적)
T(n) > 2 × T(n-2)
> 2 × 2 × T(n-4)
> 2 × 2 × 2 × T(n-6)
.....
> 2 × 2 × 2 × ... × 2 × T(0) = (2가 번 곱해진다)
귀납법으로 증명
T(2) = 3 > 2 =
T(3) = 5 > 2.83 =
일 때, T(m) > 이란 걸 가정한다
T(n) = T(n-1) + T(n-2) + 1 (비교하는데 한번)
>
> = =
4. n 번째 Fibonacci 항 구하기 (반복적) - 이전 항들의 값들을 저장해서 쓰기 때문에 n+1 번 계산한다.
5. 알고리즘 분석
CPU에서의 실제 작동시간은 구하지 않는다. ...~~
단위 연산이 수행되는 횟수를 입력의 크기에 대한 함수로 구하여 알고리즘의 효율성을 분석한다.
보통 알고리즘에서 입력의 크기를 재는 기준 - 입력 크기(input size)

참고 자료

없음

압축파일 내 파일목록

알고리즘기말고사대비.hwp
알고리즘중간고사대비.hwp