[Python] 분수의 순환소수, 순환마디 구하기
예전에 순환소수를 구하는 코드를 만들어서 포스팅을 했었다. ( https://daewonyoon.tistory.com/354 ) 손으로 하는 나누기를 그대로 따라하면서, 나머지를 기억하고, 이전에 나왔던 나머지가 다시 나오면, 싸이클이 반복되어 순환마디를 구할 수 있다는 아이디어였다. 다른 방법이 좀 더 간단할지 어쩔지 궁금해서 대충 실험을 해 봤다. 이번 아이디어는 이렇다. 순환소수는 결국 999...99 를 분모로 하는 소수로 바꿀 수 있다. 그러니, 주어진 분수의 분모가, 999...99 를 떨어지게 나눌 때까지, 9, 99, 999, 9999, ... 를 늘려가고, 나누어 떨어지면, 그 배수를 분자에도 곱하면, 분자가 순환마디가 된다. 테스트를 해 본 것은 다음과 같다. def solve(a): ..
[EP 078] 동전 나누기
문제 78 : p(n)을 n개의 동전을 무더기로 나누는 경우의 수라고 하자. 예를 들어서, 5개의 동전이 있다면, 다음과 같이 7가지 방법이 있어서, p(5) = 7이 된다. ooooo oooo o ooo oo ooo o o oo oo o oo o o o o o o o o 해법 : Q(n, m) 을 n개의 동전을 나눌 때 가장 큰 무더기를 이루는 갯수가 m개인 경우의 수라고 한다. 위 예에서 보면, Q(5,5) = 1 Q(5,4) = 1 Q(5,3) = 2 Q(5,2) = 2 Q(5,1) = 1 이 되는 것을 알 수 있다. 이렇게 정의한 Q(n, m)에서 다음과 같은 식이 항상 성립함을 알 수 있다. Q(n, n) = 1 Q(n, 1) = 1 m Q(n, m) = sum Q(n-m, i) i = 1 마지..
Connected Component
>>> data = [("ㄱ","ㄴ"), ("ㄴ","ㄷ"), ("ㄷ","ㄱ"), ("ㄱ","ㄴ"), ("ㄹ","ㅁ"), ("ㅂ","ㅅ"), ("ㅇ","ㄹ")] >>> data [('ㄱ', 'ㄴ'), ('ㄱ', 'ㄷ'), ('ㄴ', 'ㄷ'), ('ㄹ', 'ㅁ'), ('ㄹ', 'ㅇ'), ('ㅂ', 'ㅅ')] >>> class ConnectedGroups: def __init__(self): self.groups = [] # groups remain mutually exclusive def add(self, e): set_e = set(e) overlap_index = [] for i, g in enumerate(self.groups): if set_e & g: overlap_index.append(i) if..