본문 바로가기

알고리즘/필기3

치킨 쿠폰 문제: 처음에 교환 쿠폰 n장이 있고, k장을 사용하면 1장의 쿠폰을 줄 때, 최대 몇 마리의 치킨을 받을 수 있는가? 사용한 총 쿠폰 수를 t라고 하자. 처음 n장이 있으니 t의 초기값은 n이다. 새로 받을 수 있는 쿠폰은 n // k 장이다. t += n // k * 가지고 있는 쿠폰으로 최대한 많이 교환 이때 남는 쿠폰은 n // k + n % k 장이다. n = n % k + n // k * 교환하지 못한 n % k 장 + 이제 새로 받은 n // k 장 이것을 새로 받을 수 있는 쿠폰이 0장이 될 때까지 반복하면 된다. t = n while n//k > 0: t += n//k n = n//k + n%k 이제 t를 한번에 구하자. k개의 쿠폰을 사용하면 1개의 쿠폰을 받으므로, k - 1개의 쿠폰.. 2020. 11. 25.
유니온 파인드 연속된 구간 [p : q] 을 merge 하는 경우, 단순하게 p, p+1, ..., q 를 순서대로 merge 하면 정보의 낭비가 크다. merge(p ... q) 를 위에서 언급한 작업이라고 하자. 단순히 merge(p ... q)를 하는 경우 - 3, 4에서 불필요한 작업을 반복해서 하게 된다. 정보의 낭비를 줄여보자. 방향을 뒤집어 오른쪽을 root로 하여 merge 한다. 이제 구간 [3 : 6] 을 merge 해보자. 구현은 다음과 같이 하였다. while (search(p) != search(q)) { int next = search(p) + 1; merge(q, p); p = next; } p는 3을 가리키고, q는 6을 가리키고 있다. 첫 루프에서, 다음 그림과 같이 merge(q, p).. 2020. 9. 11.
Z 길이 $n$의 문자열 $S[0:n]$에 대하여 $Array Z[0:n]$를 $O(n)$에 구한다. $i$ $Z$ a n a n a b 0 6 a n a n a b 1 0 n a n a b 2 3 a n a b 3 0 n a b 4 1 a b 5 0 b $Z[i]$는 $S[0:]$와 $S[i:]$의 최대 공통 접두사의 길이이다. 코드는 다음과 같이 작성하였다. def getZ(s): l,r=0,0 ret=[0]*len(s) ret[0]=len(s) for i in range(1,len(s)): if i>r: l=r=i while r 2020. 8. 15.