python itertools product 함수는 카타시안 곱을 생성해 주는 함수입니다. 이 함수를 익혀 보고, 제가 출제한 문제를 같이 풀어보도록 하겠습니다.
product 함수 설명
이 함수는 2개의 인자를 받습니다.
- iterables
- input이 됩니다. 집합 S라고 생각하시면 되겠습니다.
- repeat
이 repeat가 이해하기 다소 힘든데요. 수학적으로 풀어보면, 아래와 같습니다. repeat가 r이라면 아래와 같은 튜플들의 집합 R을 뽑게 됩니다.
R = {(a1, … , ar) | a1 ∈ S, … , ar ∈ S}
예를 들어, 아래와 같은 코드가 있다고 해 볼게요.
보면, iterables가 range(0, 4)로 되어 있어요. 집합 S가 {0, 1, 2, 3}입니다. 다음, repeat가 2인데요. 이 r 값이 2이기 때문에 아래와 같은 튜플들의 집합 R이 뽑힙니다.
R = {(a1, a2) | a1 ∈ S, a2 ∈ S}
그렇다면 가능한 쌍은 (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3)이 됩니다. 총 16가지가 나오는 셈입니다. 튜플의 1번째 원소도 S에 속하고, 2번째 원소도 S에 속하는 셈입니다. 이 프로그램의 결과를 볼까요?
결과는 위와 같습니다.
permutations 함수와의 차이
그러면 이 python itertools product 함수는 permutation 함수와 어떤 차이를 가지고 있을까요? 먼저, product는 각 원소가 집합 S에 속하는, 크기가 r인 튜플들을 모두 뽑아내요. 예를 들어, S가 {1, 2}이고 repeat가 3이라고 해 보겠습니다. 그러면 튜플의 크기 r은 3입니다.
뽑을 수 있는 집합은 어떻게 되나요? 1과 2 이렇게 2개입니다. 튜플에 들어가는 원소 수는 3개니까, 이 3개가 1 또는 2가 되게 만들어 봅시다.
(1, 1, 1)을 만들 수 있습니다. 그리고 (1, 1, 2)도 만들 수 있어요. 왜? 1과 2가 집합 S에 포함되기 때문입니다. 하지만, (1, 2, 3)은 만들지 못합니다. 3이 S에 포함되지 않기 때문이에요. 총 23개의 서로 다른 튜플이 뽑히겠어요. 즉, product는 크기가 r이고, 각 원소가 집합 S (iterable) 에 속한 튜플을 뽑습니다.
이제, 집합 S가 {0, 1, 2, 3}이라고 해 보겠습니다. repeat를 2로 줘 보겠습니다. 이 경우, 튜플의 크기가 2이고, 튜플의 각 원소는 집합 S에 속한 원소를 뽑으면 됩니다. 고로 (2, 1)이 될 수도 있고, (1, 1)이 될 수도 있습니다. 왜? 1과 2는 S에 속하기 때문이에요.
그런데, permutation은 집합에서 카드를 r개 뽑습니다. r개를 뽑는다는 것이 중요합니다. 비복원 추출입니다.
고로, 2 다음에 1을 뽑는 건 가능합니다.
그런데 1 다음에 1을 뽑는 것은 불가능 합니다. 같은 카드를 2번 뽑았기 때문입니다. 이미 뽑은 것은 제외하는 추가 제약이 들어가는 셈입니다. 이 차이가 이해가 가신다면, 왜 제가 21776번 문제를 풀었을 때, product가 아닌 permutation을 썼는지 이해하실 수 있을 겁니다. 이에 대한 보충 설명은 아래 링크에서 대신하겠습니다.
실전 문제 풀어보기
이제, 제가 출제한 가희와 고구마 먹방 문제를 풀어보도록 하겠습니다. 어렵지 않고, n과 m 시리즈를 조금 응용한 문제이니 간단히 설명하겠습니다. 문제를 보면 아래와 같은 말이 있습니다.
가희는 1초마다 상하좌우 방향 중 한 방향으로 이동하거나
이동하지 않고 그 자리에서 머무를 수 있습니다.
게임 규칙 중
이건 어느 쪽에 가까운가요? T가 2초일 때를 생각해 봅시다. 가희가 2초동안 취한 액션을 tuple로 가지고 있다고 하죠. 그러면 1초일 때에도, 2초일 때에도 상하좌우로 가거나 멈춰 있어야 합니다. 대충 이런 상황인가요?
결국 product, 곱 집합의 상황과 같습니다. 또한 가만히 있는 것도 추가됩니다. 매 초마다 행동할 수 있는 상황이 모두 같습니다. 고로, product를 쓰기 적합합니다. 그런데, 사실 가만히 있는 것이 이득이 아닙니다. 고구마를 많이 먹어야 하는 입장에서는, 1초 버리는 것이기 때문입니다. 고로, 가만히 있는다는 조건은 함정인 셈입니다.
이 부분까지 파악했다면, itertools의 product나 그와 유사한 탐색을 돌리면 됨을 알 수 있습니다.
보면, product의 1번째 인자로 집합 {0, 1, 2, 3}이 들어갔음을 볼 수 있어요. 이는 상, 하, 좌, 우로 이동하는 연산을 의미합니다. T초동안 이 넷 중 하나를 할 수 있으므로, repeat에 T를 넣으면 됩니다.