퀴즈로 배우는 SQL
[퀴즈] 경우의 수 구하기 0 5 99,999+

by 마농 SYS_CONNECT_BY_PATH NOCYCLE CONNECT BY PRIOR 경우의수 CROSS JOIN 계층구조 ORA-01436 [2012.06.18]


  이번 퀴즈로 배워보는 SQL 시간에는 주어진 코드 리스트를 이용해 조합 가능한 모든 경우의 수를 구하는 쿼리를 어떻게 작성하는지에 대해 알아본다.

  지면 특성상 문제와 정답 그리고 해설이 같이 있다. 진정으로 자신의 SQL 실력을 키우고 싶다면 스스로 문제를 해결 한후 정답과 해설을 참조하길 바란다.

  공부를 잘 하는 학생의 문제집은 항상 문제지면의 밑바닥은 까맣지만 정답과 해설지면은 하얗다는 사실을 잊지 말자.

문제

  다음과 같은 코드 목록을 가진 테이블([표 1] 참조)에서 코드들을 조합하여 만들어 낼 수 있는 모든 경우의 수에 대한 결과를 출력하는 쿼리를 작성하세요.

  [리스트 1]의 쿼리를 실행하면 [표 1]의 원본 테이블 자료가 조회됩니다. [리스트 1]의 WITH문을 이용하여 [표 2]의 결과 테이블 자료가 조회되는 쿼리를 작성하세요. 마찬가지로 [표 3]의 결과 테이블 자료가 조회되는 쿼리를 작성하세요.

문제설명

  코드 3개로 구할 수 있는 경우의 수는 코드 1개일 때의 조합, 2개일 때의 조합, 3개일 때의조합을 모두 구하면 됩니다.

  코드의 개수는 정해져 있지 않습니다. 즉, 가변적으로 늘어날 수 있습니다. 이때 두 가지 방식의 경우의 수에 대한 정답을 각각 작성하셔야 합니다.

  코드 두 개로 이루어진 조합을 예를 들면 'A-B' 조합과 'B-A' 조합에 대해 서로 같은 조합으로 간주하여 'A-B' 하나만 조회되도록 [표 2]의 결과 집합을 만드는 것이 첫 번째 문제입니다.

  두 번째 문제는 'A-B' 조합과 'B-A' 조합에 대해 서로 다른 조합으로 간주하여 각각 조 회되도록 [표 3]의 결과 집합을 만드는 것입니다.

  • [리스트1] 원본 리스트
CREATE TABLE TEST AS
(
	SELECT 'A' code FROM dual
	UNION ALL SELECT 'B' FROM dual
	UNION ALL SELECT 'C' FROM dual
);

SELECT code
FROM test
;

  • [표 1] 원본 테이블
CODE
A
B
C

  • [표 2] 결과 테이블1 : 순서와 무관한 경우의 수
CODE
A
B
C
A-B
A-C
B-C
A-B-C

  • [표 3] 결과 테이블2 : 순서까지 고려한 경우의 수
CODE
A
B
C
A-B
A-C
B-A
B-C
C-A
C-B
A-B-C
A-C-B
B-A-C
B-C-A
C-A-B
C-B-A

정답

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

  • [리스트2] 정답 리스트 : 순서와 무관한 경우의 수
SELECT SUBSTR(SYS_CONNECT_BY_PATH(code,'-'),2) code
  FROM test
CONNECT BY PRIOR code < code
  ORDER BY LEVEL, code
;

  • [리스트3] 정답 리스트 : 순서까지 고려한 경우의 수
SELECT SUBSTR(SYS_CONNECT_BY_PATH(code,'-'),2) code
  FROM test
CONNECT BY NOCYCLE PRIOR code != code
  ORDER BY LEVEL, code
;

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

해설

  오라클에서 제공되는 계층 구조 쿼리를 이용해 문제를 풀었습니다.

  계층 구조 쿼리의 기본적인 사용법에 대해 알아보고 이 문제를 풀기 위해 계층 쿼리를 어떻게 응용했는지 알아보도록 하겠습니다. 그전에 먼저 계층구조 쿼리가 아닌 셀프 조인 방법을 통해 경우의 수를 구하는 방법도 함께 알아보고 차이점을 비교해 보도록 하겠습니다.

  경우의 수를 구하기 위해 먼저 Cross Join 을 이용해 보도록 하겠습니다.

  Cross Join은 두 집합간에 연결고리 없이 모든 경우의 수로 조인을 하는 것을 말합니다.이렇게 연결된 집합을 Cartesian Product 이라고도 합니다. Cross Join 을 이용하여 3개 코드를 이용한 두 개 조합을 만들어 보도록 하겠습니다.

  • [리스트4] Cross Join 을 이용하여 3개 코드를 이용한 두 개 조합
SELECT t1.code code1
     , t2.code code2
FROM test t1
   , test t2
;

-- 조회 결과
CODE1 CODE2
----- -----
A     A
B     A
C     A
A     B
B     B
C     B
A     C
B     C
C     C

  test 테이블을 두 번 사용하여 Self Join 했습니다.

  이 때 아무런 조건을 주지 않음으로 인해 결과 집합의 수는 각의 집합의 수의 곱셈 결과와 같습니다. 즉, 3:3 조인의 결과 3*3=9건의 자료가 조회되었습니다.

  이렇게 나온 집합에서 CODE1과 CODE2가 같은 결과는 필요가 없습니다. 또한 'A-B' 와 'B-A' 는 같은 조합으로 간주하므로 'B-A'조합 또한 필요가없습니다.

  이러한 조건을 조인조건으로 사용해 보도록 하겠습니다.

  • [리스트5] 조인 조건 추가
SELECT t1.code code1
     , t2.code code2
FROM test t1
   , test t2
WHERE t1.code < t2.code
;

-- 조회 결과
CODE1 CODE2
----- -----
A     B
A     C
B     C

  t1.code < t2.code 조건을 추가하여 우리가 원하는 코드 두 개의 조합이 완성되었습니다. 이를 이용하여 1개 조합과 3개 조합을 함께 만들어 보도록 하겠습니다.

  • [리스트6] 각 개수별 조합의 합집합
SELECT code
  FROM test
 UNION ALL
SELECT t1.code || '-' || t2.code
  FROM test t1
     , test t2
 WHERE t1.code < t2.code
 UNION ALL
SELECT t1.code || '-' || t2.code || '-' || t3.code
  FROM test t1
     , test t2
     , test t3
WHERE t1.code < t2.code
AND t2.code < t3.code
;

-- 조회 결과
CODE
----------
A
B
C
A-B
A-C
B-C
A-B-C

  셀프 조인을 이용하여 경우의 수 결과가 나오긴 했습니다만 쿼리가 복잡하고 코드 개수가늘어날 때마다 UNION ALL 쿼리가 추가되어야 하는 부담이 있습니다.

  셀프 조인이 자기 자신의 테이블과 조인하는 것이므로 이와 유사한 개념을 가진 재귀쿼리의개념을 도입하여 문제를 해결해 보도록 하겠습니다.

  오라클에서만 제공되는 재귀쿼리 또는 계층구조쿼리라고 불리는 것이 있습니다. 간단하게 그 사용법을 살펴 보면 다음과 같습니다.

  • [리스트7]
WITH test AS
(
SELECT 'A' 코드, '' 부모코드 FROM dual
 UNION ALL SELECT 'B', 'A' FROM dual
 UNION ALL SELECT 'C', 'B' FROM dual
)
SELECT 코드
     , 부모코드
     , LEVEL 레벨
     , SYS_CONNECT_BY_PATH(코드, '-') 계층경로
  FROM test
 START WITH 부모코드 IS NULL -- 계층 전개의 시작 조건
 CONNECT BY PRIOR 코드 = 부모코드 -- 계층 전개를 위한 연결 조건
;


-- 조회 결과
코드  부모코드   레벨 계층경로
---- -------- ------ ----------
A                  1 -A
B    A             2 -A-B
C    B             3 -A-B-C

  테이블은 코드와 부모코드로 구성되어 있으며 START WITH 구문을 통해 계층구조의 시작 조건을 기술해 주고 CONNECT BY 절에서 부모와 자식 간의 연결고리 조건을 기술해 줍니다.

  이때 사용되는 PRIOR 는 상위 노드의 값을 참조하겠다는 의미입니다.

  즉, PRIOR 코드 = 부모코드 조건은 상위노드의 코드가 하위노드의 부모코드와 같다는 조건 이 됩니다. 이렇게 코드와 직상위코드의 연결구조만 있는 테이블에 계층구조 쿼리를 이용하 게 되면 상위코드에 하위코드가 연결되고 또 그 하위코드에 하위코드가 연결되는 방식의 결 과를 얻을 수 있습니다.

  SELECT 절에서 사용된 LEVEL은 계층의 깊이를 의미하고, CONNECT_BY_PATH 는 해당 레벨까지 도달하는 연결 경로를 모두 표현해 줍니다.

  이러한 계층구조 쿼리는 다양한 분야에서 많이 사용이 되고 있지만, 대부분의 개발자들은 정확한 의미를 모른 채 기본 형식만을 사용하고 이를 응용하지 못하는데요. 이번 퀴즈 시간 에는 그 틀을 깨보고자 합니다.

  문제에서 주어진 테이블에는 코드만 있고 부모코드는 존재하지 않습니다.

  하지만 부모코드가 반드시 있어야 하는 것은 아닙니다. 부모와 자식간의 관계만 명확하게 표현해 주기만 하면 되는 것입니다. [표 2]의 결과에서 하이픈('-')으로 표현된 부분을 부 모 자식간의 관계라고 생각한다면 부모코드가 자식코드보다 작다는 공통 조건을 생각할 수 있습니다.

  이 조건은 이미 Cross Join 방법에서도 이미 사용되었던 조건입니다.

  CONNECT BY 정해졌습니다. START WITH에는 어떤 조건이 오면 될까요?

  우리는 모든 경우의 수를 구해야 하기 때문에 시작점을 한정지을 필요가 없습니다. 즉 START WITH 절을 생략하여 3개 코드 모두가 시작점이 되도록 할 수 있습니다.

  그럼 위 사항들을 이용해 계층 쿼리를 만들어 보도록 하겠습니다.

  • [리스트8] 계층구조쿼리 전개
SELECT code
     , LEVEL lv
     , SYS_CONNECT_BY_PATH(code,'-') path
FROM test
CONNECT BY PRIOR code < code
;


-- 조회 결과
CODE       LV PATH
---- -------- -------
A           1 -A
B           2 -A-B
C           3 -A-B-C
C           2 -A-C
B           1 -B
C           2 -B-C
C           1 -C

  [리스트8]의 결과를 레코드별로 차례대로 분석해 보면 'A'에서 시작하여 'B'로 연결되고 다시 'C'로 연결되는 구조임을 알 수 있고, 'A'에서 'C'로 연결이 되고, ’B'에서 시작하여 'C'로 연결이 되며, 'C'에서 시작한 행은 그다음 연결되는 것이 없습니다.

  즉 하위 노드가 상위노드보다 큰 값을 가진다는 아주 단순한 조건만으로 계층구조 쿼리를 전개하여 원하는 형태의결과가 나오게 되었습니다. 이렇게 나은 결과 쿼리를 가공(SUBSTR)하고 원하는 형태로 정렬하면 [리스트 2]의 정답 쿼리를 완성할 수 있습니다.

  자 그럼 두 번째 문제는 어떻게 해결할 수 있을까요?

  마찬가지로 부모 자식간의 관계만 정확하게 파악하면 계층구조 쿼리를 이용해 쉽게 해결이 가능합니다.

  첫 번째 문제의 연결조건이 부모코드가 자식코드보다 작다는 조건이었다면?

  두 번째 문제는 순서까지 고려한 경우의 수 이므로 반드시 자식코드가 부모코드보다 커야 하는 것은 아닙니다. 부모코드가 자식코드와 다르면 연결 조건이 성립되게 됩니다.

  이 조건으로 쿼리를 작성해 보겠습니다.

  • [리스트9] 계층구조쿼리 전개
SELECT SUBSTR(SYS_CONNECT_BY_PATH(code,'-'),2) code
  FROM test
 CONNECT BY PRIOR code != code
 ORDER BY LEVEL, code
;

  실행결과 안타깝게도 오류가 발생하였습니다.

  [ORA-01436: CONNECT BY의 루프가 발생되었습니다]

  PRIOR code != code 의 조건으로 연결하게 되면 ‘A-B-C-A’ 와 같은 형태로 앞에 나왔던 코드가 다시 나올 수도 있게 됩니다. 이렇게 되면 코드들이 무한 반복될 수 있기 때문에 에러를 발생하게 되는 것입니다.

  오라클 9i 버전까지만 해도 이 오류를 손쉽게 해결할 방법이 없었습니다. 하지만 10g 버전에서는 NOCYCLE 옵션으로 간단하게 이를 해결할 수 있습니다.

  CONNECT BY NOCYCLE 하게 되면 반복되는 코드를 만나는 순간 더 이상 다음 코드를 찾지 않 고 멈추게 됩니다. 이렇게 CONNECT BY NOCYCLE PRIOR code != code 조건을 이용하여 두 번 째 문제의 정답을 완성했습니다.

  이번 퀴즈는 계층구조를 이용한 경우의 수 구하기 문제였습니다. 정답 쿼리를 보면 허무할 정도로 간단합니다. 하지만 그 속에 담긴 의미는 결코 간단하지 않습니다. 이번 퀴즈는 계층구조쿼리에 대한 고정관년을 깨보는 시간이었습니다.

- 강좌 URL : http://www.gurubee.net/lecture/2196

- 구루비 강좌는 개인의 학습용으로만 사용 할 수 있으며, 다른 웹 페이지에 게재할 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^

- 구루비 강좌는 서비스 제공을 위한 목적이나, 학원 홍보, 수익을 얻기 위한 용도로 사용 할 수 없습니다.

by 이재현 [2012.07.09 14:01:59]

역쉬 천재...

by Always [2013.03.13 13:22:03]

정말 알려주시는거보면 대단하신거 같아요.
오늘도 더 많이 배웁니다. ^^;

by 허승호 [2013.06.03 13:40:37]
connect by 절으로 로또 경우의 모든 수가 만들어 지는군요~^^;

대단하세요.

by NalRim [2015.02.13 11:00:08]

워 대단합니다. 한수 배워갑니다 감사합니다.


by sarahpark [2020.03.04 15:14:49]

1. 구글링 결과 WM_CONCAT 을 알게되서 써봄.. - 결과 터무니 없음

	WITH TEST AS
	(
		SELECT 'A' code FROM dual
		UNION ALL SELECT 'B' FROM dual
		UNION ALL SELECT 'C' FROM dual
	)
	SELECT   WM_CONCAT(T.CODE)
	FROM     TEST T
	WHERE    1 = 1
	--AND      T.CODE IN ('B', 'A')
	;
	

 

2. 최근에 알게된 LEAD, LAG 함수에 꽂혀서 노가다 방식을 생각해봄. - 결과는 터무니 없음

	SELECT   T.CODE
	FROM     TEST T
	UNION ALL 
	SELECT   T.CODE || ',' || LEAD(T.CODE) OVER (ORDER BY T.CODE) 
	FROM     TEST T
	UNION ALL 
	SELECT   T.CODE || ',' || LEAD(T.CODE) OVER (ORDER BY T.CODE) || ',' || LEAD(T.CODE) OVER (ORDER BY T.CODE) 
	FROM     TEST T
	;

 

3. 셀프 조인을 해 봄 -> AA BB CC와 같은 값을 어떻게 없애야하는지 생각을 더 안함...

부등호 조인 배웠는데!!! 너무 아깝네요

	
	SELECT   *
	FROM     TEST T1, TEST T2
	WHERE    1 = 1
	;
	
댓글등록
SQL문을 포맷에 맞게(깔끔하게) 등록하려면 code() 버튼을 클릭하여 작성 하시면 됩니다.
로그인 사용자만 댓글을 작성 할 수 있습니다. 로그인, 회원가입