백준 1788번 바로가기 나의 풀이 n = int(input()) def fibo(n): a,b=0,1 for i in range(n): a,b=b,(a+b)%1000000000 return a if n < 0: print(-1 if (-n)%2==0 else 1) print(fibo(-n)) elif n == 0: print(0) print(0) else: print(1) print(fibo(n)) CODE REVIEW 원래는 n이 입력되면 [0]*(2*n+1)에 해당하는 array를 만들고 짝수 index에는 양수 피보나치 수열을, 홀수 index에는 음수 피보나치 수열을 저장해 문제를 해결하고자 했다. 그런데 n의 값이 1,000,000이므로 recursion error가 발생할 우려도 있고, 규칙성이 생각보다 단순해서 굳이 이 아이디어 대신 규칙성을 활용하였다.
백준 13777번 바로가기 나의 풀이 def binary_search(data, target): data.sort() start = 0 end = len(data) - 1 arr = [] while start <= end: mid = (start+end)//2 arr.append(mid+1) if data[mid] == target: return arr elif data[mid] < target: start = mid + 1 else: end = mid - 1 import sys for i in sys.stdin: if int(i) == 0: break print(*binary_search([i for i in range(1,51)],int(i))) CODE REVIEW 이분 탐색을 연습할 수 있는 괜찮은 문제. 이분 탐색 과정에서 mid로 사용하는 요소가 몇번째인지 출력해야했다. 재귀를 활용한 이분 탐색 구현 방법을 공부하고 이 문제를 다시 풀어봐야겠다.
백준 15489번 바로가기 나의 풀이 import math r,c,w=map(int,input().split()) sum = 0 for i in range(w): for j in range(i+1): sum += math.comb((r-1+i), j+c-1) print(sum) 고수의 풀이 import math R,C,W=map(int,input().split()) print(sum(math.comb(R+i-1,C+j-1)for i in range(W)for j in range(i+1))) 출처 CODE REVIEW 파스칼의 삼각형의 부분합을 구하는 문제. 범위 지정하는게 은근히 까다로운 문제였다. 고수의 풀이를 보면 파스칼의 각 위치를 일반항 math.comb(R+i-1,C+j-1)으로 구해 범위에 따라 바로 답을 구할 수 있게 했는데, 솔직히 내 풀이랑 거의 유사하다.
백준 16395번 바로가기 나의 풀이 def factorial(n): temp = 1 for i in range(1,n+1): temp *= i return temp n,k=map(int,input().split()) print(int(factorial(n-1)/(factorial(n-k)*factorial(k-1)))) 고수의 풀이 import math S=input() print(math.comb(int(S[:2])-1,int(S[2:])-1)) 출처 CODE REVIEW 파스칼의 삼각형 - 이항계수 내용은 이제 너무 익숙해져서 다른 문제를 풀어봐야겠다. factorial을 구현해서 이항계수의 정의에 따라 구현해도 되구 math 라이브러리의 comb 메소드를 사용해도 된다.
백준 2670번 바로가기 첫 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) s = [] for i in range(n): temp = l[i] s.append(temp) for j in range(i+1,n): temp *= l[j] s.append(temp) print(round(max(s),3)) 메모리 초과 두 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) max = max(l) for i in range(n): temp = l[i] for j in range(i+1,n): temp *= l[j] if temp > max: max = temp print(round(max, 3)) 시간 초과 세 번째 풀이 l = [] for _ in range(n:=int(input())): l.append(float(input())) m = max(l) for i in range(n): temp = l[i] for j in range(i+1,n): temp *= l[j] if temp > m: m = temp print('%.3f' % m) 고수의 풀이 n=int(input()) a=[float(input())for _ in[0]*n] for i in range(1,n):a[i]=max(a[i-1]*a[i],a[i]) print(f'{max(a):.3f}') 출처 CODE REVIEW 메모리 초과 문제를 해결하기 위해 list에서 max를 뽑아내지 않고 m(현재 최댓값)보다 크면 update, 크지 않다면 그대로 pass로 바꾸어주었다. 문제 출력 형식이 소수 셋째 자리까지 맞추어줘야하므로 round()함수 대신 '%.3f % m처럼 소숫점 출력 형식으로 바꾸어주었다. 고수의 풀이 방식이 메모리도 덜 차지하고 시간도 빠른데, 각 자리별로 구할 수 있는 max값을 a[i]에 할당하고, 그것의 max를 구한다는 아이디어였다. python에서 max, min같은 이름은 변수에 붙이지 않는걸 권장한다! 웬만하면 다른 이름을 쓰자