쉽게 배우는 알고리즘 관계 중심의 사고법 솔루션 (문병로 저)

1장

1. 계승, 피보나치수, 수열의 점화식, 하노이 타워, 병합정렬 등
2.
① ,
② ,
3.
① , ,
② , ,
4.
① a, b, c, d
② a, b, c, d
③ b, d, e, f
④ b, d
⑤ b, d, e, f
⑥ b, e
⑦ b, e

5. 병합정렬은 시작 초기에 자신과 똑같은 성격이지만 크기가 반인 두 개의 문제를 해결한다. 이후 이 두 문제를 병합함으로써 전체 문제가 해결된다.
6.
Claim 1:
[증명] 여러 가지 선택이 가능하나 로 잡으면,




, 로 잡으면 인 모든 에 대하여 이다.

Claim 2:
[증명] 여러 가지 선택이 가능하나 로 잡으면,



, 로 잡으면 인 모든 에 대하여 이다.

위 Claim 1, 2로부터 이다. ■

7. 에 비례한다. 점근적으로는 이다.
8. 에 비례한다. 점근적으로는 이다.

2장

1. 가정해도 된다. 어떠한 이라도 과 사이에 이 되는 수가 하나 있다. 즉, 인 이 하나 존재한다. 만일 이라면 이다. 이므로 으로 잡아도 점근적 복잡도에는 영향을 미치지 않는다.
2.
search
▷ 배열 A[p ... r]에서 원소 가 있는지 체크한다.
{
if then {
←
if then return search ▷ 왼쪽 그룹으로