컴퓨터 알고리즘 5주차

챕터2 99p ~ 챕터2 125p

1차시: 누승(팩토리얼) 활용 수열

반복문의 횟수를 저장하는 변수를 반복 변수라고 한다.

순서도에서 결합 기호 앞쪽을 초기화 부분, 뒤쪽을 반복 부분으로 나눌 수 있다.

반복 변수 n, 팩토리얼 변수 f, 합 저장 변수 s 의 초기값으로 0을 줘도 되지만, 1을 주는 것이 계산에 용이하다.

순서도  1. 함수를 호출할 때 함수 호출 기호 대신 제어 기호를 사용해서 함수 호출과 계산을 동시에 한다. 2. end 대신에 return F로 사용 가능하다. 이때는 F 출력과 1 출력 작업이 필요 없어지고, N이 0 보다 작을 땐 F = 1로 값을 지정한다.

 

2차시: 동적 프로그래밍(다이나믹 프로그래밍)

최적 부분구조(Optimal Substructure):

최적의 해답을 구하는 문제를 부분 구조로 풀이한 것, 큰 문제를 작은 문제로 쪼갠 후 작은 문제들의 답을 이용한다.

팩토리얼, 피보나치도 여기에 해당한다.

 

부분 문제 반복(Overlapping Subproblem):

재귀 호출에서 중복 호출의 비효율성이 큰 경우를 말한다.

피보나치에서 n을 알려면 n-1, n-2를 알아야 하고 n-1에서는 n-2, n-3을 구하는 것 같이 중복이 발생한다.

(피보나치 수열 : Fib(n) = Fib(n-1) + Fib(n-2))

 

동적 프로그래밍 사용 경우:

최적 부분구조 성격을 가지고, 부분 문제 반복이 심각할 경우 이용한다.

팩토리얼, 피보나치는 최적 부분구조 성격을 동일하게 가지지만, 팩토리얼은 부분 문제 반복이 크지 않아서 동적 프로그래밍을 사용하지 않는다.   

 

동적 프로그래밍:

계산 해 놓은 것을 미리 저장 해두어서 필요할 때 가져다 쓴다. 그래서 무조건 계산 하는 것이 아니라 저장한 값이 없을 때만 계산한다. 이를 통해 중복 호출의 비효율성을 줄일 수 있다.

• Bottom-Up 방식: 반복 구조 사용. 동적 프로그래밍의 잘 드러나지 않는다.

• Top-Down 방식: 최초의 계산만 하고, 저장된 값은 계산하지 않고 인용해서 사용하는 동적 프로그래밍의 이점 제대로 사용 가능. 재귀함수로 구현

피보나치 수열 동적 프로그래밍   Bottom-Up 방식-N은 2보다 커야 한다. 반복구조 안에서 함수를 호출한다.   그냥 Tod-Down 방식 VS 동적프로그래밍 Tod-Down 방식 F(N) = 0이 아니라면 계산을 진행하지 않고 Return 하는 것이 핵심이다. 반복 구조 없이 재귀 함수로 구현한다.

 

 

3차시

제곱의 합:

B = 101-A 이용

(B x A)^2 의 형태

 

교행 자연수 수열의 합:

방법

1,3. SUM에서 홀수항일 땐 더하고, 짝수항일땐 뺀다. 

(1번과 3번 방법은 유사한데 1번은 N 증가하고 SUM 계산하고를 번갈아서 했다면, 3번은 홀수항 짝수항을 MOD로 구분하고 SUM 계산을 한다.)

2. 스위치 변수(Toggle 변수)를 N에 곱해서 SUM에 더한다. (SW =-SW)

 

 

4차시

교행 분수 수열의 합: 순서도 분자를 보면 항의 수는 49개인 것을 알 수 있음 1. 항 순서를 나타내는 변수 K는 반복문을 돌며 1부터 49까지 증가, 그리고 항 순서를 4번에서 1을 증가시키기 때문에 0으로 초기화 2. 변수 L은 K번째 항의 값을 계산해 보관 3. SW가 0이라면 S에 L더한 후 SW에 1 대입, SW가 0이라면 S에 L 뺀 후 SW에 0 대입 (SW의 값이 0이면 더하기를, 1이면 빼기를 의미) 4. K가 49가 되면 반복문이 종료되면서 S 출력

변수 설명 B: 반복 변수 N: 팩토리얼(분모 역할) H: 각 항 조건문 답 설명 B % 2 == 1은 홀수항을 의미하고, +기호로 합한다. else는 짝수항으로 -기호로 합한다. B == 10은 10번 반복하면 반복문을 끝낸다.

변수 설명 M: 분모 N: 분자 K: 반복 변수