Junodevv Blog

[MYSQL] 비트연산을 활용한 쿼리

30 Sep 2024 - juno

#sql  #bit 

프로그래머스 SQL 문제 - 조건에 맞는 개발자 찾기를 풀면서…

SQL 문제를 풀면서 처음으로 비트연산자를 활용하는 문제를 풀게되었다. 문제풀이가 아니더라도 비트연산을 이용해 쿼리를 구성한 적은 처음이기에 흥미로워 글을 작성한다.

문제

문제 설명

SKILLCODES 테이블은 개발자들이 사용하는 프로그래밍 언어에 대한 정보를 담은 테이블입니다. SKILLCODES 테이블의 구조는 다음과 같으며, NAME, CATEGORY, CODE는 각각 스킬의 이름, 스킬의 범주, 스킬의 코드를 의미합니다. 스킬의 코드는 2진수로 표현했을 때 각 bit로 구분될 수 있도록 2의 제곱수로 구성되어 있습니다.

NAME TYPE UNIQUE NULLABLE
NAME VARCHAR(N) Y N
CATEGORY VARCHAR(N) N N
CODE INTEGER Y N

DEVELOPERS 테이블은 개발자들의 프로그래밍 스킬 정보를 담은 테이블입니다. DEVELOPERS 테이블의 구조는 다음과 같으며, ID, FIRST_NAME, LAST_NAME, EMAIL, SKILL_CODE는 각각 개발자의 ID, 이름, 성, 이메일, 스킬 코드를 의미합니다. SKILL_CODE 컬럼은 INTEGER 타입이고, 2진수로 표현했을 때 각 bit는 SKILLCODES 테이블의 코드를 의미합니다.

NAME TYPE UNIQUE NULLABLE
ID VARCHAR(N) Y N
FIRST_NAME VARCHAR(N) N Y
LAST_NAME VARCHAR(N) N Y
EMAIL VARCHAR(N) Y N
SKILL_CODE INTEGER N N

예를 들어 어떤 개발자의 SKILL_CODE가 400 (=b’110010000’)이라면, 이는 SKILLCODES 테이블에서 CODE가 256 (=b’100000000’), 128 (=b’10000000’), 16 (=b’10000’) 에 해당하는 스킬을 가졌다는 것을 의미합니다.

문제

DEVELOPERS 테이블에서 Python이나 C# 스킬을 가진 개발자의 정보를 조회하려 합니다. 조건에 맞는 개발자의 ID, 이메일, 이름, 성을 조회하는 SQL 문을 작성해 주세요.

결과는 ID를 기준으로 오름차순 정렬해 주세요.

예시

예를 들어 SKILLCODES 테이블이 다음과 같고,

NAME CATEGORY CODE
C++ Back End 4
JavaScript Front End 16
Java Back End 128
Python Back End 256
C# Back End 1024
React Front End 2048
Vue Front End 8192
Node.js Back End 16384

DEVELOPERS 테이블이 다음과 같다면

ID FIRST_NAME LAST_NAME EMAIL SKILL_CODE
D165 Jerami Edwards jerami_edwards@grepp.co 400
D161 Carsen Garza carsen_garza@grepp.co 2048
D164 Kelly Grant kelly_grant@grepp.co 1024
D163 Luka Cory luka_cory@grepp.co 16384
D162 Cade Cunningham cade_cunningham@grepp.co 8452

다음과 같이 DEVELOPERS 테이블에 포함된 개발자 중 Python 스킬이나 C# 스킬을 가진 개발자의 정보가 결과에 나와야 합니다.

ID EMAIL FIRST_NAME LAST_NAME
D162 cade_cunningham@grepp.co Cade Cunningham
D164 kelly_grant@grepp.co Kelly Grant
D165 jerami_edwards@grepp.co Jerami Edwards

1. 문제풀기 전 비트연산에 대한 이해

이 문제를 풀기위해선 비트연산에 대한 이해가 먼저 필요하다고 생각된다.

비트연산은 대학을 다니면서 여러 언어를 배우며 접하긴 했지만 딱히 활용할 일이 많지 않아 잘 떠오르지 않아 다시 찾아봤다.

MYSQL에서 비트연산은 AND(&), OR(|), XOR(^), NOT(~)가 있다.

여기서 이 문제에 필요한 연산은 &, 대응되는 비트가 모두 1이면 1을 반환하는 연산이다.

예시1

  0000 0001 --- 1
& 0000 0101 --- 5
-----------
  0000 0001 --- 1

이렇게 &연산을 이 문제에서 활용하면 SKILL_CODE의 숫자를 보고 Python - 256(0001 0000 0000)과 C# - 1024(0100 0000 0000) 를 가진 개발자를 찾아낼 수 있다.

예를들어 문제의 예시처럼 SKILL_CODE가 400(256 + 128 + 16 = 0001 1001 0000) 이고 python의 CODE 256(0001 0000 0000) 과 AND 연산을 수행하게되면

예시2

  0001 1001 0000 --- 400
& 0001 0000 0000 --- 256
-----------
  0001 0000 0000 --- 256

이런식으로 비트연산을 통해 python을 포함하는 SKILL_CODE인지 아닌지를 구분할 수 있다.

2. 나의 풀이

SELECT DISTINCT ID, EMAIL, FIRST_NAME, LAST_NAME
FROM DEVELOPERS
WHERE 
(SELECT CODE FROM SKILLCODES WHERE NAME='C#') = (SKILL_CODE&(SELECT CODE FROM SKILLCODES WHERE NAME='C#')) 
OR
(SELECT CODE FROM SKILLCODES WHERE NAME='python') = (SKILL_CODE&(SELECT CODE FROM SKILLCODES WHERE NAME='python'))
ORDER BY ID asc;

나는 이런식으로 풀었다.

서브쿼리를 이용하여 SKILLCODES.CODE에서 C#(python)에 해당하는 CODE값을 가져왔고 그 SKILLCODES.CODE와 DEVELOPERS.SKILL_CODE를 비트연산을 하게되면 그 결과값은 C#(python)에 해당하는 값과 같다는 점을 이용했다.(예시2 참고)

장점

단점

3. 다른사람풀이

SELECT DISTINCT(id), email, FIRST_NAME, LAST_NAME
FROM developers 
JOIN skillcodes ON developers.skill_code & skillcodes.code
WHERE NAME = 'C#' OR NAME = 'Python'
ORDER BY ID;

프로그래머스에 공유된 다른분의 풀이다.

비트연산결과를 JOIN 조건으로 사용했다.

비트연산 JOIN

비트연산으로 JOIN을 하게되면 어떤식으로 JOIN이 되는걸까

결론부터 말하면 비트연산의 결과가 0이 아니면 된다.

비트연산으로 JOIN 되는 레코드 예시

DEVELOPERS.SKILL_CODE가 0101 이고 SKILLCODES.CODE가 0100 (C#)인 경우라면

  0101 - DEVELOPERS.SKILL_CODE
& 0100 - SKILLCODES.CODE('C#')
  ----
  0100 - SKILLCODES.CODE('C#'), "개발자의 스킬코드에 'C#'이 포함됨 => 조인 OK"

비트 연산의 값이 0100으로 DEVELOPERS의 스킬코드에 C# 이 포함되어있음을 알 수 있고 이 레코드는 JOIN조건에 성립된다.

비트연산으로 JOIN되지 않는 레코드 예시

DEVELOPERS.SKILL_CODE가 0011 이고 SKILLCODES.CODE가 0100 (C#)인 경우라면

  0011 - DEVELOPERS.SKILL_CODE
& 0100 - SKILLCODES.CODE('C#')
  ----
  0000 - "개발자의 스킬코드에 'C#'에 포함되는 값이 없음 => 조인되지 않음"

비트 연산의 값이 0000 으로 DEVELOPERS의 스킬코드에 C#이 포함되어있지 않음을 알 수 있고 이 레코드는 JOIN조건에 성립되지 않게된다.

* 비트연산 조인의 예시 표

developers 테이블:

id email first_name last_name skill_code
1 john@example.com John Doe 1
2 jane@example.com Jane Smith 2
3 mike@example.com Mike Johnson 3
4 alice@example.com Alice White 4

skillcodes 테이블:

code name
1 C#
2 Python
3 Java
4 Go

이 두 테이블을 조인하면, 각 developers.skill_code와 skillcodes.code가 비교되어 일치하는 경우에만 데이터가 결합

  1. 조인의 실제 동작 예시
developers.skill_code skillcodes.code 비트 연산 (developers.skill_code & skillcodes.code) 결과 JOIN 성립 유무
4 (0001) 1 (0001) 0001 True O
2 (0010) 2 (0010) 0010 True O
3 (0011) 1 (0001) 0001 True O
3 (0011) 2 (0010) 0010 True O
4 (0100) 1 (0001) 0000 False X
4 (0100) 2 (0010) 0000 False X

이렇게 하면, developers.skill_code와 skillcodes.code 간의 비트 연산을 통해 특정 기술을 가진 개발자만 선택된다.

JOIN 방식의 장점

4. 기타

이 글을 쓰면서 또 다른 풀이를 생각하게 되었다.

SELECT DISTINCT ID, EMAIL, FIRST_NAME, LAST_NAME
FROM DEVELOPERS
WHERE 
(SKILL_CODE&(SELECT CODE FROM SKILLCODES WHERE NAME='C#')) > 0 
OR
(SKILL_CODE&(SELECT CODE FROM SKILLCODES WHERE NAME='python')) > 0
ORDER BY ID asc;

하지만 두번의 서브쿼리를 사용하기 때문에 한번에 JOIN하는 방식이 성능적으로 더 적절할 것이라고 생각된다.

출처

다른사람풀이

비트연산에 대한 이해를 도와준 글

프로그래머스 코딩 테스트 연습

chat-GPT