[SQL] 멸종위기의 대장균 찾기 문제 풀이

목차

---

1. 문제 설명

2. 정답

 

 

 

 

 

1. 문제 설명

---

https://school.programmers.co.kr/learn/courses/30/lessons/301651

프로그래머스

 

위 문제의 핵심은 먼저 각 세대별 대장균을 구하고, 세대 별 자식이 없는 개체 수와 세대를 출력하는 것이다.

테이블엔 몇 번째 세대까지 존재하는지 알 수 없고, 정확히 몇 번째 세대에 대한 결과를 구하는 문제가 아니기 때문에 재귀를 사용해야 함을 알 수 있다. 

 

SQL에서도 재귀가 가능한가?

당연히 가능하다.

 

CTE 문법과 RECURSIVE를 활용하면 된다.

MySQL과 Oracle 모두 CTE 문법을 지원하므로 RECURSIVE를 작성하는 방법에 대해 알아보자.

 

CTE 문법
SQL에서 임시 결과 집합을 정의하는 방법
한 번 정의한 CTE는 해당 쿼리에서 여러 번 참조할 수 있어 코드의 가독성과 재사용성을 높임
기본 문법은 WITH TEMP(테이블명) AS ( ) 형식

 

 

재귀는 WITH RECURSIVE 구문을 사용한다.

WITH RECURSIVE cte_name (column1, column2, ...) AS (
    -- 1️⃣ 비재귀 부분 (초기 값)
    SELECT 초기값 FROM some_table
    UNION ALL
    -- 2️⃣ 재귀 부분 (자기 자신을 호출)
    SELECT 다음_값 FROM cte_name WHERE 종료_조건
)
SELECT * FROM cte_name;

 

• WITH RECURSIVE로 재귀 CTE를 선언
• 비재귀 부분으로 초기값을 설정하며 해당 영역이 첫 번째로 실행
• 재귀 부분은 자기 자신을 참조하여 종료 조건까지 반복하여 실행

이때 비재귀 부분이 반드시 존재해야 한다.

또, 데이터가 자연스럽게 끊기는 경우엔 재귀 종료 조건이 없어도 괜찮지만 그렇지 않은 경우엔 무한 루프에 빠질 수 있다!

 

▼ 예제

WITH RECURSIVE cte AS (
    -- 1️⃣ 초기값 설정
    SELECT 1 AS n  
    UNION ALL
    -- 2️⃣ 재귀적으로 증가
    SELECT n + 1 FROM cte WHERE n < 5
)
SELECT * FROM cte;

 

✅ 실행 과정

1. SELECT 1 AS n → n = 1 추가
2. SELECT 1 + 1 FROM cte → n = 2 추가
3. SELECT 2 + 1 FROM cte → n = 3 추가
4. SELECT 3 + 1 FROM cte → n = 4 추가
5. SELECT 4 + 1 FROM cte → n = 5 추가
6. WHERE n < 5 조건이 거짓이므로 종료

 

✅ 출력 결과

n

1

2

3

4

5

 

---

그렇다면 해당 문제에서는 어떤 것을 재귀로 구해야하는가?

바로 각 세대별 대장균 ID, GENERATION 정보이다.

 

문제 예시 정보

 

즉 예시 테이블을 기준으로 아래와 같은 데이터를 뽑아내는 것이다.

세대  - ID
1세대 - 1, 2
2세대 - 3, 4, 5
3세대 - 6, 7
4세대 - 8

 

따라서 비재귀 영역에서 1세대의 대장균 정보를 구하고, 재귀를 통해 N세대의 대장균 정보를 구하다가 더 이상 데이터가 없으면 재귀를 멈춘다. 재귀를 통해 얻은 각 세대별 대장균 결과에 대해 해당 ID를 PARENT_ID로 갖는 대장균이 없다면 자식이 없는 것으로 간주한다.

 

 

 

 

2. 정답

---

-- ECOLI_TEMP : 각 세대별 대장균 ID, GENERATION 정보 담은 테이블
WITH RECURSIVE ECOLI_TEMP AS (
    -- 1세대의 대장균 ID 구하기
    SELECT ID AS ID, 1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    UNION ALL
    -- N세대의 대장균 ID 구하기
    SELECT CHILD.ID AS ID, GENERATION + 1 AS GENERATION
    FROM ECOLI_TEMP PARENT JOIN ECOLI_DATA CHILD 
      ON PARENT.ID = CHILD.PARENT_ID
)
-- 세대별 자식 없는 대장균 구하기
SELECT COUNT(*) AS COUNT, ET.GENERATION AS GENERATION
FROM ECOLI_TEMP ET
WHERE NOT EXISTS(SELECT * FROM ECOLI_DATA WHERE PARENT_ID = ET.ID)
GROUP BY ET.GENERATION
ORDER BY ET.GENERATION ASC;

 

해당 문제 같은 경우 데이터가 자연스럽게 끊기기 때문에 재귀 종료 조건을 명시하지 않아도 된다.

단 그렇지 않은 반드시 재귀 종료 조건을 명시해주어야 무한 루프에 빠지는 것을 방지할 수 있다.