[문제 출처 : Codechef] 이번에 살펴볼 문제는 꽤나 복잡한 문제입니다. 얼핏 보기에는 쉬워보이지만 막상 복잡한 구조로 되어있으니 정신 바짝 차라시길 ^.~ 어떤 수 n이 주어졌습니다. 이 n을 $2^x$꼴들로만 구성되게 표현하는 것이 이번 문제입니다. 간단하게 예를 들면, \[15=1111_{(2)}=2^{2+2^0}+2^{2}+2^{2^0}+2^0\] 이와 같이 지수에 있는 숫자들조차도 계속해서 $2^x$꼴로 표현해 나가는 것입니다. 생각보다 헷갈리죠?
먼저 가장 기본적으로 Python에서 어떻게 숫자를 이진수 표현으로 바꾸는지 알아봅시다.
>>> bin(5)
'0b101'여기서 0b는 이진수 표현이라는 의미이구요, 그 뒤의 101이 이진수 표현입니다. 따라서 우리가 원하는 것은
>>> bin(5)[2:]
'101'이렇게 추출하면 되겠죠? 주의할 점은 string 형태를 갖는다는 점입니다! 그리고 여기서 한 가지 더 알고 넘어갑시다. 바로 enumerate라는 함수인데요, 이것은 index와 value를 동시에 iterate할 수 있게 해주는 꽤나 효율적인 녀석입니다. 바로 살펴보시죠.
>>> for i, ch in enumerate('abc'):
... print i, ch
0 a
1 b
2 c보시면 아시겠지만, (index, value) tuple 형태로 받아올 수 있다는 걸 아시겠죠?
그럼 이제 우리가 원하는 결과로 한발짝 더 다가가 봅시다 :) 이진수 표현의 각 자리가 1이면 $2^x$들이 더해진다는 것은 쉽게 아시겠죠? 이를 이용해서 간단하게 다음과 같은 함수를 만들 수 있습니다.
def binExpr(n):
string = bin(n)[2:]
resultExpr = []
for e, b in enumerate(string):
if b == '1':
exponent = len(string) - e - 1
resultExpr.append('2(' + str(exponent) + ')')
return '+'.join(resultExpr)
>>> binExpr(7)
2(2)+2(1)+2(0)와! 드디어 우리가 원하는 것의 한 절반 정도는 구현했네요 :) 이제 문제는 지수(exponent)를 다시 이러한 표현으로 바꾸는 것일텐데요, 지수가 0 또는 1일 경우를 제외하면 모두 다 다시 $2^x$들로 쪼개야겠죠? 얼핏 생각했을 때도 Recursive로 구현하면 참 좋을 것 같은데요, 문제는 그렇게 되면 1이라는 수를 입력했을 때, 재귀함수로 0을 호출하게 되므로 대략 난감해지는 상황이 생기게 됩니다. (아마 구현해 보시면 아실거에요^^;) 그래서 저는 어쩔 수 없이 두 개의 base case (n=1,2)에 대해서만 예외처리를 하기로 했습니다.
def binExpr(n):
if n==1:
return '2(0)'
if n==2:
return '2'
string = bin(n)[2:]
resultExpr = []
## 2^2 이상부터는 지수를 다시 변환하지만,
for e, b in enumerate(string[:-2]):
if b == '1':
exponent = len(string) - e - 1
resultExpr.append('2(' + binExpr(exponent) + ')')
## 1과 2의 경우에는 굳이 지수로 넣지 말고 원래 수로 넣어서 base case로 리턴되게 합시다.
if string[-2] == '1':
resultExpr.append(binExpr(2))
if string[-1] == '1':
resultExpr.append(binExpr(1))
return '+'.join(resultExpr)
>>> print binExpr(7)
2(2)+2+2(0)
>>> print binExpr(137)
2(2(2)+2+2(0))+2(2+2(0))+2(0)
>>> print binExpr(1315)
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)아주 훌륭히 동작하는 것을 확인할 수 있네요 :) Recursive 함수 짜는 좋은 연습문제였던 것 같네요 ^^