파이썬을 해보자
Blog Python
2021-07-05
어쨌든 계속되는 코딩생활
이제 블로그에 디스커스로 댓글 기능도 구현했고, 디자인도 잘 다듬었다. 그럼 미뤄놨던 경영과학 함수를 구현… 하기엔 아직 실력이 부족하다.
블로그 만든답시고 html과 css와 자바스크립트 등 프론트엔드는 좀 건드렸지만, 아직 수학적 계산을 돌리는 본격적인 코딩은 미숙한 상태.
그럼 코딩 실력을 키워야지
백준이 그렇게 좋다던데
언젠가 건너건너 백준 사이트가 떠올랐다. 여기저기 코딩 예제들 스터디 하는걸 찾아봐도 백준을 제일 먼저 찾더라. 여튼 그렇게 백준에 들어가서 덧셈 뺄셈 그냥 대충 파이썬으로 날려적어서 맞았습니다 메시지가 나오니 자신감이 붙었는지 1003번 피보나치 수열 문제를 건드렸다.
이게 왜 안되냐…
뭐 문제에서 피보나치 수열 구하는 함수도 줬겠다, 이걸 조금만 다듬어서 대충 파이썬으로 붙여넣으면 풀릴거라 생각했다. 하지만 잘못 생각했다. 이 문제는 제한시간이 0.25초다…
여튼 그렇게 처음 작성한 코드는 비주얼 스튜디오에선 그런대로 결과값은 맞게 나오긴 했다. 근데 평가는 냉정하게도 시간초과.
n = int(input())
def fivo(n):
if n == 0:
zc = int(1)
oc = int(0)
elif n == 1:
zc = int(0)
oc = int(1)
else:
zc = fivo(n-1)[0]+fivo(n-2)[0]
oc = fivo(n-1)[1]+fivo(n-2)[1]
return (zc,oc)
for i in range (1,n+1):
globals()["num_"+str(i)]=int(input())
for i in range (1,n+1):
print(str(fivo(eval("num_"+str(i)))[0])+" "+str(fivo(eval("num_"+str(i)))[1]))
지금 와서 생각해보면 굳이 왜 동적 변수를 만들어서 컴퓨팅 자원을 더 낭비했는지도 모르겠고, 굳이 저런 식으로 배열을 쓰고 문자열로 바꿔 출력했어야 싶나 싶다.
어쨌든 다음으로 구글링을 좀 해가며 개선한 알고리즘은 이렇다.
n = int(input())
def fib(n):
if n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
for i in range (n):
inp=int(input())
if inp == 0:
a=1
b=0
elif inp == 1:
a=0
b=1
else:
a=fib(inp-1)
b=fib(inp)
print(str(a),str(b))
피보나치 수열 특성상 n번째 피보나치 수에서 0이 호출된 횟수는 n-1번째 피보나치 수, 1이 호출된 횟수는 n번째 피보나치 수인걸 확인.(물론 n>0일때 이야기다.)
그걸 이용해 결과값을 배열에서 구해와야 한다는 생각을 버리고, 정수 변수만 써서 처리 가능하게 구조를 단순화하려 했다.
하지만 결과는 또다시 시간초과. 가장 중요한건 간과하고 있었다.
from functools import lru_cache
n = int(input())
a = list(int(input()) for _ in range(n))
def fib(n):
if n == 0:
return 0
elif n == 1 or n == 2 or n == -1:
return 1
else:
return fib(n - 1) + fib(n - 2)
for i in a:
print(fib(i-1),fib(i))
이번에는 파이썬 자체 기능으로 이미 해둔 연산결과는 캐시를 사용해 저장해놔서 더 빠르게 불러오는 api를 가져왔다. 그리고 한번에 출력이 안 되는게 문제였나 싶어 2번째 입력부터는 리스트로 받은 다음 결과를 한꺼번에 출력하도록 했다.
그렇게 채점창이 좀 더 빨리 돌아가나 싶었으나 여전히 실패. 여전히 뭔가 빼먹고 있다.
from functools import lru_cache
n = int(input())
a = list(int(input()) for _ in range(n))
def fib(n):
if n == 0:
return 0
elif n == 1 or n == 2 or n == -1:
return 1
else:
return 2
for i in a:
print(fib(i-1),fib(i))
이쯤되면 슬슬 약도 오르고 지쳐간다. 그냥 원칙적으로 재귀함수로 계산해야 하는 값 따위 그냥 결과값만 같게 대체해버린다. 결과는… 틀렸습니다? 처음으로 보는 시간초과나 에러가 아닌 틀렸다는 메시지다. 답에 거의 가까이 왔다.
마지막 제출
왜 이번에 시간초과가 안 떴을까를 곰곰이 생각해본 결과, 지금껏 피보나치 수열을 불러올때 쓰던 재귀함수 매커니즘을 이번엔 아예 빼버렸다는 사실이 들어왔다.
“그럼 재귀함수 대신 다른걸로 피보나치 수열을 구하면 되려나?”
그렇게 재귀함수를 쓰지 않고 피보나치 수열을 구하는 알고리즘을 찾아 적용시켰다.
from functools import lru_cache
n = int(input())
l = list(int(input()) for _ in range(n))
def fib(n):
if n==-1:
a=1
else:
a, b = 0, 1
for i in range(0, n):
a, b = b, a + b
return a
for i in l:
print(fib(i-1),fib(i))
결과는…
드디어 해냈다!
애초에 재귀함수를 쓰면 복잡해져서 제한 시간 내에 잘 안 되게끔 설계한 듯 하다. 하긴, 매크로나 다른거 만질때도 재귀함수 그런거 잘 쓰지도 않았으니깐… 그런거 쓰는 습관 혹여라도 들이지 말라고 이런 문제를 만든걸까. 이놈의 문제 하나 푸느라 몇번을 재시도를 했는지 모르겠다.
뭐 지금은 한참 하다보면 늘겠지.