🚀[SQL 알고리즘 문제 풀이] Programmers : 멸종위기의 대장균 찾기 (with 심화 재귀쿼리(CTE))

🔓 문제 설명

 

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해주세요.

이때 결과는 세대에 대해 오름차순 정렬 해주세요. 단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재합니다.

 

 

• ECOLI_DATA 테이블

  컬럼명	타입	설명
  ID	INTEGER	대장균 개체의 ID
  PARENT_ID	INTEGER	부모 개체의 ID (최초는 NULL)
  SIZE_OF_COLONY	INTEGER	대장균 개체의 크기
  DIFFERENTIATION_DATE	DATE	분화된 날짜
  GENOTYPE	INTEGER	대장균의 형질

 

 

(문제출처:https://school.programmers.co.kr/learn/courses/30/lessons/301651)

---

 

🎯 입출력 예제

ECOLI_DATA 테이블:

ID	PARENT_ID	SIZE_OF_COLONY	DIFFERENTIATION_DATE	GENOTYPE
1	NULL	10	2019-01-01	5
2	NULL	2	2019-01-01	3
3	1	100	2020-01-01	4
4	2	16	2020-01-01	4
5	2	17	2020-01-01	6
6	4	101	2021-01-01	22
7	6	101	2022-01-01	23
8	6	1	2022-01-01	27

 

 

각 세대별 대장균의 ID는 다음과 같습니다.

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

이 때 각 세대별 자식이 없는 대장균의 ID는 다음과 같습니다.

1 세대 : ID 1
2 세대 : ID 3, ID 5
3 세대 : ID 7
4 세대 : ID 8

따라서 결과를 세대에 대해 오름차순 정렬하면 다음과 같아야 합니다.

COUNT	GENERATION
1	1
2	2
1	3
1	4

 

 

---

 

🏆 핵심 포인트

✅ WITH RECURSIVE를 활용하여 자기 자신을 기준으로 JOIN

✅ PARENT_ID를 통해 부모-자식 관계를 추적하고 세대 구분
✅ 세대가 고정이 아닌 자식세대의 ROW가 나오지 않는 세대까지 필터링 → CTE 활용
✅ LEFT JOIN으로 자식이 없는 개체 필터링

---

 

📝 코드 구현

-- ① 재귀 CTE (Common Table Expression)를 이용해 세대를 계산
with recursive gen_tree as (
    -- (Anchor 파트) : 1세대 개체 = 부모가 없는 개체
    select id, 1 as gen
    from ecoli_data
    where parent_id is null

    union all

    -- (Recursive 파트) : 부모의 세대 + 1로 자식 세대를 계산
    select A.id, B.gen + 1
    from ecoli_data A
    join gen_tree B
      on B.id = A.parent_id
    -- 즉, ecoli_data 테이블을 gen_tree와 자기 자신의 부모-자식 관계로 JOIN하면서 세대를 점점 확장
),

-- ② 각 개체가 자식을 가지고 있는지 여부를 확인
child_check as (
    select A.id, A.gen, B.id as child_id
    from gen_tree A
         left join ecoli_data B
           on A.id = B.parent_id
    -- gen_tree의 id는 개체 ID, 그것이 ecoli_data의 parent_id인 경우 자식이 있다는 뜻
    -- 자식이 없는 경우 B.id (즉 child_id)가 NULL로 나타남
)

-- ③ 자식이 없는 개체(child_id가 NULL인 경우)만 골라서 세대별로 COUNT
select count(*) 'count', gen generation
from child_check
where child_id is null
group by gen
order by 2;  -- 세대 오름차순 정렬

---

 

🔥 인사이트

🔹 Recursive CTE(재귀 공통 테이블 표현식)

• Anchor Member: 재귀의 시작점을 정의하는 쿼리
• Recursive Member: Anchor Member에서 생성된 결과를 기반으로 추가 데이터를 생성하는 쿼리
• UNION ALL: Anchor Member와 Recursive Member의 결과를 합칩. UNION 대신 UNION ALL을 사용하는 이유는 중복을 허용하여 모든 경로를 탐색하기 위함이다.
• 즉, Anchor Member는 초기값만 정의한 후 Recursive Member에서 반복하여 UNION ALL을 통해 모든 경로 탐색