이번 주는 algorithm 과 코딩테스트를 연습하는 시간을 가질 것이다. 처음에는 코딩테스트라는 것이 낯설었지만 문제를 하나하나 차근히 풀어가다보니 점점 재밌었던 것 같다. 이번 글에서는 그 중 간단하지만 참신했던 문제 풀이들을 몇 가지 소개하려 한다.
Contents
- 편지
1-1. Bits
1-2. Bitwise left shift operator (<<) - 점의 위치 구하기
- 중복된 숫자의 개수
1. 편지 ("<<" operator)
<문제>
생일 축하 편지를 쓰려고 하는데 보기 편하도록 글자 한 자 한 자를 가로 2cm 크기로 적으려고 하며, 편지를 가로로만 적을 때, 축하 문구 message 를 적기 위해 필요한 편지지의 최소 가로길이를 return 하도록 solution 함수를 완성하여라.
<나의 해답>
def solution(message):
return len(message) * 2나는 위와 같이 두 줄로 간단히 적어보았는데 이게 가장 일반적인 approach 가 아닐까 싶다. 하지만 다음의 코드를 보자.
<참고 해답>
def solution(message):
return len(message) << 1처음 참고 해답의 코드를 보고 "<<" 에 관해 찾아보게 되었는데 상당히 재밌는 operator 라는 생각이 들었다. 해당 기호는 Bitwise left shift operator 라고 하며, 이를 이해하기 위해서는 우선 bit 의 개념부터 알아야 한다.
1-1. Bits
A bit (binary digit; 0 or 1) is the smallest unit of data that a computer can process and store.
컴퓨터가 process 할 수 있는 데이터는 모두 0 과 1 의 binary 조합으로 구성되는데, 이 때 0 또는 1 이 하나의 bit 가 되며 two physical states 를 represent 한다. 따라서, n 개의 bit 로는 2ⁿ 가지의 상태를 나타낼 수 있다. 또한 주로 여덟 개의 bits 가 모여 byte 라는 단위를 이룬다.
1-2. Bitwise left shift operator
명칭에서도 유추할 수 있듯이 bitwise left shift operator (<<) 는 operand 의 bits 를 왼쪽으로 움직이는데, 그 공석은 0 으로 채워진다.
The bit positions that have been vacated by the shift operation are then zero-filled.
그렇다면 이렇듯 bitwise operator 를 사용하는 이유는 무엇일까? 그것은 bitwise operators 가 정확도는 높지만 fewer resources 를 필요로 하기에 코드를 더욱 빠르고 효율적으로 실행시킬 수 있기 때문이다.
- 참고 링크: Python bitwise operators 에 관한 설명을 제공한다.
https://www.digitalocean.com/community/tutorials/python-bitwise-operators
<해설>
다시 참고 해답으로 넘어가자면, input 인 message 가 "Happy birthday!" 라고 해보자. 그렇다면 띄어쓰기를 포함한 이 string 의 전체 길이는 15 이다. 한 자 한 자 2 cm 씩 띄어쓰려면 가로 총 30 cm 의 공간이 필요하다.
즉, Left-shift operator 를 이용하면 우선 15 가 binary 인 1111 로 변환된 후 왼쪽으로 한 칸 shift 를 한다. 즉, 오른쪽 끝에 0 이 하나 더 붙어 11110 의 binary number 가 되고, 이를 다시 decimal 로 나타내면 30 이 된다.
2. 점의 위치 구하기
<문제>
x 좌표 (x, y) 를 차례대로 담은 정수 배열 dot 이 매개변수로 주어질 때 (e.g., [2, 4]), 좌표 dot 이 사분면 중 어디에 속하는지 1, 2, 3, 4 중 하나를 return 하도록 solution 함수를 완성하여라.
<나의 해답>
def solution(dot):
if dot[0] > 0:
return 1 if dot[1] > 0 else 4
else:
return 2 if dot[1] > 0 else 3<참고 해답>
def solution(dot):
quad = [(3,2),(4,1)]
return quad[dot[0] > 0][dot[1] > 0]
<해설>
이 문제에 관해서는 나의 solution 보다 더 advanced 한 답이 있을 것 같아 찾아보게 되었다. 나는 우선 x 가 양수인지 음수인지를 판단한 후 y 의 부호를 참고해 몇 번째 quadrant 에 있는지를 판단했다. 하지만 참고 해답은 True 와 False, 그리고 list 속 tuple 을 이용하였는데 매우 clever 하다고 생각했다.
즉, True = 1, False = 0 일 때, [0][0] 이면 3rd quad, [0][1] 이면 2nd quad, [0][1] 이면 4th quad, 그리고 [1][1] 이면 x 와 y 가 모두 양수이므로 1st quad 에 있다.
3. 중복된 숫자의 개수
<문제>
정수가 담긴 array와 정수 n 이 매개변수로 주어질 때, array 에 n이 몇 개 있는 지를 return 하도록 solution 함수를 완성하여라.
<나의 해답>
def solution(array, n):
count = 0
for num in array:
count += 1 if num == n else 0
return count<참고 해답>
def solution(array, n):
return array.count(n)
<해설>
이 문제 또한 더 나은 풀이가 있을 것 같아 찾아보게 되었는데, list.count(value) 라는 함수를 알고 나니 for 문이 허무해진 대신 훨씬 좋은 코드를 짤 수 있었다.
