• 자료 구조란 프로그램이 자료를 저장하는 방식

  • 가장 기초적인 형태의 자료 구조

    • 변수, 배열, 레코드(구조체 or 클래스)

  • 모든 자료 구조는 추상화와 최적화를 위해 생겨 났다.

  • 추상화란 현실 세계에 존재하는 개념이나 구조를 간결화해 컴퓨터 프로그램에 사용되는 자료 구조로 표현하는 과정

    • 현실 세계는 너무 모호하고 많은 정보를 담고 있기에, 이를 프로그램으로 직접 구현하기 번거롭다
    • 현실 세계의 개념을 추상화한 자료 구조는 개념에서 중요한 뼈대만을 뽑아내 이름을 붙이고, 명확한 정의들을 곁들여 사람들이 쉽게 사용할 수 있게 한다.

  • 큐를 사용하는 데서 오는 가장 큰 장점은 큐를 사용하는 사람은 내부적으로 큐가 어떻게 구현되는지에 대해 전혀 신경 쓸 필요가 없다.

  • 추상화는 의사소통을 도와주는 역할도 한다.

    • 간결한 용어를 제공, 의사소통을 위한 좋은 약속

  • 최적화는 프로그램의 동작 속도를 빠르게 하기 위한 것이다.

16. 비트 마스크

16.1 도입

  • 현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현

    • 이진법 연산을 컴퓨터가 매우 빠르게 할 수 있다.

  • 비트마스크(bitmask): 이진수 표현을 자료 구조로 쓰는 기법

  • 장점

    • 더 빠른 수행 시간

    • 더 간결한 코드

    • 더 작은 메모리 사용량

    • 연관 배열(map 객체)을 배열로 대체

16.1.1 용어 정의

  • 이진수의 한 자리를 비트(bit)라고 한다.
    • 비트는 0 or 1의 값을 가질 수 있다.
    • 1: 켜져 있다
    • 0: 꺼져 있다
  • 부호 없는 N비트 정수형 변수는 N자리의 이진수로 쓸 수 있다.
  • 각 비트가 표현하는 값은 2^0 ~ 2^N-1 까지 이다
  • 최상위 비트(most significant bit): 2^N-1에 해당하는 비트
  • 최하위 비트(least significant bit): 2^0에 해당하는 비트

16.1.2 비트 연산자

  • AND 연산, a&b: 입력받은 두 정수를 한 비트씩 비교하면서, 두 정수에 해당 비트가 모두 켜져 있을 때만 결과의 비트를 킨다.

  • OR 연산, a|b: 하나라도 켜져 있을 경우, 결과 비트를 킨다.

  • XOR 연산, a^b: 하나는 켜져 있고, 하나는 꺼져 있을 경우, 결과 비트를 킨다.

  • NOT 연산, ~a: 켜져 있는 비트는 끄고, 꺼져 있는 비트는 킨다.

  • Shift(시프트) 연산, a « b / a » b: 정수 a의 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다.

    • 반대쪽 끝 비트는 0으로 채워진다.

16.1.3 유의할 점들

  • 연산자 우선순위
    • 비트 연산자의 우선순위는, 비교 연산자 보다 낮다 (C++, Java)
    • 파이썬의 경우는 반대이다.
  • 64비트 정수를 비트마스크로 사용할 때 발생하는 오버플로
  • 부호 있는 정수형의 사용
    • 변수의 모든 비트를 다 쓰고 싶을 때는 부호 없는 정수형을 쓰는 게 좋다.

16.2 비트마스크를 이용한 집합의 구현

  • N비트 정수 변수는 0부터 N-1 까지의 정수 원소를 가질 수 있는 집합이 된다.
  • 원소 i 가 집합에 속해 있는지 여부는 2^i을 나타내는 비트가 켜져 있는지 여부로 나타낸다.
  • {1, 4, 5, 6, 7, 9}을 표현하는 정수는 754, 10 1111 0010(2진수) 이다.

16.2.1 피자집 예제

  • 토핑은 20가지가 존재 (0 ~ 19번 번호를 가지고 있음)

  • 토핑을 넣기(1), 넣지 않기(0) 을 선택할 수 있다.

  • 공집합: 상수 0

  • 토핑 ‘전부 다’ 올린 피자: (1 << 20) - 1

  • 원소 추가, 해당 비트를 켠다는 의미

    • toppings |= ( 1 << p )

  • 원소의 포함 여부 확인

    • if (toppings & (1 << p))

  • 원소의 삭제

    • toppings &= ~(1 << p)

  • 원소의 토글(toggle)

    • toppings ^= (1 << p)

  • 두 집합에 대해 연산

    • 합집합: (a | b)
    • 교집합: (a & b)
    • 차집합: (a & ~b)
    • 하나에만 포함된 원소들의 집합: (a ^ b)

  • 집합의 크기 구하기

    • 내장으로 구현되어 있다. C, C++, Java
    1
2
3

    def bitCount(x):
    if x == 0: return 0
	return x % 2 + bitCount(x // 2)

  • 최소 원소 찾기

    • 이 정수의 이진수 표현에서 끝에 붙어 있는 0이 몇 개 인가?
    • 내장으로 구현되어 있다. C, C++, Java

  • 최소 원소 지우기

    • toppings &= (toppings - 1)
    • 이 방법은 어떤 정수가 2의 거듭제곱 값인지 확인할 때도 유용하게 쓰인다.

  • 모든 부분 집합 순회하기

    • pizza = {0,1,2} 일 때
      • {0}, {0, 1}, {0, 1, 2}, {0, 2}, {1}, {1, 2}, {2}
    • for pizza in toppings: subset = ((subset-1) & pizza)
      • 공집합은 방문하지 않는다.
      • subset - 1: 켜져 있던 최하위 비트가 꺼지고, 그 밑의 비트는 전부 켜진다.

Reference