백준에서 입력 받는 방법 import sys input = sys.stdin.readline 주의할 점! str을 받을 때 꼭 .strip()을 해서 공백을 없애야 한다. for문 다 돌고 난 후 for 쓰고 else: 하면 for문이 다 돌았을 경우에만 else 내용을 수행한다. 이거 은근히 유용하다. for i in range(10): print(i) else: print("for문 끝!") end 옵션 백준에서 정답 쓸 때 많이 사용함. word1 = "hello" word2 = "python" print(word1, end=" ") # "hello"를 출력하고 한 줄 띄우지 않고 끝에 공백을 출력 print(word2) hello python print("Hello World", end="!") ..

특정 노드에서 출발 - 다른 모든 노드로 가는 최단 경로 계산 음의 간선이 없어야 함. 매 상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복함

n=4 array = [1,3,1,5] d = [0]*100 d[0] = array[0] d[1] = array[1] for i in range(2,n): d[i] = max(d[i-1], d[i-2]+array[i]) print(d[n-1]) x = 26 d = [0]* 30001 for i in range(2, x+1): # 현재 수에서 1을 빼는 경우 d[i] = d[i-1] + 1 # 현재 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i//2]+1) # 현재 수가 3로 나누어 떨어지는 경우 if i % 3 == 0: d[i] = min(d[i], d[i//3]+1) # 현재 수가 5로 나누어 떨어지는 경우 if i % 5 == 0: d[i] = mi..

def fibo(x): if x == 1 or x ==2 : return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) 시간 복잡도 O(2^N) # 한 번 계산된 결과를 모메이제이션(memoization) 하기 위한 리스트 초기화) d = [0]*100 def fibo(x): if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환 d[x] = fibo(x-1) + fibo(x-2) return d[x] print(fibo(99)) d = [0] * 100 d[1] = 1 d[2] = 1 n = 99 for i i..

from bisect import bisect_left, bisect_right n=7 m=2 array=[1,1,2,2,2,2,3] right_index = bisect_right(array, 5) left_index = bisect_left(array,5) right_index - left_index

n=4 m=6 array=[19,15,10,17] # answer=15 start = 0 end=max(array) result=0 while (start mid: total += x - mid # 떡의 양이 부족하면 더 많이 자르기(왼쪽 부분 탐색) if total < m: end = mid-1 # 떡의 양이 충분하면 덜 자르기(오른쪽 부분 탐색) else: result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록 start = mid+1 print(result)