[프로그래머스 LV5][SQL] 멸종위기의 대장균 찾기

프로그래머스

문제 풀이

-- 코드를 작성해주세요
with recursive tmp as (
    select id, parent_id, 1 as generation
    from ecoli_data
    where parent_id is null
    union all
    select s.id, s.parent_id, tmp.generation + 1
    from tmp join ecoli_data s
    on tmp.id = s.parent_id
)

select count(*) AS count, generation
from tmp
where id not in (
    select distinct parent_id
    from tmp
    where parent_id is not null)
group by generation
order by generation;

 

정리

WITH RECURSIVE tmp AS (
    ...
)

WITH RECURSIVE는 재귀 CTE(Common Table Expression)라고 불리며, 계층 구조(트리 구조처럼 부모-자식 관계가 있는 데이터)를 쿼리로 탐색할 때 사용

CTE(Common Table Expression)는 일시적인 테이블을 만드는 문법

RECURSIVE는 이 CTE가 자기 자신을 다시 참조할 수 있다는 뜻

트리 구조, 계층 구조를 쿼리로 타고 내려가거나 올라갈 때 주로 사용

 

여기서 tmp는 CTE(Common Table Expression)의 이름이자 별칭(alias)

즉, tmp는 일시적으로 만든 임시 테이블처럼 쓰는 이름
그 안의 SELECT 결과를 테이블처럼 다룰 수 있게 됨

 

첫 번째 부분: 기저 조건 (anchor member)

select id, parent_id, 1 as generation
from ecoli_data
where parent_id is null

 

기본 세균(부모 없는, 즉 시조 세균)만 가져옴

generation = 1 세대로 간주

 

 

두 번째 부분: "재귀 조건 (recursive member)

union all
select s.id, s.parent_id, tmp.generation + 1
from tmp
join ecoli_data s
on tmp.id = s.parent_id

 

앞서 찾은 세균들(tmp)을 기준으로, 그 자식 세균들(s)을 계속 찾음

자식 세균은 세대가 1 증가

2까지만 만들어지지 않고 계속 깊이 내려감

재귀 CTE (WITH RECURSIVE)는 자식이 더 이상 없을 때까지 자동으로 반복

 

ex)

tmp에 id=1 (generation=1)이 있으면,

ecoli_data에서 parent_id=1인 애들(id=2, id=3)을 찾아서

그들을 generation=2로 추가.

 

 

1 as generation

generation"이라는 이름의 칼럼을 만들고 그 값은 1로 고정한다

 

UNION ALL

WITH RECURSIVE tmp AS (
    -- ① anchor member
    SELECT ... -- (시작점)
    
    UNION ALL
    
    -- ② recursive member
    SELECT ... -- (재귀적으로 이어감)
)

여기서 UNION ALL은 두 SELECT 결과를 하나로 합쳐서 계속 이어가라는 의미

WITH RECURSIVE는 다음과 같은 순서로 동작

1. anchor member가 먼저 실행됨 → generation = 1인 데이터 생성됨
2. 그 결과를 기반으로 recursive member가 실행됨
3. 그 결과도 tmp에 추가됨
4. 그걸 다시 기반으로 다음 generation 찾음…
5. … 이 과정을 자식이 더 이상 없을 때까지 반복

이걸 가능하게 만드는 게 UNION ALL

 

• UNION은 중복을 제거
• UNION ALL은 중복을 제거하지 않고 그대로 다 합침.

세 번째 부분

select count(*) count, generation
from tmp
where id not in (
    select distinct parent_id
    from tmp
    where parent_id is not null
)
group by generation
order by 2

tmp 테이블에서 조건에 맞는 행만 골라서 count

where id not in (
    select distinct parent_id
    from tmp
    where parent_id is not null
)

 

tmp에서 다른 세균의 부모로 등장하지 않은 세균들만 고름

즉, 자식이 없는 말단 세균(leaf node)만 남김