원소 n개 부분집합 → 1 << n
2^n으로 나누기 → >> n
2^n으로 나눈 나머지(홀짝 판별) → & n
Swap →
a ^= b;
b ^= a;
a ^= b;

1. 기초 강의

1.1 SW 문제 해결 능력

빅세타 대신 빅오를 사용하는 이유?

• 빅세타의 경우 모든 입력에 대해 만족하지 않는다.
• 주로 관심을 가지는 부분은 제한시간 내에 결과를 내는지 즉, 최악의 성능

효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있다!

2.2 표준 입출력

C++ 입출력

• cin: 표준 입력(키보드)
• cout : 표준 출력(화면에 출력)
  • int width(int w): 최소 필드 너비를 지정
  • int precision(int p): 유효 자리수를 설정
• 파일의 내용을 표준 입력으로 읽어오는 방법
  • freopen(”sample_input.txt”, “r”, stdin);

비트연산

• 1 << n
  • 2^n의 값을 갖는다.
  • 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.
  • Power set (모든 부분 집합)
    • 공집합과 자기 자신을 포함한 모든 부분집합
    • 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.
• i & ( 1 << j )
  • 계산 결과는 i의 j번째 비트가 1인지 아닌지를 의미한다.
• Bit를 이용한 부분 집합 생성
  • 원소 수에 해당하는 N개의 비트를 이용합나다.
  • n번째 비트 값이 1이면 n번째 원소가 포함되었음을 의미한다.

실수의 표현 ← 근사적 표현

정수를 2진수로 표현하는데는 문제가 없으나 실수를 표현하기에는 부족하다. → 오차 누적 가능성 존재

1. 비트 연산

2.1 비트(bit)

• 컴퓨터에서 자료를 표현하기 위해 비트를 사용합니다.
• 1bit = 0 또는 1
• 8bit = 1byte

2.3 나누기, 나머지 연산

흔히 쓰이는 /, % 연산자는 오버헤드가 크기 때문에 필요한 경우 그보다 더 빠른 비트 연산을 사용 할 수 있습니다.

2.3.1 나누기

나누는 수가 2^n 인 경우 >> 연산자가 / 연산자를 대체할 수 있습니다.

ex) 9 / 8 = 9 / 2^3 = 1 -> 10012 >> 3 = 12

2.3.2 나머지

• 나누는 수가 2^n 인 경우 & 연산자를 활용해 % 연산자를 대체할 수 있습니다.

• 2^n 꼴의 숫자를 이진수로 표현하면 최상위 비트만 1인 형태를 띄게 되고, 2^n에 – 1을 더하면 n - 1번 이하의 모든 Bit들이 1로 변하는 것을 이용하면 됩니다.

  ex) 9 % 4 = 1 -> 10012 & 112 = 12

• 이를 홀수 판별에도 적용할 수 있습니다

  ex) n % 2 = n & 1

2.4 SWAP

XOR 연산을 이용하면 임시 변수를 선언하지 않고 두 변수의 값을 바꿀 수 있습니다.

int a, b;
a = 10, b = 30;
a ^= b;
b ^= a;
a ^= b;

2.5 비트마스킹

• 각 Bit를 하나의 Flag로 활용한다면 자료 저장과 집합 표현을 쉽게 할 수 있습니다.
• 사람에 0~31 사이의 번호가 매겨져 있고, 사람 A의 친구 목록이 {0, 3, 6, 7, 10, 13, 28}이고, B의 친구 목록이 {0, 1, 4, 5, 6, 17, 21, 28} 이라고 합시다.
• 이 때 다음과 같은 문제를 풀어봅시다.
  1. A 또는 B가 아는 친구의 수는?
  2. A와 B 사이에 겹치는 친구의 수는?
• 반복문을 이용해서 문제를 풀 수 도 있지만, 비트를 사용하면 이러한 "집합" 연산이 간단해집니다.
• 친구 목록을 사람 번호로 저장하지 않고 x번째 사람이 내 친구라면, x번째 비트를 1로 표시하는 방식으로 바꿔보겠습니다.
• 그러면 A의 친구 목록은 전체 사람의 수가 32명이므로 32bit 이진수에 0, 3, 6, 7번 비트를 1로 표시한 0001 0000 0000 0000 0010 0100 1100 10012 이 됩니다.
• B의 친구도 이와 같이 바꾸면 0001 0000 0100 0010 0000 0000 0111 00112 이 됩니다.
• 이렇게 비트로 친구 목록을 저장하면 앞의 두 문제를 빠르게 해결할 수 있습니다.
• 1)번 문제는 두 친구목록을 | 연산해 구할 수 있고 2)번 문제는 & 연산해 구할 수 있습니다.