python itertools에 있는 product permutations combinations 함수를 알아봅시다.

 안녕하세요. 이번에도 예약글을 써야 겠어요. 파이썬으로 코테를 준비하시는 경우가 많은 걸로 들었어요. 보통 코테에서는, 전수 탐색과 구현을 버무린 이런 문제들이 종종 출제가 되곤 해요. 잘 읽어보면 아시겠지만, 8문제 세트 중에 2번째 문제로 출제하였습니다. 앞쪽에 배치하였다는 이야기는 풀어야 한다는 의미와도 일맥상통합니다. 그러한 문제들을 풀 때 product, permutations, combinations 함수를 알아두면 좋을 듯 해서 간단하게 소개해 보도록 하겠습니다.

 

 

---

 먼저 product 함수입니다. iterable한 것에 대해서 카타시안 곱을 생성합니다. 이렇게만 들으면 뭔가 어려운 거 같습니다. 결과부터 보겠습니다.

 

 

 어떤 식으로 생성되는지 눈치를 채셨을 텐데요. repeat를 2로 주었어요. 그랬더니 i와 j가 정수이면서, [1, 4]에 속하는 모든 쌍 (i, j)를 생성했음을 알 수 있어요. repeat가 3이면 어떨까요?

 

 

 코드로는 요래 됩니다. 1번째 인자로 range(1, 5)를 받았고, repeat값이 3입니다. 그러면 i, j, k가 정수이면서, [1, 4]에 속하는 모든 쌍 (i, j, k)를 생성할 겁니다. 결과를 보겠습니다.

 

 

 정말 그랬음을 알 수 있어요.

 

 

 이제 permutation 함수를 봅시다. 1번째 인자로 range(1, 5)를 넣었습니다. 이는 아이템이 4개 있다는 의미입니다. 이 중에서 2개를 뽑을 건데, 순서도 고려할 거에요. 그러면 가짓수가 어떻게 될까요? 4!/2! = 12가지가 나올 겁니다. 결과를 보겠습니다.

 

 

 결과를 보면, 1번과 2번을 뽑은 데이터가 (1, 2), (2, 1) 이렇게 2개가 나왔음을 볼 수 있어요.

 

 

 이제 combinations를 봅시다. 이것은 n개 중 r개를 뽑는 것이에요. 1을 뽑고 2를 뽑는 것과 2를 뽑고 1을 뽑는 것을 같은 경우로 취급합니다. 실행 결과를 보면 알 수 있습니다.

 

 

 중요한 것은 (2, 1, 3)은 결과에 없다는 것인데요. 이미 (1, 2, 3)과 같은 경우로 취급이 되기 때문입니다.

 

 

---

 제가 낸 문제 중에 이 문제는 가희가 최대 T번 움직일 수 있어요. 그리고, 처음에 가희가 북쪽을 선택했다면, 그 다음에도 북쪽을 선택할 수 있어요. 벽으로 가면 안 되고, 맵 안에서만 이동해야 한다는 제약을 무시해 봅시다. 그리고, 북쪽으로 이동하는 것을 0, 동쪽으로 이동하는 것을 1, 남쪽으로 가는 것을 2, 서쪽으로 가는 것을 3이라고 해 봅시다. T가 3이라고 한다면, 가희가 3초동안 움직일 수 있는 경우의 수를 모두 출력하기 위해서 아래와 같은 코드를 작성하면 됩니다.

 

 

 여기서 핵심은 가희가 1번 연산을 수행한 후에, 또 다시 1번 연산을 수행할 수 있다는 것입니다. 벽과 맵을 벗어나지 말아야 한다는 조건을 무시한다면요.

 

 

 이제 각각의 경우에 대해서 가희를 이동시켜 보면서, 먹은 고구마 갯수를 세면 됩니다. 만약에 중간에 벽을 만나거나, 맵을 벗어난다면, 그 경우는 무시하면 됩니다.