꿈꾸는 개발자, DBA 커뮤니티 구루비

이번 퀴즈로 배워보는 SQL 시간에는 개미 수열 쿼리 문제를 풀어본다. 지면 특성상 문제와 정답 그리고 해설이 같이 있다.

진정으로 자신의 SQL 실력을 키우고 싶다면 스스로 문제를 해결한 다음 정답과 해설을 참조하길 바란다. 공부를 잘하는 학생의 문제집은 항상 문제지면의 밑바닥은 까맣지만 정답과 해설지면은 하얗다는 사실을 기억하자.

문제

다음과 같은 수열이 있습니다. 9번째 수는 무엇일까요? <표 1> 형태의 결과를 도출하는 SQL을 작성하세요

[표 1] 개미 수열

        N V
--------- ------------------
        1 1
        2 11
        3 12
        4 1121
        5 122111
        6 112213
        7 12221131
        8 1123123111
        9    ?

문제설명

수열의 규칙을 찾아내고, SQL로 구현하는 문제입니다.

이 수열 은 우리나라에서 인기가 좋은 프랑스 소설가 베르나르 베르베르의 소설 ‘개미’를 통해 소개가 되면서 많이 알려지게 된 수열로 일명 개 미 수열이라고 합니다.

1로 시작되는 이 수열은 다음에는 1이 1개 있다는 의미로 11이, 11은 1이 2개 있으므로 12가, 12는 1이1개, 2가1 개이므로 1121이 됩니다.

이렇게 동일한 숫자가 몇 개 연속인지를 세어 붙이면 다음 수가 되 는 것입니다.

수열이 계속 진행이 되면 9번째 수는 12213111213113 이 됩니다. 독자 여러분들께서는 9번째 수를 맞히셨나요?

그럼 이 제 수열의 규칙을 알았으니 이 규칙을 이용해 SQL을 작성하는 것 이 문제입니다.

정답

문제를 스스로 해결해 보셨나요? 이제 정답을 알아보겠습니다.

[리스트 1] 정답 리스트

WITH t(n, v, x) AS
(
SELECT 1 n
     , CAST('1' AS VARCHAR2(100)) v
     , CAST('' AS VARCHAR2(100)) x
  FROM dual
 UNION ALL
SELECT NVL2(x, n, n+1) n
     , NVL2(x, v||SUBSTR(x, 1, 1)
                ||LENGTH(REGEXP_SUBSTR(x, '^(.)(\1)*'))
             , SUBSTR(v, 1, 1)
                ||LENGTH(REGEXP_SUBSTR(v, '^(.)(\1)*'))
            ) v
     , REGEXP_REPLACE(NVL(x, v), '^(.)(\1)*') x
  FROM t
 WHERE NVL2(x, n, n+1) < = 9
)
SELECT n, v
  FROM t
 WHERE x IS NULL
;

어떤가요? 여러분이 만들어본 리스트와 같은가요? 틀렸다고 좌절할 필요는 없답니다. 첫 술에 배부를 순 없는 것이니까요. 해설을 꼼꼼히 보고 자신이 잘못한 점을 비교해 보는 것이 더 중요합니다.

해설

수열 문제입니다. 일정한 규칙에 의해 다음 수를 만들어 내야 합 니다. 개미 수열에서 사용된 규칙은 복잡한 수학 공식이 들어 있지 않고, 단순하게 이어진 숫자의 개수를 세어 숫자와 개수를 이어 붙 이는 방식으로 이루어집니다.

산술적인 계산식이 존재한다면 적용하기 오히려 쉬울 텐데요. 계산식이 없습니다. N이라는 숫자만 일정한 공식에 대입하면 결과 값을 알 수 있는 수열이 대부분인데 반해 이 개미 수열은 공식이 없 이 차근차근 차례대로 결과를 만들어 나가야 합니다.

다시 말하면 정해진 공식에 의한 구조적 질의가 불가능하며, 절 차적인 처리를 해야만 가능하다는 결론이 나옵니다.

SQL 태생 자 체가 절차적인 프로그래밍 언어를 대체하는 구조적인 질의어로 탄 생을 한 것이기 때문에 SQL에서는 절차적 처리가 불가능합니다. 절차적 처리는 별도로 PL/SQL을 이용해야만 합니다.

그렇다면 SQL 로는 불가능하다는 결론이 나오는데요. 절차적 처리가 불가 능하다는 단점이 존재했는데요. SQL도 진화를 하고 있습니다. 기 존에는 절차적 처리가 전혀 불가능했었지만, 이제는 어느 정도는 가능하게 됐습니다. 문제를 풀기 전에 좀 더 간단한 예제를 살펴보 도록 하겠습니다.

[리스트 2] 누적 수량 - 재귀SQL

WITH t(n, v) AS
(
  SELECT 1, 1 FROM dual
   UNION ALL
  SELECT n + 1 AS n
       , v + n + 1 AS v
    FROM t
   WHERE n + 1 < = 10
)
SELECT * FROM t
;

[표 2] 누적 수량 - 재귀SQL

     N          V
------ ----------
     1          1
     2          3
     3          6
     4         10
     5         15
     6         21
     7         28
     8         36
     9         45
    10         55

<리스트 2>의 쿼리를 수행하여 <표 2>의 결과를 얻었습니다. 오라클 11G의 새 기능인 재귀쿼리(Recursive SQL)입니다.

<리스트 2>의 쿼리는 매우 특이한 형태로 구성됩니다. WITH 로 정의 한 집합 t 가 WITH 구문 안에서 사용이 되고 있습니다.

WITH 구 문 안은 UNION ALL 로 묶인 두 개의 SELECT 절로 구성이 되며 첫 번째 SELECT 구문을 시작으로 해당 결과를 두 번째 SELECT 절에서 재사용하면서 UNION ALL 로 결과를 붙여나가는 구조입 니다

처음 n=1, v=1을 시작으로 해당 n값에 1을 더해 두 번째 n값이 됩니다. 즉, n은 1씩 증가하는 구조로 n+1< =10 조건에 의해 10까 지만 증가하고 멈추게 됩니다. v는 이렇게 매 행 증가하는 n 값을 누적 합산한 값이 됩니다.

이전 행의 결과를 읽어와 현재행의 결과를 도출하는 절차적인 SQL입니다. 물론, 이 문제는 개미수열과 달리 매우 간단해 절차 적인 문제가 아닌 집합적 문제, 계산공식 문제로 접근이 가능합 니다.

[리스트 3] 누적 수량 - 분석함수/계산공식

SELECT n
     , SUM(n) OVER(ORDER BY n) AS v1
     , (n + 1) * n / 2 AS v2
  FROM (SELECT LEVEL n
          FROM dual
       CONNECT BY LEVEL < = 10
       )
;

[표 3] 누적 수량 - 분석함수/계산공식

       N         V1         V2
-------- ---------- ----------
       1          1          1
       2          3          3
       3          6          6
       4         10         10
       5         15         15
       6         21         21
       7         28         28
       8         36         36
       9         45         45
      10         55         55

<리스트 3>의 쿼리를 수행하여 <표 3>의 결과를 얻었습니다. 분 석함수를 이용하여 집합적인 방식으로 구할 수도 있습니다.

, SUM(n) OVER(ORDER BY n) AS v1

일정한 수열의 규칙을 찾아 공식화하여 구할 수도 있습니다.

, (n + 1) * n / 2 AS v2

하지만 개미수열은 이보다 복잡하여 이러한 방식을 적용하기 어 렵습니다. 따라서 재귀SQL을 통해 문제에 접근해 보도록 하겠습 니다.

[리스트 4] 계산 과정

WITH t(n, v, x) AS
(
SELECT 1 n
     , CAST('1' AS VARCHAR2(100)) v
     , CAST('' AS VARCHAR2(100)) x
  FROM dual
 UNION ALL
SELECT NVL2(x, n, n+1) n
     , NVL2(x, v||SUBSTR(x, 1, 1)
                ||LENGTH(REGEXP_SUBSTR(x, '^(.)(\1)*'))
             , SUBSTR(v, 1, 1)
                ||LENGTH(REGEXP_SUBSTR(v, '^(.)(\1)*'))
           ) v
     , REGEXP_REPLACE(NVL(x, v), '^(.)(\1)*') x
  FROM t
 WHERE NVL2(x, n, n+1) < = 9
)
SELECT * FROM t;

[표 4] 계산 과정

       N V                              X
-------- ------------------------------ ------------------
       1 1
       2 11
       3 12
       4 11                             2
       4 1121
       5 12                             21
       5 1221                           1
       5 122111
       6 11                             22111
       6 1122                           111
       6 112213
       7 12                             2213
       7 1222                           13
       7 122211                         3
       7 12221131
       8 11                             2221131
       8 1123                           1131
       8 112312                         31
       8 11231231                       1
       8 1123123111
       9 12                             23123111
       9 1221                           3123111
       9 122131                         123111
       9 12213111                       23111
       9 1221311121                     3111
       9 122131112131                   111
       9 12213111213113

<리스트 4>의 쿼리를 수행하여 <표 4>의 결과를 얻었습니다. < 표 4>의 결과를 차례대로 설명하겠습니다.

1행은 초기 값으로 1, ‘1’, ‘’로 시작됩니다. 2행은 1행의 V값 ‘1’이 1이 1개 있으므로 ‘11’이 되며 N 값이 증가해 2가 됩니다.

3행은 2행의 V값 ‘11’이 1이 2개 있음으로 ‘12’가 되며 N 값이 증가해 3이 됩니다. 4행은 3행의 V값 ‘12’가 첫 글자 1이 1개 있으므로 ‘11’로 표현하고 아직 처리하지 못 한 ‘2’를 X에 남겨둡니다.

그리고 아직 값이 남아 있으므로 N값은 증가하지 않습니다. 5행은 V값이 아닌 남아있는 X값을 기준으로 동작합니다.

남아 있는 X값 ‘2’와 2가 1개 있으므로 ‘21’이, 이 값을 이전 V값 ‘11’에 붙여 ‘1121’이 되며, 남아 있는 X값이 없으므로 N 값이 증가하 여 4가 됩니다.

이렇듯 첫 글자 연속 값에 대한 처리를 하여 V에 붙여나가면서 첫 글자 연속 값을 제거하고 남은 글자를 X 에 남겨 둡니다. 글자가 남아 있는 경우 N 은 증가하지 않습니다.

X에 값이 남아 있다는 것은 아직 V값이 완결되지 않은 진행형임 을 의미합니다. X에 값이 없다는 것은 V값의 완결을 의미합니다. 이렇게 계속 진행하여 최종 원하는 수인 9만큼 진행하고 멈추면 되는 것입니다.

지금까지 <표 4> 결과 값의 의미를 살펴봤습니다. 이번에는 <리 스트 4>에서 이를 어떻게 구현했는지 살펴보겠습니다. N값은 완성된 결과의 행번호를 의미하며 X값의 존재유무에 따 라 증가여부가 결정됩니다.

      NVL2(x, n, n+1) n

NVL2 함수를 이용하여 이를 구현하였습니다. V값은 결과 값이 며 이 전행 첫 글자의 수를 세어 붙여나가는 값입니다.

X값이 존재 한다면 X에서 값을 구해 V에 연결해 붙이며, X값이 없다면 V값에 서 새로 시작합니다. 이 조건 분기 또한 NVL2 함수로 제어 했으며 연속된 첫 글자를 잘라내는 것은 정규표현식을 이용했습니다.

     , NVL2(x, v||SUBSTR(x, 1, 1)
                ||LENGTH(REGEXP_SUBSTR(x, '^(.)(\1)*'))
             , SUBSTR(v, 1, 1)
                ||LENGTH(REGEXP_SUBSTR(v, '^(.)(\1)*'))
           ) v

‘^’ 은 문자열의 시작을 의미하고 ‘.’ 은 모든 문자를 의미합니다. 이 둘을 합치면 첫 글자를 의미합니다. ‘\1’ 은 앞에서 나온 첫 번 째 괄호안의 문자를 의미합니다. ‘*’은 0개 이상이 연속됨을 의미합 니다.

즉, 이 모든 표현식을 하나로 묶으면 첫 글자 다음에 같은 문자 가 0개 이상 반복됨을 의미합니다. REGEXP_SUBSTR은 위 패턴 문자열을 잘라내는 정규표현 함수입니다. 이렇게 잘라낸 연속문자 의 길이를 LENGTH 함수를 이용해 구하고, SUBSTR함수로 잘라 낸 첫 글자에 이 길이를 연결합니다.

즉, X값이 없을 때까지 X값을 이용해 V값을 계속 붙여나가면서 결과를 완성시키고, 결과가 완성된 후 다음 값은 V값으로 만들어 내는 것입니다.

X값은 V값을 완성해 나가는 과정에 남은 부분을 의미합니다. 초기 완성된 V값에서 첫 연속글자를 제거하고 남은 부분이 되며, 완성되지 않은 V값일 경우엔 X값으로부터 첫 연속글자를 제거하 고 남은 부분이 됩니다.

반대로 말하면 X값이 있으면 X에서 잘라내고 없으면 V에서 잘 라냅니다. 잘라내는 대상은 NVL 함수를 이용해 구현했으며, 잘라 내는 방법은 정규식 REGEXP_REPLACE를 이용했습니다.

      , REGEXP_REPLACE(NVL(x, v), '^(.)(\1)*') x

이렇게 차근차근 절차적으로 접근해 나가면서 최종 원하는 수만 큼 도달하면 멈춥니다.

 WHERE NVL2(x, n, n+1) < = 6

재귀SQL에서 이 조건은 상당히 중요합니다. 자칫 잘못하면 무 한 루프에 빠질 수도 있으니 반드시 기술해 주어야 하는 부분입니 다. V와 X값은 계속해서 글자 수가 늘어나게 됩니다.

     , CAST('1' AS VARCHAR2(100)) v
     , CAST('' AS VARCHAR2(100)) x

따라서 CAST 함수를 이용해 충분한 자리수를 확보해 줍니다. 이렇게 하지 않으면 에러를 만나게 됩니다. 재귀SQL의 문법적 특 징은 또 있습니다.

  WITH t(n, v, x) AS

WITH 구문에서 반드시 컬럼명을 나열해 주어야만 합니다. 잠깐 문법적인 특징들과 오류가 나지 않도록 작성하는 부분을 살펴봤습 니다. <표 4>의 결과는 우리가 원하는 최종 결과는 아니죠. 최종 결과를 도출하기 위한 중간 단계입니다.

SELECT n, v
  FROM t
 WHERE x IS NULL
;

최종 결과를 도출하기 위해서는 마지막으로 X값이 없는 것만 추 려내고 결과를 도출하기 위한 임시 변수 X를 제거하고 필요한 N, V 항목만 SELECT절에 기술하면 됩니다.

이번 퀴즈로 배우는 SQL 시간에는 일상에서 재미있게 접했었던 개미수열 문제를 SQL을 이용해 풀어보았습니다.

집합적, 구조적 언어인 SQL의 한계(절차적 쿼리 불가)를 이해하고, 오라클 11G의 새로운 기능인 재귀쿼리(Recursive SQL)를 이용해 절차적인 처리 가 가능함을 소개했습니다. 잘 알아두면 SQL의 한계를 극복하는 좋은 TIP이 될 것입니다.