조합론 - C++ 로 구현한 카탈란 수(Catalan Number), 원리와 응용
- 최초 등록일
- 2007.08.19
- 최종 저작일
- 2007.08
- 4페이지/ MS 워드
- 가격 1,000원
소개글
조합론의 주요 수열 중 하나인 카탈란 수(Catalan Number) 에 대해서 정리한 리포트입니다.
응용사례 및 실제 동작하는 구현 소스코드가 포함되어 있어 프로그래밍 및 이산수학을 공부하시는 분들께 매우 유용합니다.
목차
조합론 - 카탈란 수(Catalan Number)
1. 개요
2. 설명
3. Catalan Number 가 적용되는 예
4. Catalan Number 구현 (C++)
5. 참고문헌
본문내용
조합론 – 카탈란 수 (Catalan Number)
조합론에서는 일정한 규칙을 가진 수열이 자주 등장한다. 대표적인 예가 바로 피보나치 수열(Fibonacci Numbers) 이며, 이 외에도 여러 가지 수열들이 많은데, 여기에서는 조합론에서 자주 등장하는 수열 중 하나인 카탈란 수에 대해서 알아보기로 한다.
1. 개요
카탈란 수(Catalan Number) 란 다음과 같이 정의되는 수를 말하며, 여러 응용 분야가 존재하여 조합론 분야와 프로그래밍 경시대회와 같은 문제풀이 대회에서 매우 자주 등장한다.
= =
이는 주어진 조건들이 2(n-1) 개인 상태에서 n-1 개 만큼 선택하는 경우의 수들이 된다.
Catalan Number 의 첫 10개는 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 이 된다.
2. 설명
각각 n 개의 왼쪽, 오른쪽 괄호가 있을 때 괄호의 짝을 맞춰서 식을 만드는 경우의 수는 얼마일까? 예를 들어 n = 3 인 경우에는 ((())), ()(()), (())(). (()()), ()()() 이렇게 다섯 가지 방법이 있다.
맨 왼쪽에 있는 괄호 l 은 오른쪽에 있는 어떤 괄호 r 에 매치되며 이 괄호들은 전체 식을 l 과 r 사이에 있는 부분과 r 오른쪽에 있는 부분, 이렇게 두 개의 균형 잡힌 식으로 나눈다. l 과 r 이 한 쌍을 이루므로, 왼쪽 부분에 k쌍의 괄호가 있다면, 오른쪽 부분에는 n-k-1 쌍의 괄호가 있어야 한다.
N 개의 짝을 가진 괄호가 입력될 때, 이 괄호들의 짝을 맞추는 방법의 수
참고 자료
Tom Davis – Catalan Numbers, November, 26, 2006
Programming Challenges