TIL0816

오늘 배운 것

비트마스킹 (Bitmasking)

비트마스킹은 비트 연산을 활용하여 자료를 저장하고 집합을 표현하는 효율적인 기술입니다. 비트 연산의 우선순위에 주의해야 하는데, 비트 연산자(&)는 논리 연산자(&&)보다 우선순위가 높지만 비교 연산자(==, >)보다 우선순위가 낮습니다. 따라서 if (x & y == 0)과 같은 코드는 if (x & (y == 0))와 같이 해석되므로 주의가 필요합니다.

비트 연산 활용

• A^(1<<6): 6번 비트의 상태를 전환하는 코드입니다. 특정 위치가 0이면 1로, 1이면 0으로 변합니다.
• A&(~(1<<6)): 6번 비트를 0으로 바꾸는 코드입니다. 원래 0이었으면 그대로 0입니다.
• visite = visite | (1<<num): 특정 숫자가 등장했다는 의미로 해당 비트를 1로 변경하는 데 사용될 수 있습니다.
• total = (1 << 10) -1;: 모든 숫자가 등장했을 때의 상태를 나타내는 값으로, 10개의 비트가 모두 1인 0b1111111111을 만드는 데 사용됩니다.
• if (visite == total) break;: 모든 숫자가 등장했는지 확인하고 종료하는 조건으로 사용할 수 있습니다.

비트마스킹의 한계

비트마스킹은 무한정 길어질 수 없으며, 보통 int (32비트)나 long (64비트)로 제한됩니다. 64개를 넘어가는 자료를 다룰 때는 배열을 64개씩 끊어서 사용하는 테크닉이 필요합니다.

C++ 비트 시프트 연산

• (-1) << 3의 결과는 -8입니다.
• 1 << 31의 결과는 -21억입니다.
• 1 << 32의 결과는 0이 나오며, 이는 변수형 오버플로우 문제입니다.

LinkedList 최적화

링크드 리스트는 자료 삽입 및 삭제가 빠르지만, 특정 위치에 접근하는 것이 느린 단점이 있습니다. 하지만 이러한 문제를 해결하기 위해 위치를 기억하고 다닐 수 있습니다. 삭제가 랜덤 액세스로만 일어나는 것은 아니므로, 위치를 기억하는 전략을 통해 성능을 개선할 수 있습니다.

메모리 관리

new 연산은 가장 느린 연산 중 하나입니다. 따라서 메모리를 미리 100000개 정도 할당해놓고 사용하는 메모리풀(Memory Pool) 기법을 활용하면 좋습니다. 또한 띄엄띄엄 new를 하면 연산 중에 최악의 상황을 만들 수 있으며, 이는 시간 초과의 주범이 될 수 있습니다.