반응형

 안녕하세요. 이번에도 예약글을 써야 겠어요. 파이썬으로 코테를 준비하시는 경우가 많은 걸로 들었어요. 보통 코테에서는, 전수 탐색과 구현을 버무린 이런 문제들이 종종 출제가 되곤 해요. 잘 읽어보면 아시겠지만, 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번 연산을 수행할 수 있다는 것입니다. 벽과 맵을 벗어나지 말아야 한다는 조건을 무시한다면요.

 

 

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

 

반응형

댓글을 달아 주세요