2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/정보영재

2018년 정보올림피아드 지역예선 중등부 15번 카탈란수 관련 문제 풀이

원당컴퓨터학원 2018. 6. 8. 13:04

2018년 중등부 15번


정답이 56이 나오는 문제였는데 지문에 정답이 없어서 이슈가 되었던 문제입니다.

올바른 괄호짝이 아닌 문자열이 모두 몇개인지 확인하려면 모든 경우의 수에서 올바른 괄호짝을 찾아서 그 경우를 빼 주면 되는 문제네요.


4개의 짝으로 만들 수 있는 경우- 즉 8개의 (,) 를 가지고 만들수 있는 모든 경우의 수는 8개의 괄호를 순서대로 나열 할 수 있는 모든 경우 8! 에서 ( 가 동일한 모양 4개 ) 가 동일한 모양 4개 이므로 4! * 4! 로 나눈 수가 전체의 경우의 수입니다.

따라서 나올수 있는 모든 경우의 수는 8!/(4!*4!)= 70 가지가 됩니다.


이제 올바른 괄호 짝을 구하는 방법을 찾아 보겠습니다.


이러한 규칙을 찾는 수열 중에 카탈란 수라고 불리우는 수열이 있습니다.

핀란드 수학자 카탈란의 이름을 단 수열이라고 하는데요. 이 수열을 이용하면 간단하게 찾을 수 있습니다.


1에서 n쌍의 괄호가 잘 짜놓는 방법의 수를 Cn 이라고 하면 C0,C1,C2...,Cn-1 을 이용하여 Cn 을 찾는 방법을 살펴 보겠습니다.

n-1쌍의 괄호가 잘 짜여진 것에 ()를 알맞은 곳에 넣어 주는 방법을 세면 됩니다.

(A)B와 같이 넣는다고 하면 A도 잘 짜여진 괄호가 되어 있어야 하고 B도 잘 짜여져 있어야 합니다.

만약 A에 괄호가 k쌍이 있다면 B에는 n-1-k 쌍이 있어야 합니다.(n-1 쌍의 괄호의 갯수이므로 A가 k쌍일때 B는 n-1-k쌍)

따라서 A와 B를 나누는 경우를 세면 됩니다.

따라서 다음과 같은 점화식을 얻을 수 있습니다.

C0=1 (괄호쌍이 없는 경우 1가지 존재)

C1=C0C0 (k=0,n-1-k = 0,k=0만 존재)

C2=C0C1 + C1C0

C3=C0C2 + C1C1 + C2C0

C4=C0C3 + C1C2 + C2C1 + C3C0

...

이렇게 계산해 보면 다음의 결과가 나오는 것을 확인 할 수 있습니다.

C0=1

C1=1

C2=1 + 1 = 2

C3=2 + 1 + 2 = 5

C4=5+2+2+5=14


따라서 정답은 70 - 14 = 56 입니다.


그 외에 카탈란수를 이용하여 구할 수 있는 경우는 다음과 같은 경우에 구할 수 있을것 같네요.

  • n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다. (XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY)



정보올림피아드 문제 풀이 리스트 정리




사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기