알고리즘 분석기법들

알고리즘 분석기법들

명지대학교 컴퓨터공학과

이 충기

지난 주 강의 내용

• 알고리즘 소개

• 알고리즘 표현 방법

• 알고리즘의 분류

• 알고리즘의 정확도 분석

• 알고리즘과 데이터 구조

이번 주 강의 내용

• 수학적 귀납법

• 기본 공식 증명

• 수열과 점화식

• 선형 점화식 해 구하기

Impossible

I’m possible

내 생각을 바꾼다

문제

옛날에 어느 나라에 승려들만 모여 사는 섬이 있다. 그들 중에서 어느 사람은 눈이 빨갛고 어느 사람은 눈이 까맣다. 눈이 빨간 사 람은 마법에 걸려 있기 때문에 스스로 눈이 빨갛다는 사실을 깨 닫게 되면 그날 밤 자정에 섬을 떠나야 한다. 승려들은 서로의 눈 색깔에 대해 전혀 말할 수 없다. 또한 자신의 눈이 무슨 색인지 알지 못한다. 그러던 어느 날 그 섬에 관광객이 찾아 왔다. 그는

“당신들 중에 적어도 한 명은 눈이 빨갛다.”라고 말한 후 떠났다.

그러면 그날 밤부터 그 섬에는 어떤 일이 일어났겠는가?

수학적 귀납법

• 모든 양의 정수 n 에 대해 명제 P( n )이 참 이라는 것을 증명하기 위한 기법이다.

• 증명 방법

1. 기본 단계: 명제 ____이 참임을 보인다.

2. 귀납적 가설: n 이 k 일 때 명제 ____가 참이 라고 가정한다.

3. 귀납적 단계: n 이 ( k + 1) 일 때 명제 ______가

참이라는 것을 증명한다.

도미노를 이용한 수학적 귀납법 작동 원리

만약 두 도미노사이의 거리가 도미노의 높이

보다 항상 ___면, 첫 번째 도미노가 쓰러지면

나머지 모든 도미노가 쓰러진다.

기본 공식 1



i

i

1

기본 공식 1의 증명 1



 1

1 k

i

i

기본 공식 1의 증명 1 (계속)



i

i

1



 1

1 k

i

i

기본 공식 1의 증명 2

그림을 통한 증명



i

i

1

. . . .

. .

.

. .

.

.

. ^{. . .}

n

n

기본 공식 1의 증명 2 (계속)



i

i

1 2

기본 공식 2



i0

x



0 i

xi

기본 공식 3



0 i

ix



0 i

ixi

수열과 점화식

상수 계수들을 가진 선형 점화식

상수계수들을 가진 선형 점화식

상수계수들을 가진 선형 점화식 (계속)

일반 해 구하기

예: 일반 해 구하기

다중 근들(Multiple Roots)

특수 해 구하기

예: 특수해 구하기

예: 특수해 구하기 (계속)

예: 특수해 구하기 (계속)

상수계수들을 가진 선형 점화식 해 구하기

예제 8 (계속)

예제 8 (계속)

요약

• 기본 공식 증명

– 수학적 귀납법

– 그림, 수식 재처리

• 상수 계수들을 가진 선형점화식 해 구하기

– 일반 해 구하기

– 특수 해 구하기

– 해 구하기