파스칼 삼각형
-
[알고리즘] 파스칼의 삼각형 만들기Algorithm Study/Java 2020. 5. 29. 18:43
오늘은 파스칼의 삼각형을 구현하는 방법을 알아볼 것이다. 파스칼의 삼각형은 위 그림처럼 생긴 삼각형으로 각 층의 양 끝은 1이고 나머지 값은 위층에 있는 값의 합으로 구성되어 있다. 이 삼각형이 가지고 있는 의미는 여러가지가 있겠지만 대표적으로 삼각형의 각 항목이 조합으로 표현되는 Combination의 각 항목을 나타내고 있다는 점이다. 예를 들어 1C0 부터 6C6까지의 조합을 나타낸 것과 파스칼의 삼각형의 위에서 2번 ~ 7번 층의 항목이 동일하다는 것을 알 수 있다. 그럼 이 파스칼의 삼각형을 어떻게 활용할 수 있을까? 조합의 경우 n!의 연산을 수행해야하기 때문에 n의 크기가 커지면 int형으로 나타낼 수 있는 범위를 초과하는 문제가 발생한다. 이 때, 파스칼의 삼각형을 이용하면 각 항목 nCk..