[SQL] MySQL에서 재귀 구현하기 (프로그래머스 - 멸종위기의 대장균 찾기)

나는 SQL 기본 문법밖에 모르는 사람이다. 코딩테스트 공부를 하던 중, 재귀로 풀어야 하는 문제를 만났는데 아무리 생각해도 이전의 값을 가져와야 하기 떄문에 내가 아는 방식으로는 풀어낼 수 없었다. 그래서 찾아보았는데, SQL문법에도 재귀가 있었다. 그래서 이거를 정리해보고자 한다.

 

재귀를 이용해야 했던 문제는 아래 링크로 달아두었다.

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

프로그래머스

 

---

 간단한 문제설명

문제를 간단히 설명하자면, 균이 번식을 하고 균의 부모id가 주어진다. 결론적으로는 자식이 없는 균의 세대를 구하고 세대 별 균의 수를 구하는 문제였다.

문제를 읽었을 때 생각한 건, 재귀가 필요하고 셀프조인을 해야하는 문제라는 거였다. 셀프조인이야 많이 배웠으니,, 괜찮지만 재귀는 SQL에서 써본적이 없었기에 공부가 필요하다 생각했다. (이런 무지함으로 코테를 치던 내 자신이 안쓰럽다)

 

 

SQL로 재귀 구현하기

WITH RECURSIVE rc AS (

    ━━━ ① 기저 파트 ━━━━━━━━━━━━━━━━━━━━━━━━━
    SELECT id, parent_id, 1 AS generation
    FROM   ecoli_data
    WHERE  parent_id IS NULL

    UNION ALL           ← 반드시 이 키워드로 연결

    ━━━ ② 재귀 파트 ━━━━━━━━━━━━━━━━━━━━━━━━━
    SELECT e.id, e.parent_id, rc.generation + 1
    FROM   ecoli_data e
    JOIN   rc ON e.parent_id = rc.id
                      ↑ 자기 자신(cte_name)을 테이블처럼 JOIN

)

 

먼저 재귀를 생성해준다.

WITH RECURSIVE 이름 AS (구현내용)

 

저 이름을 가지고 테이블처럼 사용할 수 있다!

 

구현 내용 안에는 기저파트와 재귀파트를 분리해서 구현해주면 된다. 

위 문제에서는 부모id가 null인 균이 1세대라고 했으므로 기저파트를 위와 같이 작성해주었고 재귀파트에서는 이를 +1씩 해나갈 수 있도록 작성해주었다.

기저파트와 재귀파트는 UNION ALL로 연결해주면 된다. 

 

 

저렇게 만들어진 재귀를 이용해 select로 문제를 풀어주었다.

with recursive rc as(
    select id, 1 as generation from ecoli_data
    where parent_id is null
    
    union all
    
    select e1.id, rc.generation + 1
    from ecoli_data e1
    join rc on rc.id = e1.parent_id
)

select count(*) as count, generation 
from ecoli_data e, rc
where e.id = rc.id 
and e.id not in (
	select e1.id 
	from ecoli_data e1, ecoli_data e2
	where e1.id = e2.parent_id
)
group by generation
order by generation
;

 

SQL은 문법에서 특히 구멍이 많은 거 같다. 정진합시다~!