백준 10826번 바로가기 나의 풀이 fibo = [0] + [1] * 10000 n = int(input()) if n < 3: print(fibo[n]) else: for i in range(3, n+1): fibo[i] = fibo[i-1] + fibo[i-2] print(fibo[n]) 고수의 풀이 a=0;b=1;exec("a,b=b,a+b;"*int(input()));print(a) 출처 CODE REVIEW DP를 이용해서 피보나치 수를 구하는 문제. DP를 이용하지 않고 함수로 구현하면 메모리 초과의 문제에 부딪힌다. 고수의 풀이를 보면 a,b=b,a+b를 볼 수 있는데, index 고려하지 않아도 되는 점이 매우 편리하다.
백준 1010번 바로가기 첫 번째 풀이 import itertools for _ in range(int(input())): n, m = map(int, input().split()) print(len(list(itertools.combinations(range(m),n)))) 두 번째 풀이 def factorial(n): k = 1 for i in range(n): k *= (i+1) return k for _ in range(int(input())): n, m = map(int, input().split()) print(round(factorial(m) / (factorial(n) * factorial(m-n)))) 고수의 풀이 import math for l in[*open(0)][1:]:print(math.comb(*map(int,l.split()[::-1]))) CODE REVIEW itertools의 combinations을 이용하면 편리하지만 숫자가 커지면 뻗어버린다. 알고리즘에서는 combinations 직접 구현하자! 아무래도 경우의 수를 모두 보여준 뒤에 len()으로 길이를 추출해내기 때문에 그런듯. 경우의 수만 구해야한다면 굳이 이 과정을 거칠 이유가 없다. 따라서 combination 조합의 정의에 따라 factorial을 구현해서 풀어내었다. 경우의 수만 구하는 경우 math 라이브러리를 import해서 math.comb을 이요하자.
백준 15841번 바로가기 첫 번째 풀이 import sys def pibo(n): if n < 3: return 1 else: return pibo(n-1) + pibo(n-2) for i in sys.stdin: if (i:=int(i)) == -1: break cows = pibo(i) print(f"Hour {i}: {cows} cow(s) affected") 두 번째 풀이 import sys cows = [1,1] + [0 for _ in range(490)] for i in range(2, 491): cows[i] = cows[i-1] + cows[i-2] for i in sys.stdin: if (i:=int(i)) == -1: break print(f"Hour {i}: {cows[i-1]} cow(s) affected") CODE REVIEW 피보나치 수열만 구현할 수 있다면 쉽게 풀어낼 수 있는 문제였다. 영어로 된 문제였는데, 요약하자면 피보나치 수열로 늘어나는 감염된 소의 숫자를 구하라이다. 피보나치 수열을 함수로 구현했을 때 시간초과 문제가 발생하길래 미리 490 범위의 피보나치 수열을 구해두고 꺼내 쓰는 방식을 택했다.
백준 17202번 바로가기 나의 풀이 angle = [] for _ in range(3): angle.append(int(input())) if sum(angle) != 180: print('Error') else: if len(set(angle)) == 1: print('Equilateral') elif len(set(angle)) == 2: print('Isosceles') else: print('Scalene') 고수의 풀이 x=[0]*16 x[::2]=map(int,input()) x[1::2]=map(int,input()) while len(x)>2:x=[(i+j)%10 for i,j in zip(x,x[1:])] print(*x,sep='') 출처 CODE REVIEW 추억의 핸드폰 번호 궁합. 요즘 초등학생들도 이걸 하는지 모르겠다. 이거랑 이름 궁합 심심할 때마다 했는데 말이지 고수의 풀이에서는 애초에 지정할 때에 x[::2] x[1::2]로 지정한 것을 볼 수 있다. for문을 돌리지 않아도 되다니 신박하구만!!
백준 24416번 바로가기 나의 풀이 a_count = 1 b_count = 1 def fibo(n): global a_count if n==1 or n==2: return 1 else: a_count += 1 return fibo(n-1) + fibo(n-2) def fibonacci(n): global b_count f = [1,1] + [0]*(n) for i in range(3, n): f[i] = f[i-1] + f[i-2] b_count += 1 return f[n] fibo(n:=int(input())) fibonacci(n) print(a_count, b_count) CODE REVIEW 재귀호출에 비해 동적 프로그래밍(Dynamic Programming)이 얼마나 빠른지 체감할 수 있는 문제였다. 앞으로 문제를 풀 때에 동적 프로그래밍 기법을 잘 활용해서 시간을 단축하자! 때로는 수열의 요소를 여러 번 불러와야한다면, 그냥 fibonacci 수열을 쫙 구해놓고 리스트에 저장하는 것도 한 방법이다.