피보나치수열
1, 1, 2, 3, 5, 13... An = An-1 + An-2 (n>=3)
피보나치수열 순서도로 나타내는 방법
시작
A, B는 피보나치 초항
SUM 초기값
N을 3으로 하면 앞으로 더할 값/ N이 2면 지금 SUM에 참여한 값(A, B 두 개 참여함)
A, B를 합한 값 = C
SUM이 바뀌는 부분
단계 올라감
N+1은 지금까지 한 항의 수
N =100이면 다음에 할 N이 아닌 현재 참여한 N의수
100보다 작으면 돌아간다.
피보나치수열 이용해 디버깅 표 만들기
A B S N C N=1
수열
수열 : 규칙에 따라 숫자들이 차례대로 나열된 것
EX) 1부터 100까지의 자연수의 합을 구하는 알고리즘
- 등차수열
- 등비수열
- 피보나치 수열
- 공차
+ 문제
서로 다른 자연수 2개를 받아 그 사이에 존재하는 자연수의 합과 3의 배수의 제곱의 합을 구하여 출력하는 알고리즘.
힌트 : MOD( i,3 ) = 3의 배수 알아낼 수 있는 함수.
N1, N2 : 입력된 2개의 자연수 (단 N1 < N2)
i : 반복 처리를 위한 변수
S1 : 두 자연수 사이에 존재하는 자연수의 합
S2 : 두 자연수 사이에 존재하는 3의 배수의 제곱의 합
① 0
② N1
③ N2
④ S1
⑤ i * i
누승 알고리즘 (팩토리얼)
N! = N에 대한 누승
= 1 × 2 × 3 × --- × N
팩토리얼 순서도
N : 자연수 1부터 100까지 보관하는 변수 , 초깃값 1
F : 자연수 N에 대한 누승을 보관하는 변수
S : 자연수의 누승의 합을 보관하는 변수
시작
초기화
반복시작
N은 앞으로 처리
이전의 N-1에 N 을 곱한다.
N은 처리한것임. 방금 처리한게 100인지 확인
출력
끝
+ 누승을 재귀호출로 구하는 방법
10! => 9! * 10 => 8! * 9 ... 1! *2
동적 알고리즘
동적프로그래밍 사용하는 경우
1. 최적부분구조 성격의 문제일때
- 최적부분구조의 문제 : 큰 문제의 해답을 구하는 과정 안에 작은 문제의 해답을 구하는 과정이 포함된 경우
- Ex) 자연수 n의 팩토리얼을 재귀호출을 통해 구할 경우 (재귀호출할시 중복호출 비효율성이 크지 않아 동적프로그래밍을 사용하지 않음)
- Ex) 피보나치의 수열을 재귀호출을 통해 구할 경우 ( 최적부분의 구조 문제 + 재귀호출할때 중복 호출의 비효율성이 크므로 동적 프로그래밍을 사용함)
2. 재귀호출 할때 중복호출의 비효율성이 심각한 경우 = 부분 문제 반복
피보나치 수열에 대한 정의
A1 = 1, A2 =1
An = An-1 + An-2 (n>=2인경우)
N번째 피보나치 수열 항을 구하는 알고리즘, N번쨰 피보나치 수여ㅕㄹ 항까지의 합을 구하는 알고리즘
bottom-up방식의 동적 프로그래밍(반복구조 사용)
밑에서부터 올라가는
top-down 재귀호출방식
위에서부터 내려가는
중복계산이 많이 발생함
Top-down방식의 동적 프로그램(재귀호출 사용)
이미 계산되어 있는지 표에서 찾아봄. 중첩되는 것들이 재계산되지 않음
팩토리얼은 0보다 큰데 F(1000)을 0으로 둠
첫번째로 table check F(N)=0 : 한번도 피보나치수열을 계산시킨적 없다는 뜻
0이 아니면 F(N)의 값을 리턴함. 새로 없는 것은 갱신
첫번째 호출할때만 계산하고 나머지는 보관했다가 사용.
제곱수열과 교행 자연수 수열 알고리즘
제곱의 합
S = (100*1)² + (99*2)² + (98*3)² + --- + (3*98)² + (2*99)² + (1*100)²의 합 구해 출력하는 알고리즘
수열 100개 = 100번 반복
(B * A)² : B와 A의 합 100 -> B = 101 - A
변수 선언
A = 1
B =100
C = 100 * 1
(100 * 1 )² -----반복
수열의 합 구하는 S에 새로운 항 C더하기
A 100보다 작으면 반복
출력
+ , - 교행 자연수 수열
S = 1 - 2 + 3 - 4 + 5 - 6 --- - 100 = (-1) 50번 반복
+1 +3 +5 ---
-2 -4 ---
N =100일때 끝
SW = -SW
+1 -1 +1 -1반복되며 누적
스위치 변수 사용하지 않고 구하는 방법 (짝수, 홀수 이용한 방법)
MOD(N,2) = 0 짝수
MOD(N,2) = 1 홀수
짝수일때 빼고 홀수일때 더하는
S = 5 - 10 + 15 -20 + --- -500
NN은 5*N값
N을 2로 나눈 값 = 1 홀수
홀수면 NN을 더하고 짝수이면 NN을 뺀다.