[Python/파이썬] 백준 11444번: 피보나치 수 6

문제 풀이 분할 정복을 이용한 거듭제곱이므로 피보나치 수를 제곱의 형태로 만들려고 노력했다. 노트에 끄적이다가 우연히 규칙 발견!! n % 2 == 0 인 경우 Fn = F(n//2+1) ** 2 - F(n//2-1) ** 2 n%2 == 1 인 경우 Fn = F(n//2+1) ** 2 + F(n//2) ** 2 메모제이션도 활용해야 시간 초과가 나지 않는다. 코드 dp = dict() def fibo(n): if dp.get(n) != None: return dp[n] if n == 0: return 0 if n == 1 or n == 2: return 1 if n % 2 == 0: dp[n // 2 + 1] = fibo(n // 2 + 1) % 1000000007 # 맨 처음에는 % 100000000..

[Python/파이썬] 백준 9251번: LCS

문제 풀이 ACAYKP의 A와 CAPCAK의 C, CA, CAP, CAPC, CAPCAK 부분 수열의 LCS를 구한 뒤 2차원 배열에 저장. (0, 0) : A, C의 LCS 값(0) 저장 / (1, 0) : A, CA 의 LCS 값(1) 저장 / (2, 0) : A, CAP 의 LCS 값(1) 저장 ACAYKP의 AC, CAPCAK의 C, CA, CAP, CAPC, CAPCAK 부분 수열의 LCS를 구한 뒤 2차원 배열에 저장. (0, 1) : AC, C 의 LCS 값(1) 저장 / (1, 1) : AC, CA 의 LCS 값(1) 저장 / (2, 1) : AC, CAP 의 LCS 값(1) 저장 위 과정을 반복 그림에서 빨간색 글자는 최장 부분 수열 검은색 글자는 최장 부분 수열의 길이 파란색 글자는 L..

[Python/파이썬] 백준 1654번: 랜선 자르기 [이진 탐색]

내 코드 def find(lans, n,h,m): high = h min = m mid = (high + min)//2 while min = n: min = mid + 1 elif sum < n: high = mid - 1 mid = (high + min)//2 return mid from sys import stdin k, n = map(int,stdin.readline().split()) lans = [] for i in range(k): lans.append(int(input())) high = max(lans) min = 1 mid1 = find(lans,n,high,min) print(mid1) 처음 작성한 코드 k,n = map(int,input().split()) lans = [] for i..

[Python/파이썬] 백준 1157번: 단어 공부

내가 쓴 코드 a = input().upper() s = list(set(a)) count = [] for i in range(len(s)): count.append(0) for j in range(len(a)): if(s[i] == a[j]): count[i]+=1 max = 0 for i in range(0, len(count)): if(count[max] 0) & (max != i): k = "?" print(k) 다른 사람이 쓴 코드 n = input() n = n.upper() alpa='ABCDEFGHIJ..