글에 들어가기전에...
기껏해야 평일 개인정비 1시간 반이랑 주말이 전부다
하지만 주말엔 놀아야하고 코딩공부하는게 쉽진않은거같다
사실 지금까지 군복무하면서 폰만보고 놀았던거같은데
주변을 보면 열심히하는 사람들이 많다
선임분중에는 매일 주말도 포함해서 개인정비/연등 시간을 통해 자격증공부
동기중에는 블로그를 4월에 시작해서 꾸준하게 포스팅한 결과 엄청 유명해졌더라구
그래서 나도 저렇게 열심히 해봐야겠다 라는 생각이들어 일주일에 한번이라도
본인이 푼 알고리즘 문제를 설명하는것처럼 글을 써볼 생각!
아무튼 화이팅..!
오늘 푼 문제는 DP라고 불리는 동적 프로그래밍 문제이다
복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법
정의는 위와같은데, 피보나치 수열을 보고 이해해보자
첫항과 두번쨰 항을 각각 1로 두고
n이 3이상일때는 그전항과 전전항을 더하는 수열이다
그럼 F3는 결과가 어떻게 나올까?
위에 식으로 보면
F3 = F2 + F1 에서 F1과 F2는 1이므로 F3은 2가된다
이렇게
F4 = F3 + F2
F5 = F4 + F3
...
계속 이어나가게된다
그러면! 이수열을 코드로 짜보자
def fib(n):
if n <= 1: #F1은 1
return 1
elif n == 2: #F2도 1
return 1
else:
return fib(n-1) + fib(n-2) #Fn = Fn-1 + Fn2 / n이 3이상일때만 연산
n = int(input("n을 입력하세요: "))
print(f"fib({n}) = {fib(n)}")이렇게 되면 예를 들어 n이 5이면
fib(3) + fib(4) 를 계산해야하므로 fib(3)과 f(4)값이 연산되어 더한후 fib(5)의 값이 나오게된다
fib(5)라는 계산을 fib(3)과 fib(4)로 나누어서 계산하고
fib(3)과 fib(4)도 나누어서 계산하고
이것이 동적 프로그래밍이다.
하지만 위코드에는 문제점이 있다..!
무엇이 문제일까??
위에서 말했다 싶이 fib(5)라는 항을 fib(4)와 fib(3)을 더한 값으로 나눠서 계산한다고 했다.
그러면 그 다음 항인 fib(6)은???
fib(6)도 fib(5)와 fib(4)의 값을 더한것으로 적용되는데
fib(5)와 fib(4)를 다시 처음부터 계산해야하는 것이다!!!
위그림과 같이 특정 함수를 호출하면 똑같은 계산이 빈번한걸 볼수있다
그러면 또 fib(3)다시계산하고... fib(2)도 다시계산하고... 코드의 실행시간이 기하급수적으로 늘어나게된다
그럼 어떻게 하면 될까??
방법은 간단하다 우리가 한 계산을 저장하면 된다!
저장하면 굳이 계산을 다시 할 필요가 없기 때문이다
우리는 이걸 "Memoization"이라고 한다
memo = {1: 1, 2: 1} # F1과 F2의 초기값을 설정
def fib(n):
if n in memo: # 이미 계산된 값이 있으면 반환
return memo[n]
else:
memo[n] = fib(n-1) + fib(n-2) # 값이 없으면 계산 후 저장
return memo[n]
n = int(input("n을 입력하세요: "))
print(f"fib({n}) = {fib(n)}")이렇게 메모를 이용하면 실행시간이 줄어들게 된다!
백준 1003번 피보나치 함수
간단하게 말해서 위 문제는 특정 함수가 실행되면 그 함수의 값을 계산할때
fib(0)과 fib(1)이 사용되는 횟수를 반환하게 하라는 문제이다
memo = {0:[0,1,0],1:[1,0,1]} #초기값
def fib(n):
if n in memo: #전에 계산된 값이라면,
return memo[n] #바로 그값을 리턴
else: #처음 계산하는 것이라면,
tmp = fib(n-1) + fib(n-2) #두 값과 실행횟수를 리스트에서 넣어
memo[n] = [0,0,0]
#메모에 넣어준다
memo[n][0] = tmp[0] + tmp[3] #tmp 인덱스 0과 3은 함수계산값
memo[n][1] = tmp[1] + tmp[4] #tmp 인덱스 1과 4는 각함수의 0실행횟수를 더함
memo[n][2] = tmp[2] + tmp[5] #tmp 인덱스 2과 5는 각함수의 1실행횟수를 더함
return memo[n]
n = int(input())
for i in range (n):
n1 = int(input())
print("%d %d"%(fib(n1)[1],fib(n1)[2]))나는 메모설정을 키값에는 fib(n)의 n값을,
벨류값에는 리스트로 [결과값,0출력횟수,1출력횟수] 순으로 설정했다
마치며...
알고리즘 공부를 시작하면서 동적 프로그래밍 먼저 풀고있는데
처음 이해할때에는 머리가 너무아팠는데 또 이해하고 보니까 괜찮을거같기두
해당 글은 직접 공부한 내용을 정리한 글입니다
어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!
