9. 경우의 수와 알고리즘

문제해결을 위한 알고리즘 입문

이번에는 팩토리얼, 이항계수, 곱의 법칙등 기본적인 경우의 수 공식을 다룹니다. 이 공식들은 프로그램의 계산 횟수를 추정하는 등 다양한 상황에서 매우 중요합니다. 마지막에는 이러한 공식을 활용할 수 있는 3가지 프로그래밍 문제를 소개하여 경우의 수에 익숙해지는 것을 고려했습니다.

(1) 기본공식①: 곱의 법칙

어떤 사건1이 발생하는 방식이 N가지, 사건2가 발생하는 방식이 M가지인 경우, 사건1과 사건2의 조합은 모두 N x M가지가 됩니다. 예를 들어 다음과 같은 상황을 생각해 보겠습니다.

내일 아침식사는 김밥, 식빵, 샌드위치 중 하나입니다.

내일 기상시간은 5:00, 6:00, 7:00, 8:00중 하나입니다.

여기서 내일 아침식사를 '사건1', 내일 기상시간을 '사건2'라고 한다면, 사건1은 3가지, 사건2는 4가지인 경우가 있으므로, 두 사건의 조합은 3 x 4 = 12가지가 됩니다. 이처럼 경우의 수를 곱셈을 통해 구할 수 있는 원리를 곱의 법칙이라고 합니다.

(2) 기본공식②: 곱의 법칙 확장

앞에서 소개한 곱의 법칙은 사건이 3개 이상일 때도 확장할 수 있습니다. 사건1이 발생하는 방식 A1가지, 사건2가 발생하는 방식이 A2가지, ..., 사건N이 발생하는 방식이 AN가지라면, 사건 1, 2, ..., N의 모든 조합은 A1 x A2 X ... X AN가지가 됩니다. 예를 들어 아래 선택지 중에서 '모양', '색상', '기입할 숫자'를 선택하여 오리지널 로고를 만드는 상황을 고려해 봅시다.

모양: 원, 사각형, 삼각형 중 하나

색상: 오렌지색 또는 보라색 중 하나

기입할 숫자: 1, 2, 3, 4 중 하나

따라서, 모양 선택지는 3가지, 색상 선택지는 2가지, 숫자 선택지는 4가지이므로 로고를 만드는 방법은 3 x 2 x 4 = 24가지가 됩니다.아래의 트리 구조 그림을 보면, 각 단계마다 경우의 수가 순서대로 3배, 2배, 4배씩 증가하는 것을 알 수 있습니다.

특히, 선택지가 M가지인 사건이 N개 있는 경우의 조합수는

가지가 됩니다. 예를 들어, 모든 요소가 1 또는 2인 길이 4의 수열 A = (A1, A2, A3, A4)의 경우의 수는

가지입니다. 또한, N개의 물건을 선택하는 방법은 모두

가지가 됩니다.

이는 물건1을 선택하는 방법이 Yes/No, 물건2도 Yes/No, ..., 물건N도 Yes/No, 즉 각각 2가지 경우가 있기 때문입니다.

(3) 기본공식③: n개의 물건을 나열하는 방법의 수는 n!

다음으로 n개의 물건을 나열하는 방법의 수는

n! = n x (n-1) x ... x 3 x 2 x 1

가지가 됩니다. 예를 들어, 정수 1, 2, 3을 나열하는 방법은 3! = 3 x 2 x 1 = 6가지가 있습니다. 방법의 수가 3!가지가 되는 이유를 설명하면 아래와 같은 트리 구조의 그림에서 볼 수 있습니다.

맨 왼쪽에 올 정수를 선택하는 방법은 3가지

가운데에 올 정수는 첫번째 정수를 선택할 수 없으므로 2가지

맨 오른쪽에 올 정수는 이미 2개의 정수를 선택했으므로 1가지

이와 같이 각 위치마다 선택가능한 경우의 수를 곱해주면 전체 경우의 수가 3!가 되는 것을 쉽게 이해할 수 있습니다.

(4) 기본공식④: n개의 물건 중 r개를 배열하는 방법은 nPr

n개의 물건 중에서 r개를 선택하여 일렬로 나열하는 방법의 수는 다음 식으로 표현됩니다.

예를 들어, 사람 A, B, C, D 중에서 2명을 선택하고 그 순서까지 결정하는 방법은 4P2 = 12가지입니다. 이전 항과 같이 '첫번째 사람을 선택하는 방법은 n가지', '두번째 사람은 n-1가지'라고 생각한 후, 곱의 법칙을 적용하면 이 식을 도출할 수 있습니다.

(5) 기본공식⑤: n개의 물건 중 r개를 선택하는 방법은 nCr

n개의 물건 중에서 r개를 선택하는 방법의 수는 아래의 식으로 표현되며, 이를 이항계수라고 합니다.

약간 어려워 보일 수 있지만, 이 식은 nPr의 식과 비교하여 도출할 수 있습니다. r개의 물건을 배열하는 방법은 r!가 있으므로, 순서를 구분하여 셀 경우의 수는 순서를 구분하지 않은 경우의 수보다 r!배 많습니다. 따라서 nPr = r! x nCr가 성립합니다.

예를 들어, 아래 그림은 A, B, C, D중에서 2개의 선택하는 방법이 4C2 = 6가지임을 보여주며, 순서를 구분할 경우, (4P2 = 12가지)는 그 값이 2! = 2배가 되는 것을 알 수 있습니다.

(6) 응용예시①: 쇼핑하는 방법의 수

여기부터 경우의 수 공식을 알고리즘에 응용한 예시들을 소개합니다. 먼저 아래 문제를 생각해 봅시다.

문제

편의점에 N개의 상품이 판매되고 있으며, i번째(1 ≦ i ≦ N) 상품의 가격은 Ai원입니다. 서로 다른 두 상품을 구매하는 방법중에서, 총 가격이 500원이 되는 경우는 몇가지일까요?

제한조건: 2 ≦ N ≦ 200,000, Ai는 100, 200, 300, 400 중 하나

실행시간 제한: 1초

먼저, 상품을 고르는 방법을 전수조사하는 방법을 떠올리게 됩니다. 그러나, N개의 상품 중에서 2개를 선택하므로, 전체 선택 경우의 수는 nC2가지입니다. 따라서, 계산량은

가 되어 비효율적입니다. 그러므로, 다른 방법을 생각해 봅시다. 총 가격이 500원이 되는 쇼핑방법을 생각하면, 아래 2가지 방법만 가능함을 알 수 있습니다.

A방법: 100원짜리 상품1개와 400원짜리 상품1개 구매

B방법: 200원짜리 상품1개와 300원짜리 상품1개 구매

또한, 100원, 200원, 300원, 400원 상품의 갯수를 각각 a, b, c, d개라고 하면, 곱의 법칙에 따라 각 방법에서의 구매 경우의 수는 다음과 같습니다.

A방법: a가지 x d가지 = ad가지

B방법: b가지 x c가지 = bc가지

따라서, 구해야 하는 답은 ad + bc가 됩니다. a, b, c, d의 값은 계산량 O(N)으로 셀 수 있으므로 N = 200,000인 경우에도 1초 이내에 답을 구할 수 있습니다.

(7) 응용예시②: 같은 색카드의 조합

다음 문제는 카드 선택 방법의 갯수를 구하는 문제입니다.

문제

N장의 카드가 있으며, 왼쪽부터 i번째(1 ≦ i ≦ N) 카드의 색은 Ai입니다. Ai = 1이면 보라색, Ai = 2이면 주황색, Ai = 3이면 파란색입니다. 같은 색 카드 2장을 선택하는 방법은 몇 가지일까요?

제한 조건: 2 ≦ N ≦ 500,000, 1 ≦ Aᵢ ≦ 3

실행시간 제한: 1초

먼저, 카드 선택방법을 전수조사하는 방법을 떠올릴 수 있습니다. 그러나, 2장의 카드를 선택하므로 전수조사의 경우의 수는

가 되어 비효율적입니다.

따라서, 다른 방법을 생각해 봅시다. 보라색, 주황색, 파란색 카드 갯수를 각각 x, y, z장이라고 하면 다음고 ㅏ같은 사실을 알 수 있습니다.

보라색 카드 2장을 선택하는 방법은 xC2가지

주황색 카드 2장을 선택하는 방법은 yC2가지

파란색 카드 2장을 선택하는 방법은 zC2가지

따라서 구해야 하는 답은

가 됩니다. 이처럼 각 색상별 카드 갯수를 단순히 세기만 하면 되므로, 계산량은 O(N)으로 전수조사에 비해 훨씬 효율적입니다.

(8) 응용예시③: 같은 색 카드의 조합

다음 문제는 카드 선택방법의 갯수를 구하는 문제입니다.

문제

N장의 카드가 있으며, 왼쪽부터 i번째(1 ≦ i ≦ N)카드의 색상은 Ai입니다. Ai=1이면 보라색, Ai=2이면 주황색, Ai=3이면 파란색입니다. 같은 색상의 카드 2장을 선택하는 방법은 몇가지일까요?

제한 조건: 2 ≦ N ≦ 500,000, 1 ≦ Aᵢ ≦ 3

실행시간 제한: 1초

먼저, 카드 선택 방법을 전수조사하는 방법이 떠오를 것입니다. 그러나, 2장의 카드를 선택하므로 전수조사의 경우의 수는

가 되어 비효율적입니다.

따라서, 다른 방법을 생각해 봅시다. 보라색, 주황색, 파란색 카드의 갯수를 각각 x, y, z장이라고 하면 다음과 같은 사실을 알 수 있습니다.

보라색 카드 2장을 선택하는 방법은 xC2가지

주황색 카드 2장을 선택하는 방법은 yC2가지

파란색 카드 2장을 선택하는 방법은 zC2가지

따라서 구해야 하는 답은

가 됩니다. 이처럼 각 색상별 카드 갯수를 단순히 세기만 하면 되므로 계산량은 O(N)으로 전수조사에 비해 훨씬 효율적입니다.

5개 카드를 모두 탐색하는 프로그램

(9) 연습문제

9-1. 2C1, 8C5, 7P2, 10P3의 값을 각각 계산하세요.

9-2. "CAKE ONE"케이크 가게에서는 케이크를 구매할 때 아래 항목들 중에서 각각 하나씩 선택할 수 있습니다. (반대로 이 외의 방법으로 구매할 수는 없습니다)

크기: 소, 중, 대, 특대

토핑: 사과, 바나나, 오렌지, 블루베리, 초콜릿

네임플레이트: 있음, 없음

케이크 1개를 구매하는 방법은 몇 가지인가요?

9-3. 1 ≦ r ≦ n ≦ 20을 만족하는 정수 n, r이 주어집니다. nCr을 출력하는 프로그램을 작성해주세요.

9-4. '응용예시①'에서 소개한 문제를 해결하는 파이썬 프로그램을 작성하세요.

9-5. '응용예시②'에서 소개한 문제를 해결하는 파이썬 프로그램을 작성하세요.

9-6. N장의 카드가 있으며, 왼쪽부터 i번째 카드에는 정수 Ai가 적혀 있습니다. 합이 100,000이 되는 2장의 카드 선택 방법은 몇 가지인지 구하는 프로그램을 작성하세요.

단, 2 ≦ N ≦ 200,000, 1 ≦ Aᵢ ≦ 99,999를 만족하는 케이스에서 1초이내 실행이 끝나야 합니다.

9-7. 다음과 같은 격자모양의 도로가 있습니다. 시작점에서 도착점까지 최단 경로로 이동하는 방법은 몇 가지인가요?

©2024-2025 GAEBAL AI, Hand-crafted & made with Damon JW Kim.

GAEBAL AI 개발사: https://gaebalai.com

LLM/RAG/미세조정 전문개발 - GAEBAL AI

AI 강의 및 개발, 컨설팅 문의: https://talk.naver.com/ct/w5umt5

ZERO AI - 네이버톡톡