처음에는 조합(combination)을 이용해서 나오는 각 경우의 수에 대한 색상 종류를 구해서 전체 평균을 구하는 형태로 접근했는데, 가능한 조합인 70C20의 값이 161,884,603,662,658,000이어서 코딩을 정확하게 한 것은 자신있지만 시간 내에 답을 구하리라는 장담을 할 수 없는 상황이었다.
그래서 다른 형태의 접근이 필요한 상황이었는데, 구글의 도움을 받아 해결할 수 있었다. 특정 색이 있지 않을 확률은 70개 중 60개에서 20개의 공을 꺼내는 경우이므로(60C20/70C20), 특정 색이 있을 확률은 정반대가(1-60C20/70C20) 되며, 7개 공 각각에 대해 구하면(7*(1-60C20/70C20)) 된다.
이렇게 접근하는 논리를 생각해 내는 것이 쉽지 않은 문제이지, 이 논리를 구현하는 것은 정말 간단하다.
가방에 붉은 색 원반 1장과 푸른 색 원반 1장이 있다. 게임에서 원반 1장을 랜덤하게 꺼내고 색을 기록한다. 각 회차가 끝나고 나면 원반을 다시 가방에 넣고 붉은 색 원반 1장을 추가한 후, 원반 1장을 랜덤하게 꺼낸다.
참가자는 1파운드를 내고 경기에 참가하고, 게임이 끝났을 때 푸른 색 원반이 붉은 색 원반보다 많은 경우 승리한다.
게임이 4회차로 구성된 경우, 참가자가 승리할 확률은 정확하게 11/120이고, 주최측이 손실을 입지 않으려면 할당해야 하는 최대 상금은 10파운드가 되어야 한다. 모든 상금은 파운드 단위로만 되어야 하고 참가비 1파운드가 포함되므로, 예시에서 참가자가 획득하는 돈은 9파운드가 된다.
예시를 조금 설명하면, 참가자가 승리하는 경우는 파란색 4장을 꺼낸 경우와 3장을 꺼낸 경우이다. 그러면 전체 가능한 경우 120(2*3*4*5) 중 파란색 4장을 꺼낸 경우는 1회이며(1/2*1/3*1/4*1/5), 3장을 꺼낸 경우는 10회(처음 나올 경우 1회, 2번째 2회, 3번째 3회, 4번째 4회)가 된다.
15회차 게임에서 승리할 경우는 전체 경우 20,922,789,888,000(2*3*4*5*6*7*8*9*10*11*12*13*14*15*16) 중 파란색을 8장 이상 꺼낸 경우를 계산하면 된다. 위 예시 설명에서 나오듯이 파란색을 꺼내는 경우는 1, 붉은색을 꺼내는 경우는 '해당 차수 원반 전체-1'이 된다.
붉은 색인 경우를 대상으로 계산을 하면 되므로, 붉은 색이 0장에서 7장인 경우를 계산하는 반복문을 만들고, 각 반복에서 가능한 조합을 생성해서 조합의 갯수를 합하는 형태로 구성하였다. 참고로, 붉은색 공이 2개인 경우 2개를 곱하는 방식을 통해 조합의 전체 갯수를 구하고, 조합의 갯수를 합해야 한다.
그리고, 참가자가 우승할 조합 갯수에 상금을 곱해서 전체 경우보다 작으면서 가장 큰 상금을 구하면 된다.
조합이나 확률을 잘 이해하면 좀 더 짧은 코드로 구현 가능했을 것 같은데, 기초만 이해하는 상황에서는 이 구성이 최선이었고 빠른 시간 내에 답을 구할 수 있었다. 난이도는 35%였지만 적성에 맞는 문제인지 어렵지 않게 해결 가능했다.
By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.
Note that concatenations of the digits, like 12 + 34, are not allowed.
Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.
Find the set of four distinct digits,a<b<c<d, for which the longest set of consecutive positive integers, 1 ton, can be obtained, giving your answer as a string:abcd.
{1, 2, 3, 4}의 각 숫자를 한 번씩 사용하고, 4개 연산자(+, -, *, /)와 괄호를 사용하여, 서로 다른 정수를 구할 수 있다.
몇가지 고민할 사항이 있어 나중에 해결했는데, 인터넷에서 누군가가 알려준 eval() 함수를 활용하면서 많은 부담을 덜 수 있었다.
연산자는 +,-,*,/의 4가지를 사용하는데, 예시에 있는 것처럼 연산자의 우선순위와 관계없이 계산하기 위하여 괄호를 이용해 인위적으로 순서를 지정할 필요가 있다. 연산자가 들어갈 곳은 3자리이므로 괄호를 통해 순서를 강제하는 것은 연산자의 순서를 1,2,3이라 할 때 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)의 6가지 경우가 있는데 이 중 (3,1,2)는 괄호를 통해서도 만들어낼 수 없는 경우이기 때문에 5가지 연산을 하게 만들면 된다.
4가지 숫자를 점차 커지는 순서로 만들고, 생성된 숫자 4개를 순열을 통해 다양한 순서를 만들고, 각 순서에 4가지 연산자 조합에 대해 5가지 연산을 해서, 결과가 양의 정수일 때 결과에 더하고, 모은 결과를 집합, 정렬을 통해 순서대로 배열해서 1부터 가장 긴 연속된 숫자가 있는 4가지 숫자 조합을 찾으면 된다.
위 경우 중 4가지 숫자를 커지는 순서로 만드는 데 반복문 4회, 순열 생성에 반복문 1회, 연산자를 3자리에 배열하는 데 반복문 3회를 해서 들여쓰기를 많이 하는 구조가 되었다.
그리고, 0으로 나누는 경우가 발생할 수 있으므로 exception을 사용하여 예외처리했는데, 개발툴인 Visual Studio Code가 익숙하지 않아서 exception을 무시하도록 설정하지 않아 처음에는 계속 F5를 눌러야 했다. 나중에 보니 Raised Exceptions을 Breakpoints로 설정하지 않도록 하는 옵션이 있어 결과를 빨리 볼 수 있었다.
Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.
For example, the square number 64 could be formed:
In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.
For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.
However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.
In determining a distinct arrangement we are interested in the digits on each cube, not the order.
{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5} {1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}
But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.
How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?
두 개의 육면체의 각 면에 0~9 사이의 글자가 있는 경우, 두 육면체를 나란히 두면 다양한 2자리 숫자를 만들 수 있다.
예를 들어, 제곱수인 64는 아래와 같이 만들어진다:
실제로, 두 육면체의 숫자를 잘 정하면 100 이하의 모든 제곱수를(01, 04, 09, 16, 25, 36, 49, 64, 81) 표시할 수 있다.
예를 들어, 한 육면체에 {0, 5, 6, 7, 8, 9}, 다른 육면체에 {1, 2, 3, 4, 8, 9}가 있으면 모든 제곱수를 표시하는 한 방법이 된다.
그러나, {0, 5, 6, 7, 8, 9}와 {1, 2, 3, 4, 6, 7}가 9개 제곱수를 모두 표현하기 위해서는 6, 9는 아래위가 뒤집힌 경우를 허용해야 한다. 그렇지 않으면 09를 만들 수 없다. 유일한 배열을 결정하기 위해 각 육면체의 배열은 중요하지만 순서는 아니다.
{1, 2, 3, 4, 5, 6}과 {3, 6, 4, 1, 2, 5}은 동일하다. {1, 2, 3, 4, 5, 6}과 {1, 2, 3, 4, 5, 9}은 서로 다르다.
그러나, 6과 9가 뒤집어지는 것을 허용했으므로, 마지막 예시 두 가지 모두 2자리 수를 만들기 위한 확장된 집합인 {1, 2, 3, 4, 5, 6, 9}를 나타내고 있다.
문제 지문이 긴데, 두 수를 조합해서 제곱수(01, 04, 09, 16, 25, 36, 49, 64, 81)을 만들어낼 수 있는 주사위 번호 조합이 몇가지 만들 수 있는지에 대한 질문이다. 처음에 하나는 10의 자리, 다른 하나는 1의 자리를 두는 조합을 생각했는데, 문제에서 요구하는 것은 주사위가 특정 자리에 고정되지 않고 제곱수를 만들어 낼 수 있는 조합을 요구하기 때문에 조금 더 고민을 해야 되었다.
순서가 다르더라도 동일하다고 했으므로 10개의 숫자(0~9)에서 6개 숫자를 뽑는 조합으로 리스트를 만들고, 두 조합 리스트(주사위 2개)에서 제곱수가 만들어지는 경우를 확인할 수 있도록 했다. 10C6에 해당하는 조합 크기가 210이어서 생각보다 크지 않고, 이 문제를 해결하기 위한 새로운 알고리즘이 있을 것 같지는 않아서 반복문 2개를 이용하는 전수조사(라고 좋게 표현했지만 brute force) 방식으로 해결하기로 했다.
6, 9를 동일한 경우로 판정하는 것은 어렵지 않았는데 오답으로 판정되어 문제의 원인을 찾느라 여러가지 방법을 적용해보느라 해결하는데 시간이 많이 걸다. 실제 문제가 된 것은 두 주사위를 독립사건으로 보고 210x210의 전수 대상으로 조사했지만 이 경우 문제에서 예시로 제시한 {0,5,6,7,8,9}, {1,2,3,4,8,9}와 {1,2,3,4,8,9}, {0,5,6,7,8,9}를 두 번 계산하기 때문에 결과값이 크게 나오고 있었고, 이 부분이 중복되지 않도록 조정하고 나서 정답을 구할 수 있었다.
문제 요구조건을 잘못 이해해서 시간이 많이 걸렸어도 복잡한 알고리즘을 요구하는 문제는 아니었는데, 나중에 확인해보니 처음으로 해결한 40% 난이도의 문제였다.
By replacing the 1stdigit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rdand 4thdigits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
2자리 숫자 *3의 첫번째 자릿수를 바꾸면 가능한 9개의 값 중 6개인 13, 23, 43, 53, 73, 83이 소수이다.
56**3의 3번째, 4번째 자릿수를 같은 숫자로 바꾸면, 가능한 10개의 값 중 5개(56003, 56113, 56333, 56443, 56663, 56773, 56993)가 소수가 되는 최초의 숫자이다. 따라서, 56003은 이러한 속성을 가지는 숫자 중 가장 작은 소수이다.
같은 자리의 숫자 일부를 바꿔(인접한 숫자일 필요 없음) 8개의 소수를 만드는 가장 작은 소수는 무엇인가?
문제를 보고 가장 난감했던 부분은 대상 숫자의 자릿수가 없고, 몇 개의 숫자를 바꿀 것인지 없으며, 어느 자리를 바꿀 것인지에 대한 힌트도 없는데 8개의 소수를 만들어내는 숫자를 찾으라는 것이었다. 짝수는 소수가 아니므로 8개를 만들기 위해서는 1의 자리 숫자를 바꾸지 않는 것은 확실한데 다른 숫자는 엄두가 나지 않았다.
몇 번의 반복문을 통해 해결했는데, 전체 자릿수를 두고, 바꾸면서 들어갈 숫자가 몇자리인지 정하고, 고정되게 들어갈 숫자를 반복하게 하고, 조합(combinations)을 이용해 바꾸면서 숫자가 들어갈 자리를 반복하고, 각 자리에 0~9를 대입하여 그 중 소수가 몇 개인지 찾도록 하였다.
반복되는 부분이 많고, 반복문이 독립적이지 않고 앞의 반복문에 연동되고(6자리 숫자인데 바꾸면서 들어갈 숫자가 2자리이면 고정되게 들어갈 숫자는 4자리), 파이썬의 특징을 살리지 못하는 전통적인 방식으로 코딩을 하다 보니 생각보다 코딩은 복잡했는데 답은 구할 수 있었다.
앞의 반복문에 연동되는 범위 계산을 잘못해서 오답을 구한 덕분에, 프로그램을 구성하는 시간만큼 수정하는 시간이 필요했다.
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
2x2 격자의 왼쪽 위에서 출발하고, 오른쪽과 아래쪽으로만 이동할 수 있으면, 오른쪽 아래로 이동하는 데에는 정확히 6개의 경로만 있다. 20x20 격자에는 몇 개의 경로가 있는가? --------------------------------------------------------------------------
격자를 만들고, 이동하는 형태로 반복문을 작성하면 해결 가능할 것 같았는데, 이상하게도 반복문이 만들어지지 않으면서 혼자 논리가 꼬이는 일이 계속되어 답을 구하는 데 많은 시간이 걸렸다. 그래도 아직 답을 구하는 규칙을 찾지 못한 26번에 비하면 빨리 답을 구한 편이긴 하다.
15번이면 비교적 앞쪽의 문제인데 해결방안을 못찾아 애먹으면서 답답했지만, 한 번 논리가 꼬여버린 논리를 푸는 것은 어려운 일이라는 것을 다시 한 번 느꼈고, 좋은 논리로 해결하지 못하고 단순하게 해결할 수 밖에 없어 답답했던 문제이다.
divide and conquer라는 분할정복 방법으로 접근할 수 밖에 없었고, 1x1에서는 2개, 2x2에서는 6개, 3x3에서는 20개로 늘어나는 과정을 쪼개어서(3x3 경로를 1x1, 2x2의 경로를 이용해 구하기) 이전 과정의 합계를 활용하는 규칙을 찾아 그것을 프로그램으로 해결하였다.
이제 생각해보니 전체 2n개의 경로에 n개의 한 방향을 입력하면 되는 것이어서 조합을 이용하면 간단히 답을 구할 수 있는 것이었다.
