[나채공] 이진수 변환과 파이썬의 bin()함수
[나채공] 이진수 변환과 파이썬의 bin()함수
코딩테스트를 하다가 해당 수가 2로 나누어진 횟수를 구하는 것에 대해서 공부하는데 새로운 것을 발견해서 이에 대해 정리하고자 합니다.
len(bin(12)) -3
여기서 bin(n)은 숫자 n을 이진수 문자열로 변환합니다.
예를 들면 n = 12일때 0b1100과 같이 변합니다. 이때, 0b는 접두어로 이진수라는 표시를한다고 합니다.
그래서 len(bin(12)) -3에서 -3을 하는 이유가 앞에 접두어의 길이를 제거하기 위해서 한다고 합니다.
그런데 여기서 의문이 접두어 0b는 문자열 길이가 2자인데 왜 -3을 빼는가 입니다.
이것은 문제에 달려있습니다.
제가 풀던 문제가 주어진 수를 2로 얼마나 나눌 수 있는가를 구하는 문제입니다.
이를 이해하기 위해서, 예를 들어 n = 10일때, 과정을 보겠습니다!
- 10은 짝수,
10 / 2 = 5 - 5는 홀수, 5에서 1을 빼고 2로 나누면 2
- 2는 짝수,
2 / 2 = 1
이렇게 3번의 연산을 해야합니다.
이 문제는 n을 1로 만드는데 필요한 연산 횟수를 구하는 것인데, 이때 이진수의 특성을 활용해서 풀 수 있습니다.
이진수의 특성과 풀이
짝수는 이진수에서 0으로 끝나는 수 입니다. 그래서 2로 나누면 이진수에서 끝자리를 제거하는것입니다. 1로 끝나서 홀수여도 어짜피 계산에서 -1하여 계산하기 때문에…
그래서 이것 때문에 len(bin(12)) -3을 하는 겁니다.
접두어인 0b뿐만 아니라 마지막 자리를 제외하고 이진수의 길이를 구하는 것입니다.
왜 이진수의 길이와 연산 횟수가 연관되어있을까?
그 이유는 숫자를 1로 만드는 과정에서 이진수의 비트 이동과 연관이 있기 때문입니다.
숫자를 1로 만드는 과정은 이진수의 비트 단위 연산과 유사합니다. 그래서 이진수의 길이가 연산 횟수와 관련이 있는 것입니다.
문제에서 숫자로 1로 만들때, 2로 나누어 반으로 만드는 과정을 거치는데, 이것이 이진수에서 비트를 한 칸씩 오른쪽으로 이동하는 것과 같습니다.
이진수에서 비트의 오른쪽 이동은 숫자를 2로 나누는 것과 같기 때문입니다.
이진수에서 마지막으로 구해야하는 1을 남겨야하기 때문에, 접두어+마지막 2^0부분 해서 3을 빼는 것입니다.
2^0을 구하기 위해서 몇번 연산하느냐가 중요한 문제이기 때문입니다.
bin(12)== 0b1100에서 2^0으로 만들기 위해서 0b를 제외한 1100에서 오른쪽으로 3번 비트 이동을 해야 2^0값이 나오기 때문에 이 문자열의 길이가 연산 수 와 같은 것입니다!
이런 특성을 잘 생각하고 기억하고 있으면 활용하기 좋을 것 같습니다.!
댓글남기기