[MySQL] 특정 형질을 가지는 대장균 찾기

문제 설명

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다. 다음은 실험실에서 배양한 대장균들의 정보를 담은 ECOLI_DATA 테이블입니다. ECOLI_DATA 테이블의 구조는 다음과 같으며, ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE 은 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타냅니다.

Column name	Type	Nullable
ID	INTEGER	FALSE
PARENT_ID	INTEGER	TRUE
SIZE_OF_COLONY	INTEGER	FALSE
DIFFERENTIATION_DATE	DATE	FALSE
GENOTYPE	INTEGER	FALSE

최초의 대장균 개체의 PARENT_ID 는 NULL 값입니다.

---

문제

2번 형질을 보유하지 않으면서 1번이나 3번 형질을 보유하고 있는 대장균 개체의 수(COUNT)를 출력하는 SQL 문을 작성해주세요. 1번과 3번 형질을 모두 보유하고 있는 경우도 1번이나 3번 형질을 보유하고 있는 경우에 포함합니다.

---

예시

예를 들어 ECOLI_DATA 테이블이 다음과 같다면

ID	PARENT_ID	SIZE_OF_COLONY	DIFFERENTIATION_DATE	GENOTYPE
1	NULL	10	2019/01/01	8
2	NULL	2	2019/01/01	15
3	2	100	2020/01/01	1
4	2	16	2020/01/01	13

 

각 대장균 별 형질을 2진수로 나타내면 다음과 같습니다. 

ID 1 : 1000₍₂₎

ID 2 : 1111₍₂₎

ID 3 : 1₍₂₎

ID 4 : 1101₍₂₎

각 대장균 별 보유한 형질을 다음과 같습니다.

ID 1 : 4

ID 2 : 1, 2, 3, 4

ID 3 : 1

ID 4 : 1, 3, 4

따라서 2번 형질이 없는 대장균 개체는 ID 1, ID 3, ID 4 이며 이 중 1번이나 3번 형질을 보유한 대장균 개체는 ID 3, ID 4 입니다.

따라서 결과는 다음과 같아야 합니다.

COUNT

2

---

문제를 해석하자면, GENOTYPE 컬럼에 있는 값들을 2진수로 나타냈을 때, 각 비트 번호를 형질이라 표현한다.

즉, 8이라는 숫자를 이진수로 표현하면,

1000₍₂₎ 이 되고, 맨 오른쪽을 1번으로 칭했을 때, 4번 형질을 보유하고 있다 얘기하는 것이다.

이 문제를 풀기 위해서는 SQL의 비트 연산자를 알아야 한다.

비트 연산자(AND, OR, NOT)의 개념과 예시

1. 비트 AND(&)

• 정수들을 이진수로 변환한 뒤, 각 자릿수별로 AND 논리연산(둘 다 1 이면 1, 아니면 0)을 수행
• 예:
  • 6 & 3을 해석하면
    • 6 → 110₍₂₎
    • 3 → 011₍₂₎ 
    • 110 & 011
      -------
         010₍₂₎ = 2
  • 결과는 2

2. 비트 OR(|)

• 정수들을 이진수로 변환한 뒤, 각 자릿수별로 OR 논리연산(둘 다 1이면 0, 둘 다 0이면 1, 둘 중 하나가 1이면 1)을 수행
• 예:
  • 6  | 3을 해석하면
    • 6 → 110₍₂₎
    • 3 → 011₍₂₎ 
      110 | 011
      -----
      111₍₂₎ = 7
    •  
  • 결과는 7

3. 비트 XOR(ˆ)

• 정수들을 이진수로 변환한 뒤, 각 자릿수별로 XOR 논리연산(둘 중 하나가 1이면 1, 둘 다 0이면 0)을 수행
• 예:
  • 6 ^ 3을 해석하면
    • 6 → 110₍₂₎
    • 3 → 011₍₂₎
      110 ^ 011
      -----
      101₍₂₎ = 5
  • 결과는 5

4. 비트 NOT(~)

• 하나의 정수를 이진수로 변환한 뒤, 각 비트를 반전(1이면 0, 0이면 1)시킨 정수를 반환
• 예:
  • 6(10진수) = 110(2진수)이지만, 실제로는 DB 내부에서 정수는 32비트 혹은 64비트로 표현됨
  • 예를 들어 32비트 정수 기준, 6은 00000000 00000000 00000000 00000110
    • NOT을 하면 11111111 11111111 11111111 11111001 (10진수로 -7에 대응)
  • 따라서 결과는 -7(2의 보수 표현)과 같이 음수가 될 수도 있다.

그 외 Shift 연산자(<<, >>) 가 있지만, SQL에서는 낮은 빈도로 사용

x << n : x의 이진수를 왼쪽으로 n 비트 이동

x >> n : x의 이진수를 오른쪽으로 n 비트 이동

6 << 1 = 110 -> 1100

6 >> 1 = 110 -> 011

계산 방법으로는 x * 2의 n제곱, x / 2의 n제곱

6 << 1 = 6 * 2의 1제곱 = 12

6 >> 1 = 6 / 2의 1제곱 = 3

 

이를 통해, 위 문제를 풀면

select count( * ) as COUNT
from ECOLI_DATA
where !(GENOTYPE & 2)
and ((GENOTYPE & 1) or (GENOTYPE & 4))

GENOTYPE & 2: 비트 번호 2번 (오른쪽에서 2번째 비트 번호)가 0이다. 즉, 2번 형질을 보유하지 않는다.

GENOTYPE & 1 or GENOTYPE & 4: 1번과 3번 형질을 보유한다.

주의!
왜 GENOTYPE & 3이 아니라 4인가?
문제에서 예시로 든 대장균들의 GENOTYPE 값을 2진수로 나타낸 예시를 보면,

1번 형질을 갖고 있다 → 2진수로 ...0001 → 10진수로 1
2번 형질을 갖고 있다 → 2진수로 ...0010 → 10진수로 2
3번 형질을 갖고 있다 → 2진수로 ...0100 → 10진수로 4
4번 형질을 갖고 있다 → 2진수로 ...1000 → 10진수로 8

즉, n번 형질은 **2^(n-1)**에 해당하는 비트가 켜져 있는지(1인지) 여부로 판단

1번 형질 = 2^(1-1) = 2^0 = 1
2번 형질 = 2^(2-1) = 2^1 = 2
3번 형질 = 2^(3-1) = 2^2 = 4
4번 형질 = 2^(4-1) = 2^3 = 8 ... 이런 식으로, 형질 번호에 따라 비트 값이 결정

따라서 3번 형질이 있는지 확인하려면 GENOTYPE & 4가 0이 아닌지 체크하면 된다.