[python] 비트 연산을 이용한 알고리즘
비트 연산은 컴퓨터의 내부적인 데이터 처리에 사용되는 연산 기술입니다. 이러한 비트 연산을 이용하여 다양한 알고리즘을 구현할 수 있습니다. 이번 포스트에서는 파이썬에서 비트 연산을 활용한 알고리즘에 대해 알아보겠습니다.
1. 비트 연산의 종류
파이썬에서 비트 연산은 다음과 같은 종류를 가지고 있습니다.
&(AND) 연산: 각 비트가 모두 1일 때만 결과가 1이 됩니다.|(OR) 연산: 두 비트 중 하나라도 1이면 결과가 1이 됩니다.^(XOR) 연산: 두 비트가 다를 때만 결과가 1이 됩니다.~(NOT) 연산: 비트를 뒤집습니다.
2. 비트 연산을 활용한 예제
예제 1: 집합의 원소 개수 구하기
비트 연산을 활용하여 집합의 원소 개수를 구하는 예제를 살펴보겠습니다. 각 원소를 비트로 표현한 후, & 연산을 사용하여 공통된 비트 위치를 확인할 수 있습니다.
def count_set_bits(n):
count = 0
while n > 0:
count += n & 1
n >>= 1
return count
result = count_set_bits(5)
print(result) # 출력: 2
예제 2: 중복 제거하기
비트 연산을 활용하여 중복된 원소를 제거하는 예제도 살펴보겠습니다. 각 원소를 비트로 표현한 후, | 연산을 사용하여 중복된 비트를 확인할 수 있습니다.
def remove_duplicates(nums):
result = 0
for num in nums:
result |= 1 << num
unique_nums = []
while result > 0:
unique_nums.append(result & 1)
result >>= 1
return unique_nums
nums = [1, 2, 3, 2, 1]
result = remove_duplicates(nums)
print(result) # 출력: [1, 2, 3]
3. 결론
비트 연산은 데이터 처리에 있어서 효율적인 알고리즘을 구현하는데 사용될 수 있습니다. 위에서 살펴본 예제들을 참고하여 파이썬에서 비트 연산을 활용하는 다양한 알고리즘을 구현해보세요.