세군데 병원에 방문하는 모든 방법의 수 알고리즘 - 팩토리얼(Factorial)

알고리즘 문제를 풀다가 팩토리얼(Factorial)문제가 나와서 정리 해봅니다. 팩토리얼은 중학교때인가 고등학교때인가 배웠습니다. 이것이 무엇인지 우리는 알고 있습니다.

 

하지만 저는 단순히 외워서 알고 있었던 것 같습니다. N팩토리얼이면 N! 이고 N * (N - 1) ... * 2 * 1 이렇게 곱하는 것이라는 것은 알고 있습니다. 하지만 이 패토리얼 연산을 언제 써야 하는지에 대해서는 그 예제가 '학생 4명을 한줄로 세우는 방법의 수'와 같이 학생이라면 떠올리겠지만 학생이 아니고 '문자열 N개를 배열하는 경우의 수'라던지 '카드 N개를 배열하는 경우'라던지 조금만 바뀌면 제가 떠올리지 못하는 것을 보고 다시 정리를 해 보았습니다.

 

제가 풀었던 문제는 아래 문제 입니다.

 

문제

프로젝트가 끝나고 모처럼 휴일이 왔습니다. 몸이 아픈데가 많아서 병원을 세군데를 들리려고 합니다. 세군데 병원은 내과, 치과, 안과 입니다. 세군데 병원을 들리는 모든 경우의 수는 몇가지 인지 출력 해보세요. ex) 내과 치과 안과 내과 안과 치과 치과 내과 안과 ...생략...

어떤 병원을 어떤 순서로 갈 것인지는 내가 정할 수 있습니다. 그래서 첫번째, 두번째, 세번째에 내과, 치과, 안과를 다 갈 수 있습니다. 

 

그러면 전체 경우의 수는 몇가지가 나올까요?

1번째	2번째	3번째
내과	내과	내과
치과	치과	치과
안과	안과	안과

 

위와 같이 각 번째에 3가지 병원을 갈 수 있으니 3 * 3 * 3 = 27가지 일까요? 아닙니다.

1번째	2번째	3번째
내과	내과	내과

위와 같이 첫번째, 두번째, 세번째 모두 ‘내과’를 가는 경우는 없습니다. 처방전을 안받아 왔거나 우산을 놓고 온 경우 다시 방문할 수는 있겠지만 한번 갔던 병원을 또 가지는 않을 것입니다.

 

1번째	2번째	3번째
내과

위와 같이 첫번째로 내과를 방문하기로 했다면 2번째에 방문할 병원은 치과, 안과 둘중에 하나 입니다. 왜냐하면 이미 내과는 다녀왔기 때문입니다.

 

1번째	2번째	3번째
내과	치과
내과	안과

첫번째에 내과를 선택 했다면 나올 수 있는 경우가 위에 두가지 경우 뿐입니다.

 

1번째	2번째	3번째
내과	치과	안과
내과	안과	치과

첫번째로 내과를 방문했다면 치과, 안과 순으로 가거나 안과, 치과 순으로 가는 경우의 수만 있습니다.

 

위 경우의 수가 첫번째로 내과를 선택한 경우입니다. 하지만 첫번째로 갈 수 있는 병원은 내과, 치과, 안과 3가지 이므로 위에 2가지 경우가 총 3번 반복됩니다.

1번째	2번째	3번째
내과	치과	안과
내과	안과	치과
치과	내과	안과
치과	안과	내과
안과	치과	내과
안과	내과	치과

그래서 3 * 3 * 3 = 27이 아닌 3 * 2 * 1 = 6이 됩니다.

 

만약 산부인과 병원 한군데가 더 추가 되어서 총 4개의 병원을 방문하는 경우의 수를 구해야 한다면 총 몇가지 경우의 수가 나올까요?

1번째	2번째	3번째	4번째
산부인과	내과	치과

산부인과, 내과, 치과를 이미 방문을 했다고 하면 4번째에는 안과 한군데 밖에 남지 않습니다.

 

역시나 첫번째로 방문할 병원은 산부인과, 내과, 치과, 안과 4가지 중에 한군데 입니다.

1번째	2번째	3번째	4번째
산부인과
내과
치과
안과

그래서 나올 수 있는 모든 경우의 수는 4 * 3 * 2 * 1 = 24가 됩니다.

 

이 연산은 팩토리얼(Factorial)연산이 되겠습니다. 팩토리얼 연산은 N * (N-1) * … 2 * 1로 N부터 1까지 한개씩 빼면서 곱하는 연산입니다.

 

방문해야 할 병원이 3군데라면 3!이고 4군데라면 4!입니다.