백준 - 단기간 성장 1

12865. [다이나믹프로그래밍] 평범한 배낭 (골드5)

🔗 문제/코드 보기

dp = [[0*(k+1)]*(n+1)]

이렇게 하면 초기화 제대로 안 됨

dp = [[0] * (k + 1) for _ in range(n + 1)]

이렇게 해야 함

---

1655. [우선순위 큐]가운데를 말해요 (골드2)

🔗 문제/코드 보기

원래는 sort() 썼는데  당연히 시간초과 뜸

1. leftHeap, rightHeap ( 짝수개인 경우 작은수를 중앙값으로 부르기 위함) 로 나누어 저장
2. left의 root와 right의 root 비교하여, left가 더 큰 경우 두 루트 교환

파이썬에서 힙은 heapq로 선언

heapq.heappop(leftHeap)
heapq.heappush(leftHeap, -number)  #leftHeap은 최대힙이기 때문에 역수 저장

 

그리고 이런 시간 보는 문제는 반드시 sys 사용해야 한다. 그냥 앞으로는 sys로만 풀어야겠다..

---

11401. [수학] 이항 계수 3 (골드1)

🔗 문제/코드 보기

이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미

처음에는 시간초과만 생각해서 다이나믹 프로그래밍을 사용해 풀었다. nCk = (n-1)Ck + (n-1)C(k-1) 라는 점화식을 사용해 풀었는데, dp[N+1][K+1]를 만드는 과정에서 당연히 메모리 초과가 나왔다..

그래서 두번째로는 이항계수 식을 그대로 구현하되, factorial을 재귀함수로 만들었는데, 이러니 재귀 깊이 초과 오류가 났다. 이건 처음 안 건데, 파이썬은 재귀함수 호출을 1000번으로 제한한다고 한다. 그래서 반복문을 사용하여 factorial을 계산했다.

 

이때, N의 크기가 매우 크므로 매 계산마다 mod(1000000007) 로 %(모듈러)하는 과정이 필요한데,

나누기 계산 시에는 모듈러를 사용할 수 없어, 페르마의 소정리 [모듈러 역원]를 사용해야 한다.

# 페르마의 소정리 - 모듈러 역원: (a**−1)%m == a**(m−2) % m
def modular(a, mod):
    return pow(a, mod-2, mod)