자료구조는 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식이 있다. 배열은 연속 방식의 가장 기본이 되는 자료형이다. 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기는 고정되어 있고, 한번 생성한 배열은 크기를 바꾸는것은 불가능이다.
DP : Dynamic Programming 동적 계획법, => 탑다운, 바텀업
dp에서 대표적인 사례는 피보나치 수열이 있다. 점화식을 이용해서 표현할 수 도 있는데, 점화식이란 인접한 항들 사이의 관계식을 의미한다.
a(n+2) = f(a(n+1), a(n)) = a(n+1) + a(n) a1 = 1, a2 =1
=>
n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
1번째 피보나치 수 = 1 , 2번째 피보나치 수 = 1
파이썬에서는 이런 수열을 배열이나 리스트로 표현할 수 있다.
n번째 피보나치 수를 f(n)이라고 할때 f(4)는 어찌 구할까?
f(4) = f(3) + f(2) = f(2) + f(1) + f(1)
#fibonacci function을 재귀 함수로 표현
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1) + fibo(x-2)
이렇게 계산하면은 문제가 생기는데 f(n)에서 n의 값이 커지면 커질수록 수행시간은 기하급수로 늘어난다. 시간복잡도가 매우 큼.
=> DP을 사용하기 위한 조건은 다음과 같다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에ㅓ도 도잉ㄹ하다.
피보나치를 메모이제이션 기법을 사용해서 해보면, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그댈 가져옹는 기법, 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고 함.
d= [0] * 100
def fibo(x):
if x==1 or x==2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
bottom-up 이 이숙한데 짜보면
d= [0] * 100
d[1] = 1
d[2] =1
n= 99
for i in range(3,n+1):
d[i] = d[i-1] + d[i-2]
#1로 만들기 : 정수 X에 대해서
1) 5로 나누어 떨어지면 , 5로 나눈다.
2) 3으로 나누어 떨어지면, 3으로 나눈다.
3) 2로 나누어 떨어지면, 2로 나눈다.
4) 1을 뺀다.
이 4개의 연산을 이용해서 1로 만들려고 하는데, 이때 연산을 사용하는 횟수의 최솟값은?
x = int(input())
d = [0] * 30000
for i in range(2,x+1):
#현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1
#현재의 수가 2로 나누어 지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
if i % 3 ==0:
d[i] = min(d[i], d[i//3] + 1)
if i % 5 ==0:
d[i] = min(d[i], d[i//5] + 1)