124. Ordered Radicals

 

n의 근인 rad(n)은 서로 다른 소수 n의 곱이다. 예를 들어, 504=23*32*7이고, rad(504)=2*3*7=42이다.

n이 1이상, 10이하일 때 rad(n)을 계산하고, rad(n)을 기준으로 정렬하고, 근 값이 같을 때 n 값에 따라 정렬하면 위의 표와 같다:

E(k)를 정렬된 n의 k번째 요소라고 하자. 예를 들어, E(4)=8이고, E(6)=9이다.

rad(n)이 1이상, 10만 이하의 값으로 정렬되었을 때, E(10000)을 구하시오.

--------------------------------------------------------------------------

 

미리 만들어 둔 약수 함수를 이용해서 결과 중 소수만 찾으면 rad(n) 값을 구할 수 있다.

 

10만개 결과 리스트에 대해 rad(n)값을 1순위, n값을 2순위로 해서 정렬하면 답을 구할 수 있다. 파이썬 리스트의 인덱스가 0부터 시작하는 것 때문에 1만번째 값을 다른 것을 구하는 덕분에 다시 한 번 더 실행해야 되어서 시간이 좀 걸렸다.

 

약수 함수를 아무리 개선해도 성능에 한계가 있어서 문제에서 10만개를 요구했으니 다행이지 다른 문제처럼 몇조 단위의 처리를 요구했으면 시간내에 해결하지 못했을 것 같다.

123. Prime Square Remainders

 

pn을 n번째 소수(2, 3, 5, 7, 11, ..), r을 (pn-1)n+(pn+1)n을 pn2으로 나눴을 때 나머지로 하자.

예를 들어, n이 3일 때, p3=5이고, 43+63=280은 5 mod 25와 합동이다.

나머지가 처음으로 109을 초과할 때 가장 작은 n의 값은 7037이다.

나머지가 처음으로 1010을 초과할 때 가장 작은 값을 구하시오.

--------------------------------------------------------------------------

 

이전 오일러 프로젝트 문제를 통해 소수와 나머지를 다루는 데 익숙해져 있으면 난이도 30%이지만 크게 어렵지 않게 해결 가능한 문제이다.

 

우선 충분한 크기의 소수 목록을 만들어 두고(천만 이하의 소수 목록을 만들어서 해결했는데, 결과론으로 보면 더 작은 목록을 만들어도 해결 가능했다), 각 소수에 대해 문제에서 제시한 공식을 대입해서 나머지 값을 구하면서 1010보다 큰 경우를 찾으면 된다.

 

앞에서 나온 나머지 문제를 해결할 때 중간값이 너무 커져서 에러가 발생한 경우를 봤기 때문에 부분계산을 할 때마다 나머지 연산을 적용해서 큰 수가 만들어지지 않게 하면서 답을 구했는데 생각보다 빠른 시간 내에 답을 구할 수 있었다.

121. Disc Game Prize Fund

 

가방에 붉은 색 원반 1장과 푸른 색 원반 1장이 있다. 게임에서 원반 1장을 랜덤하게 꺼내고 색을 기록한다. 각 회차가 끝나고 나면 원반을 다시 가방에 넣고 붉은 색 원반 1장을 추가한 후, 원반 1장을 랜덤하게 꺼낸다.

참가자는 1파운드를 내고 경기에 참가하고, 게임이 끝났을 때 푸른 색 원반이 붉은 색 원반보다 많은 경우 승리한다.

게임이 4회차로 구성된 경우, 참가자가 승리할 확률은 정확하게 11/120이고, 주최측이 손실을 입지 않으려면 할당해야 하는 최대 상금은 10파운드가 되어야 한다. 모든 상금은 파운드 단위로만 되어야 하고 참가비 1파운드가 포함되므로, 예시에서 참가자가 획득하는 돈은 9파운드가 된다.

게임이 15회차로 구성되는 경우 할당해야 하는 최대 상금을 구하시오.

--------------------------------------------------------------------------

 

확률과 조합을 이용하여 해결하는 문제이다.

 

예시를 조금 설명하면, 참가자가 승리하는 경우는 파란색 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%였지만 적성에 맞는 문제인지 어렵지 않게 해결 가능했다.

119. Digit Power Sum

 

512는 각 자리수의 합을 거듭제곱한 것과 같다는 점에서 재미있는 수이다: 5+1+2=8이고 83=512이다.

이러한 속성을 가진 다른 수는 614656=284이다.

an을 이런 수열의 n번째 숫자라고 정의하고,  an은 두자리 이상의 숫자가 되어야 한다.

a2=512이고 a10=614656임을 알려준다.

a30을 찾으시오.

--------------------------------------------------------------------------

 

처음에는 brute force에 가까운 방법으로 접근했는데, 시간 문제가 생겼다. 즉, 10부터 1씩 키워나가며 자리수의 합을 구하고, 자리수의 합에 대해 거듭제곱을 하면서 원래 숫자가 만들어지는지 확인하는 방법이었는데, 예시로 제공한 10번째 숫자까지는 비교적 빠른 시간 내에 구했지만, 그 이후로는 숫자가 기하급수적으로 커지면서 10분 이상이 지나도 답이 나오지 않는 상황이 되었다.

 

그래서, 다른 사람은 어떤 식으로 접근했는지 찾아봤는데, 파이썬이 큰 수를 다루는 데 유리한 점을 이용하여 해결했다는 것이 있어서 그것을 참조해서 해결했다. for 반복문 2개를 이용해서 일정크기 이내의 밀과 지수에 대한 거듭제곱을 만들어서, 거듭제곱 각 자리수의 합이 밑과 동일한 경우를 구하는 방법이다. 그 이후에는 정렬하고, 30번째 요소를 찾으면 되는 것이다.

 

만약, 찾은 것이 정답이 아니면 밑을 충분히 크게 만들지 않았기 때문에 밑의 반복범위를 키우고, 그래도 안되면 거듭제곱의 반복범위를 키우는 방법으로 접근하면 어렵지 않게 구할 수 있을 것이다. 생각하기에 따라 상당히 위험한 방법의 brute force이지만 파이썬이 큰 숫자를 다루는 데 문제가 없기에 가능한 방법이었던 것 같다.

145. Reversible Numbers

 

어떤 양의 정수 n은 [n+reverse(n)]의 모든 숫자가 홀수로만 이뤄지는 속성이 있다. 예를 들어, 36+63=99이고 409+904=1313이다. 이런 숫자를 가역숫자(reversible number)라 한다. 36과 63, 409와 904는 가역숫자이다. 0으로 시작하는 경우는 n, reverse(n)에 허용되지 않는다.

1천 이하에는 120개의 가역숫자가 있다.

10억(109)이하에는 몇 개의 가역 숫자가 있는가?

--------------------------------------------------------------------------

 

문제에서 0으로 시작하는 경우를 허용하지 않는다고 했으므로, 끝이 0인 숫자는 가역 여부를 확인할 필요가 없다. 프로그램의 구성은 비교적 간단한데, 10억까지 계산을 해야되기 때문에 시간이 많이 소요된다. 이것을 줄일 방법이 있는지 모르겠지만 일단 시도해 봤다.

 

10억까지 반복하면서, 각 숫자의 순서를 바꾸고 더해서, 모든 자릿수가 홀수인지 확인하면 된다. 10이하의 숫자는 무조건 짝수가 되기 때문에 고려하지 않았다. 1억까지 구하는데 10분 넘는 시간이 걸렸고, 숫자가 커지면서 조금씩 시간이 늘어나 10억까지는 100분 넘게 걸려 답을 구할 수 있었다.

 

가만히 생각해 보니, 10이하 숫자를 고려하지 않았던 것처럼, 9자리 숫자도 n+reverse(n)을 하면 모두 홀수가 되지 않는다. 가운데인 5번째 숫자는 같은 숫자를 2번 더하기 때문에 무조건 짝수가 되고, 그것을 막으려면 6번째 숫자가 10이 넘어야 한다. 그러면 4번째 숫자도 10이 넘어서, 7번째 숫자가 홀수이면 3번째 숫자도 홀수인 경우 4번째 숫자에서 1이 넘어오기 때문에 (3번째와 7번째) 둘 중 하나는 짝수가 될 수 밖에 없다. 그러다보니, 전체 연산시간의 90% 이상을 차지하는 1억 이상의 숫자 모두가 가역숫자가 되지 못하는데 계산하느라 시간을 낭비한 꼴이 되어버렸다.

 

다음 수식에서 x, y, n은 양의 정수이다.

1/x+1/y=1/n

n이 4일 때, 다음의 3개 답안만 있다:

1/5+1/20=1/4

1/6+1/12=1/4

1/8+1/8=1/4

서로 다른 해결책이 1,000개를 넘는 가장 작은 값 n은 얼마인가?

주의: 이 문제는 문제 110의 쉬운 버전이므로, 이 문제를 먼저 해결하기를 강력하게 권고함

--------------------------------------------------------------------------

 

다른 분이 이야기한 아이디어(양변에 nxy를 곱해서 분모 없애기)를 참고해서 해결할 수 있었다.

문제에 나오는 공식의 분모를 없애기 위해 간단히 수학을 적용해서 양변에 xyn을 곱하면 ny+nx=xy가 된다. 그리고, 예시를 보면 짐작 가능하겠지만 n이 x, y보다는 작기 때문에 x를 n+a, y를 n+b로 바꾸면 n(n+b)+n(n+a)=(n+a)(n+b)가 된다. 이를 풀면 n2+nb+n2+na=n2+na+nb+ab가 되고 양변을 정리하면 n2=ab가 된다.

 

이 특성을 이해하고, 예시를 다시 보면 x의 값이 n=4일 때, n보다 1, 2, 4만큼 큰 것을 알 수 있다. 이것이 4의 약수이기 때문에, 솔루션이 1000개를 넘는 것은 약수가 1000개를 넘는 경우와 같은 것으로 이해되었다. 그래서, 먼저 풀었던 243번 문제에서 적용한 소수의 곱을 대상으로 배수로 키워나가면서 약수가 1000개 이상인 경우를 찾는 방법을 적용했는데, 예상과는 달리 오답이었다.

 

n2=ab를 다시 생각해보니, n의 약수가 아니라 n2의 약수 중 n이하의 값인 것들을 찾으면 되는 것이었다. 예시로 나온 4가 너무 작은 수이면서 2의 배수여서 다양한 경우가 나오지 않아 잘못된 유추를 하게 되었던 것이다.

 

약수를 구하는 함수를 n제곱을 입력값으로 해서 n이하의 값만 구하도록 바꾸고 나니 빠른 시간 내에 답을 구할 수 있었다.

120. Square Remainders

 

r을 (a-1)n+(a+1)n을 a2으로 나누었을 때 나머지로 하자.

예를 들어, a=7이고 n=3일 때, r=42가 된다(63+83=728≡42 mod 49). 그리고 n 값이 바뀌면 r도 바뀌게 된다. 하지만, a=7일 때 r의 최대값인 rmax=42이다.

3≤a≤1000일 때, rmax의 합계(∑rmax)를 구하시오.

--------------------------------------------------------------------------

 

어렵지 않아 보이지만 실행 시간이 많이 소요되는 문제이다. 나누는 수가 a2이기 때문에 나머지를 확인하기 위해 검증하는 범위를 a2번까지 설정해야 했기 때문이다.

 

그리고, 나머지 함수의 특성을 살려서 적용해야지 문제에서 제시한 그대로 코딩했을 때에는 숫자가 기하급수적으로 커지면서 실행시간이 매우 많이 필요하게 되었다.

 

나머지 함수의 곱셈 특징((a*b)%c=(a%c)*(b%c))을 활용하여, 거듭제곱의 경우 분산해서 계산하도록 코드를 개선했다. 즉, a7=a*a2*a4, a9=a*a8과 같은 형태로 나누고, 각각에 나머지 함수를 적용해서 숫자가 최대한 커지지 않도록 만들었다.

 

그렇게 개선했어도 실행시간은 많이 필요했으며(100까지 7초, 200까지 58초, 300까지 173초, 400까지 360초, 500까지 628초, 600까지 942초, 700까지 1365초, 800까지 1777초, 900까지 2415초, 1000까지 3043초로 총 3시간 필요), 이 방식보다는 좀 더 빠른 형태의 수학에 기반한 해법이 있을 것 같다.

112. Bouncy Numbers

 

예를 들어 134468과 같이, 숫자를 왼쪽에서 오른쪽으로 읽을 때 각 자릿수가 이전 자릿수보다 작지 않으면 증가수라고 한다.

비슷하게, 예를 들어 66420과 같이 각 자릿수가 이전 자릿수보다 크지 않으면 감소수라고 한다.

예를 들어, 155349와 같이 증가하지도 감소하지도 않는 숫자를 bouncy number라고 한다.

명백하게, 100 미만으로는 bouncy number가 있을 수 없다. 1000 미만으로는 절반이 넘는 525개 숫자가 bouncy number이다. 실제로, bouncy number의 비중이 처음으로 50%가 되는 숫자는 538이다.

놀랍게도, bouncy number는 점차 많아져서 21780이 되면 bouncy number의 비중이 90%가 된다.

bouncy number가 정확히 99%가 되는 가장 작은 숫자를 찾으시오.

--------------------------------------------------------------------------

 

한 자리 숫자는 증가, 감소, bouncy가 있을 수 없으므로 10부터 시작해서 솟자를 계속 키워나가면서 증가수, 감소수, bouncy number를 판별하게 구성하면 된다.

 

구성할 때 한 가지 고려할 것은 이전 숫자와 값이 같으면 아직 증가수인지 감소수인지 판별을 유보해야 한다는 것이다. 처음에 이 부분을 잘못 생각하고 유보할 때 증가수, 감소수 플래그를 무조건 True로 값을 넣도록 프로그램을 만들었는데, 3자리에서는 유효하지만 4자리 숫자에서 오류를 만들게 되어 있어서 판별할 숫자를 50%만 제시했으면 이유를 찾지 못할뻔 했다. (값이 같을 때 이전에 증가수/감소수로 판별된 경우 이전 판별을 유지해야 되는데 잘 못 생각해서 계속 유보하게 만든 것이 문제였다)

 

조건문만 잘 구성하면, 반복문을 통해 까다롭지 않게 구할 수 있다.

 

102. Triangle Containment

 

−1000≤x,y≤1000인 좌표평면 위에 임의의 점을 3개 찍으면 삼각형을 만들 수 있다.

다음 두 삼각형을 생각해 보자:

A(−340,495), B(−153,−910), C(835,−947)

X(−175,41), Y(−421,−714), Z(574,−645)

삼각형 ABC에는 원점이 포함되지만, 삼각형 XYZ에는 원점이 포함되지 않는다.

 

27K 크기의 triangles.txt (우클릭하고 다른 이름으로 저장)에는 1,000개의 임의의 삼각형 좌표가 있다. 원점이 삼각형 안에 엤는 경우는 몇 개인가?

--------------------------------------------------------------------------

 

해결할 아이디어가 떠오르지 않아 찾아보니 고1 정도의 수학 지식을 필요로하는 문제였다. 벡터를 이용, 삼각형 면적 이용, 도형(삼각형)과 교차하는 점의 갯수, 무게중심좌표 등 해결하는 방법은 몇 가지가 있는데 개념은 알겠는데 실제 어떤 형태로 구현할 것인지는 쉽지 않았다.

 

이 중 무게중심좌표(Barycentric Coordinate System)를 이용한 해법으로 답을 구했다. 삼각형 세 꼭지점의 좌표를 (x1,y1), (x2, y2), (x3, y3)라 하고, 원점을(xp, yp)라 할 때, 다음과 같이 세 좌표를 계산해서 모두 0보다 크면 삼각형 내부에 있다고 한다.

alpha=((y2-y3)*(xp-x3)+(x3-x2)*(yp-y3)) / ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3))

beta=((y3-y1)*(xp-x3)+(x1-x3)*(yp-y3)) / ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3))

gamma=1.0-alpha-beta

왜 그렇게 되는지는 이해 못했지만 위 내용대로 구현하니 답을 구할 수 있었다.

 

그리고, 왜 이렇게 난이도가 올라갈까 싶었는데, 게임을 할 때 특정 좌표가 도형 내에 있는지 밖에 있는지 판단하는 방법으로 이 코드를 사용할 수 있다고 한다. 좌표가 보호막 내에 있는지 판단하거나, 게임 내의 비행체와 총알의 충돌을 판단하는 등에 사용할 것을 생각하면 이해가 필요한 것 같다.

프로젝트 오일러의 문제를 100번까지 모두 해결하는 것을 목표로 진행했는데, 몇 문제는 아이디어가 잘 떠오르지 않아 아직 해결하지 못했다. (특히 68번은 문제 자체를 이해할 수 없어 어떤 식으로 접근해야 할 지 오리무중이다) 이제는 난이도를 중심으로 해결되는 대로 포스팅할 예정이다.

 

100번대 이후 문제를 풀어보니, 난이도 5%도 문제대로 하면 코딩은 간단하지만 말도 안되는 수준으로 실행시간이 많이 필요하게 되어, 수학지식을 바탕으로 최적화하기를 요구하고 있는 등 적절한 방법으로 해결하는 것이 쉽지 않았다. 이제는 진짜 파이썬 공부인지 수학 공부인지 알 수 없어지는 상황이 되었지만, 그래도 최대한 해결해 볼 예정이다.

 

 

 

 

In the game, Monopoly, the standard board is set up in the following way:

A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.

In addition to G2J, and one card from each of CC and CH, that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.

At the beginning of the game, the CC and CH cards are shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.

  • Community Chest (2/16 cards):
    1. Advance to GO
    2. Go to JAIL
  • Chance (10/16 cards):
    1. Advance to GO
    2. Go to JAIL
    3. Go to C1
    4. Go to E3
    5. Go to H2
    6. Go to R1
    7. Go to next R (railway company)
    8. Go to next R
    9. Go to next U (utility company)
    10. Go back 3 squares.

The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing on it is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes at on each roll that we are interested in. We shall make no distinction between "Just Visiting" and being sent to JAIL, and we shall also ignore the rule about requiring a double to "get out of jail", assuming that they pay to get out on their next turn.

By starting at GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.

Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.

If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.

 

표준 보드 게임인 '모노폴리'는 위 그림과 같이 구성된다.

플레이어는 GO에서 시작하고, 육면체 주사위 2개를 굴려 나온 값만큼 시계방향으로 진행한다. 추가 규칙이 없으면 각 자리를 방문할 확률은 2.5%로 동일하다. 그러나, G2J(감옥으로 가시오), CC(보물상자), CH(기회)를 방문하면 확률은 바뀐다.

G2J를 방문하거나, CC, CH에 있는 한 장의 카드를 뽑으면 플레이어는 감옥으로 가야한다. 플레이어가 같은 숫자를 3번 연속으로 굴리지 못하면, 3번째 굴린 결과까지는 진행하지 못하고, 감옥으로 곧장 가게 된다.

게임을 시작할 때, CC, CH카드는 섞어 둔다. 플레이어가 CC, CH에 도착하면 각 파일 가장 위에 있는 카드를 뽑아, 지시사항을 따르고, 뽑은 카드는 가장 파일 가장 아래에 둔다. 각 파일에는 16개 카드가 있지만, 이번 문제의 목적을 위해 이동을 명령하는 카드만 고려하고, 이동과 관련없는 카드는 무시되고 플레이어는 CC/CH 자리에 남아있게 된다.

  • 보물 상자 (2/16 카드):
    1. GO로 이동하시오
    2. 감옥(JAIL)으로 가시오
  • 기회 (10/16 카드):
    1. GO로 이동하시오
    2. 감옥(JAIL)으로 가시오
    3. C1로 가시오
    4. E3으로 가시오
    5. H2로 가시오
    6. R1로 가시오
    7. 다음 R(열차 회사)로 가시오
    8. 다음 R로 가시오
    9. 다음 U(전력(utility) 회사)로 가시오
    10. 3칸 뒤로 가시오

이번 문제의 핵심은 특정 자리를 방문하게 될 것을 고려하는 것이다. 즉, 주사위를 굴린 후 특정 자리를 끝낼 확률을 말한다. 이런 이유로 끝낼 확률이 0인 G2J를 제외하고, CH는 5/8이 다른 자리로 이동하게 하므로 가장 낮은 확률을 가지고, 플레이어가 각 롤을 끝낼 때 우리가 관삼가지는 마지막 자리이다. 우리는 감옥의 단순 방문과 감옥으로 보내는 것에 차이를 두지 않을 것이고, 다음 순서에 나오기 위해 지불할 것이라 가정하고 "감옥에서 나오기 위한" 같은 숫자를 요구하는 규칙 또한 무시할 것이다.

GO에서 시작해서 각 자리에 번호를 00에서 39까지 매기면, 대응하는 자리 집합을 2자리 문자열을 결합하여 만들수 있다.

통계적으로, 가장 인기 있는 자리 3개를 순서대로 보면, 10번 자리인 감옥(6.24%), 24번 자리인 E3(3.18%), 0번 자리인 GO(3.09%)이다. 이 셋은 가장 인기있는 자리이고 6자리 숫자로 표현하면 102400이다.

육면체 대신 사면체 주사위를 굴릴 경우 (가장 인기있는 3자리를 결합한) 6자리 숫자를 구하시오.

--------------------------------------------------------------------------

 

부루마불이라 부르는 모노폴리를 단순화하여 문제를 만든 것인데, 문제에서 요구한 조건을 정리하면 다음과 같다.

 

주사위 결과에 따라 이동하는데, 같은 숫자가 3번 나오면 감옥으로 이동, 보물상자(CC)와 기회(CH)에서는 뽑은 카드 결과에 따라 이동, G2J에 가면 감옥으로 이동한다. 그 외 모노폴리에 있는 부동산 구매 등은 생략하고 이동 중심으로만 했으며, 감옥을 빠져나오는 조건도 따로 두지 않았다.

 

가장 많이 방문하는 3곳을 구하라는 것인데, 어떻게 할 것인지 고민하다가 주사위 2개를 랜덤하게 굴리는 형태로 많은 횟수를 실제 게임을 해서 방문하는 장소를 카운트하는 형태로 구하기로 했다. 나중에 찾아보니 이것을 몬테 카를로 방법이라 부른다고 한다.

 

여기까지 정리되고 나니 구현하는 것은 그렇게 어렵지 않았다. 다만, 기본값 설정 등에 있어 명확하게 하지 않은 부분에서 잘못 동작되어 처음에는 오답이 나왔었다.

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 1012 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

 

파란색 디스크 15장, 빨간색 디스크 6장으로 구성된 21장의 디스크가 있는 박스에서, 디스크 2장을 랜덤하게 선택하는 경우 2장의 파란색 디스크를 선택할 확률은 P(BB)=(15/21)x(14/20)=1/2이다.

동일한 구성으로 2장의 파란색 디스크를 랜덤하게 선택할 확률이 50%인 경우는 85장의 파란색 디스크와 35장의 붉은색 디스크로 구성된 경우이다.

 

총 1012 = 1,000,000,000,000장 이상 디스크가 있을 때 동일한 구성으로 2장의 파란색 디스크를 랜덤하게 선택할 확률이 50%가 되는 경우는, 파란색 디스크가 몇 장 있을 때인가?

--------------------------------------------------------------------------

 

(중학생 이하 수준이지만) 갈수록 수학문제가 되고 있는 상황인데, 근의 공식을 이용하여 해결하기로 결정했다. 이전에 √를 바로 사용하면서 소숫점이 이하 자리 숫자가 있음에도 값이 너무 작아 정수로 판정되는 오류를 겪었기 때문에, 큰 수이지만 일단 제곱수인 상태에서 적용해 보기로 했다.

 

확률이 1/2일 때 총 디스크 수를 c, 파란색 디스크 수를 x라고 하면, P(BB)=(x/c)*((x-1)/(c-1))=1/2이며, 이것을 전개하면 2x2-2x=c(c-1), 2x2-2x-c(c-1)=0이 된다. 여기에 근의 공식을 적용하면 x=(2+(4+4*2*c(c-1))**0.5)/2*2가 되고, 루트 기호 부분 기준으로 정리하면 (4+8c(c-1))**0.5=4x-2이 되고, 양쪽을 제곱하여 루트를 없애면 1+2c(c-1)=(2x-1)2가 된다. 수학 기호를 html로 표기하는 방법이 익숙하지 않아 가독성이 나쁘게 적었지만 이와 같은 형태로 방정식을 구할 수 있다.

 

여기에서 c는 1조에서 시작하고, x는 좌변의 값보다 조금 작은 값이 나올 값에서 시작해서 양 변이 같을 때까지 c와 x값을 계속 키우면서 찾는 작업을 했다. 양변을 크게 보면 8*c^2와 16*x^2가 있어서 x의 시작값을 1부터 하지 않고 c/√2부터 시작해서 추적했다. 실행이 생각보다 오래 걸려서 상황을 보니 이 방법으로는 답을 구할 수 없을 것 같았다.

 

먼저 방법으로는 해결되지 않아 인터넷을 검색해 보니, 연분수와 비슷하게 x, c의 이전값을 통해 새 값을 찾을 수 있다고 되어 있었다. 문제에서는 (x, c) 값이 (15, 21), (85, 120)인 경우가 있었는데, (3, 4)인 경우에도 확률이 파란색 2개가 연속으로 나올 확률은 1/2가 된다.

 

이 (x,c)값 3쌍을 이용하여 x, c값의 다음 항에 대한 일차방정식을 유추해봤고(xn=3x+2c-2, cn=4x+3c-3), 그 공식으로 만든 숫자로 다음 값인 (493, 697) 또한 파란색 2개가 나올 확률이 1/2임을 확인해서 해당 공식을 통해 빠른 시간 내에 답을 구할 수 있었다.

 

일차방정식을 빨리 유추하기 위해 엑셀을 사용했는데, 엑셀로는 12자리 이상 숫자를 확인할 수 없다는 것 또한 알게 되었다.

 

Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

 

지수로 표현된 두 수 211과 37을 비교하는 것은 어렵지 않다. 계산기를 이용하면 211 = 2048 < 37 = 2187을 확인할 수 있다.

그러나, 3백만 자릿수 이상이 되는 두 수가 632382518061 > 519432525806 인 것을 확인하는 것은 상당히 어렵다.

1천 개 이상의 밑과 지수 쌍이 각 행에 있는 22K 크기의 텍스트 파일 base_exp.txt (오른쪽 클릭하고 다른 이름으로 링크 저장) 중 가장 큰 값을 가지는 숫자를 찾으시오.

주의: 파일의 첫 두 줄은 위의 예시에 있는 숫자이다.

--------------------------------------------------------------------------

 

정직하게 프로그래밍 했더니 역시나 OverflowError: math range error라는 에러메시지를 보게 되었다. 급격하게 커지는 지수를 따라가지 않고 계산할 방법은 이제는 까맣게 잊어버린 log를 다시 찾아보는 방법밖에 없어 보인다.

 

로그의 지수법칙(logab=bloga)을 이용하여 동일한 밑인 상황에서 base_exp 파일의 밑과 지수를 로그에 대입하면(문제의 예시에서 518061*log632382와 525806*log519432를 비교하는 형태) 어렵지 않게 해결 가능하다.

 

 

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 362. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = 962. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

 

단어 CARE의 각 글자를 각각 1, 2, 9, 6으로 바꾸면 1296 = 362의 제곱수가 된다. 여기서 주목할만한 점은, 동일한 디지털 교체 방법인 애너그램(anagram, 철자 순서 바꾸기)을 적용한 RACE 또한 9216 = 962로 제곱수가 된다. CARE(와 RACE)는 제곱 애너그램 쌍이라 부르는데, 단어는 0으로 시작하지 않고 서로 다른 글자는 같은 디지털 값을 가지지 않도록 한다.

약 2천개 일반 영어 단어가 있는 16K 텍스트 파일인 words.txt (우클릭하고 다른 이름으로 저장)을 이용하여 모든 제곱 애너그램 쌍을 찾으시오 (회문 형태는 자신의 애너그램이 아니다).

이 쌍에서 구할 수 있는 가장 큰 제곱수는 무엇인가?

주의: 모든 애너그램은 제시된 텍스트 파일에서 구해야 한다.

--------------------------------------------------------------------------

 

문제를 해결할 때마다 드는 생각이지만, 요즘 언어 특성에 맞는 간결하면서도 빠른 접근방법이 있을 것 같은 느낌은 들지만 정확하게 모르기 때문에 정공법이라 할 수 있는 시간이 걸려도 단계별로 구현해 나가는 형태로 해결하고 있는 것 같다.

 

이 문제를 해결하려면, 일단 파일을 읽어 단어 리스트를 만들고, 그 중 애너그램이 될 수 있는 단어를 찾고, 단어 길이만큼의 제곱수 목록을 만들어서, 애너그램 후보 단어 그룹과 제곱수 목록이 매치되는 최대값을 찾는 4가지 과정이 필요했다.

 

파일을 읽어 단어 리스트를 만드는 것은 프로젝트 오일러 문제를 풀면서 몇 번 해봤기 때문에 기존에 작성한 것을 활용해서 따옴표만 처리해주면 되었다.

 

애너그램이 될 수 있는 단어를 찾기 위해, 각 단어를 알파벳 순으로 정렬했을 때 같은 값을 가지는 단어를 묶어 리스트를 만들었다.

 

제곱수 목록을 만들기 위해, 애너그램이 될 수 있는 단어들의 길이를 측정해서 최소 길이부터 최대 길이 사이에 있는 제곱수 목록을 만들었다. 조금 편하게 쓸 수 있을 것 같아 제곱수 목록을 단어 길이별로 만들었다.

 

애너그램 후보 단어 그룹과 제곱수 목록을 매치시키는 것을 구현하는 부분이 제일 어려웠는데, 실제 구현한 코드도 처음 생각한 모든 기능을 반영한 것은 아니지만 일단 정답을 맞췄기에 넘어가기로 했다. 문제의 예시로 설명하면, 4자리 제곱수의 1296, 애너그램 대상이 되는 CARE, RACE를 읽어서 애너그램 숫자 9216을 만들고 그것이 4자리 제곱수 목록에 있는지, 각 단어그룹을 해당 자리 제곱수 목록만큼 2중 반복문을 통해 찾도록 했는데 간단히 구현한 만큼 문제가 있었다.

 

SHEET, THESE의 경우 E의 자리 값이 같아야 되고, 그 값이 THESE로 되었을 때 같은 자리에 있어야 한다. SHEET의 숫자가 12334이면, THESE는 42313이 되어야 되는데 가지고 있는 실력으로는 그렇게까지 정교하게 만들어 낼 수가 없었다. 그래서 고민끝에 아이디어를 낸 것이 두 숫자의 종류가 같고, 같은 숫자 최대값이 애너그램의 같은 문자 최대값과 같은 경우로 조건을 추가했는데 답을 구할 수 있었다.

 

문제에서 요구한 기능을 모두 구현한 것은 아니지만 답은 구할 수 있어서 아쉽지만 기뻤다. 코드가 깔끔해지 못하지만 실행시간이 짧은 것은 의외였다.

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.

Find the last ten digits of this prime number.

 

1백만 자릿수가 넘는 소수 중 처음으로 알려진 소수가 1999년에 발견되었다. 이것은 26972593−1 형태인 메르센 소수(Mersenne prime)이다. 이 숫자는 2,098,960 자리로 구성된다. 마르센 소수 이후, 자릿수가 더 많은 2p−1 형태의 메르센 소수가 발견되고 있다.

그러나, 2004년에 2,357,207 자릿수인 큰 규모의 비 메르센 소수 28433×27830457+1이 발견되었다.

이 소수의 마지막 열 자릿수를 구하시오.

--------------------------------------------------------------------------

 

메르센 소수(Mersenne prime)라는 새로운 형태의 소수를 소개하고 그것을 응용하는 문제이다. 프로그래밍을 효율적으로 또는 어렵게 하는 데 수학이 필요하다는 것은 인정하지만, 갈수록 프로그래밍 보다는 수학을 공부하고 있는 것 같다.

 

파이썬의 정수 최대값 허용폭이 넓은 것을 믿고 정직하게 한 줄로 작성했더니 최대값을 넘어 동작하지 않는다는 에러가 나왔다.

 

문제에서 마지막 10자리 숫자를 물어봤고, 이것은 모든 숫자를 계산할 필요없이 마지막 10자리 숫자만 계산하면 되는 것이었다. 그래서 % 연산자를 이용해 계속 10자리만 남게 하면서 2를 계속 곱해 27830457을 구하고, 거기에 28433곱하고 1을 더해서 나온 숫자의 마지막 10자리만 뽑아내면 되므로 문제를 해결하는 것은 그리 까다롭지 않았다.

 

 

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

 

소수 3, 7, 109, 673은 주목할 만하다. 두 소수를 선택해서 연결하면 소수가 된다. 예를 들면, 7, 109를 연결한 7109와 1097은 모두 소수이다. 네 소수의 합인 792는 이런 속성을 가진 네 소수의 합 중 가장 작은 값이다.

임의의 두 소수를 연결해도 소수가 되는 다섯 소수의 합계 중 가장 작은 값을 구하시오.

--------------------------------------------------------------------------

 

값을 찾을 소수의 최대값을 정해야 하는데, 예시를 보고 일단 1만 이하의 소수를 대상으로 찾아보기로 했다.

 

단순대입법보다 좋은 방법이 생각나지 않아서, 크기가 커지는 5개의 소수를 대상으로 반복문을 구성해서 이 중 2개씩 연결한 것 모두 소수인 것을 찾도록 구성했다. 5개 숫자를 a, b, c, d, e라고 할 때 2번째 반복문에서 ab, ba가 소수이고, 3번째 반복문에서 ac, ca, bc, cb가 소수이고, 4번째 반복문에서 ad, da, bd, db, cd, dc가 소수이며, 5번째 반복문에서 ae, ea, be, eb, ce, ec, de, ed의 20가지 모두 소수가 되는 경우를 찾게 했다.

 

소수 리스트가 1200개가 넘게 있으니 5중 반복문이면 최악의 경우 12005를 계산해야 되는 구조여서 예상했던 것 보다 시간이 많이 필요했다. 제일 처음 나오는 값이 합계가 가장 작은 경우라는 보장이 없기 때문에 모든 경우를 계산해서 답을 찾아야 하지만, 가장 먼저 나온 경우를 입력했을 때 정답으로 처리되어 다행히 조금 더 빨리 답을 구할 수 있었다.

 

상황을 분석해보니 연결한 숫자의 소수여부를 판별하는 데 시간이 많이 걸리는 것을 발견하고, 초기에 소수 목록을 연결된 숫자까지 만들고 난 이후에 그 값으로 판별하게 하니 실행 시간이 몇시간에서 몇분으로 개선되었다. 그리고, 계속 오답을 찾아 이상했는데 리스트의 값과 인덱스를 잘 구분하지 못하고 사용한 문제 때문에 발생한 것이었다.

 

1만 이하 소수에서 답이 되는 경우가 하나 이상 있을 수 있어 5중 반복문을 전부 돌려 답을 찾게 했는데, 실제로는 답이 되는 경우가 하나 밖에 없었다.

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using p059_cipher.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

 

컴퓨터의 각 글자에는 유일한 코드가 할당되어 있으며, 선호되는 표준은 ASCII(American Standard Code for Information Interchange)이다. 예를 들어, 대문자A=65, 별표(*)=42, 소문자k=107이다.

근대 암호화 기법은 텍스트 파일을 가져와서, 바이트를 ASCII로 변환하고, 각 바이트를 비밀키에서 가져온 값으로 XOR 계산하는 것이다. XOR 함수의 장점은 암호화 된 텍스트에 같은 키를 적용하면 평문(원래 텍스트)을  복원할 수 있다는 것이다. 예를 들어 65 XOR 42 = 107이고, 107 XOR 42 = 65이다.

깰 수 없는 암호화를 위하여 키는 평문과 같은 길이이고, 키는 랜덤한 바이트로 만들어진다. 사용자가 암호화 된 메시지를 가지고 있지만 암호화 키를 다른 곳에 보관하면, 둘 모두가 있지 않으면 복호화할 수 없다(암호를 해독할 수 없다).

불행하게도, 이 방법은 대부분 사용자에게 실용적이지 못하기 때문에, 수정된 방법이 패스워드를 키로 사용하는 것이다. 패스워드가 메시지보다 짧으면, 키는 전체 메시지에 반복되면서 적용된다. 이 방법을 위한 균형은 패스워드가 보안을 유지하기에 충분히 길면서 기억할 수 있을만큼 짧은 것이다.

당신의 과제는 암호화 키를 3자리의 소문자로 구성하는 것으로 단순화되었다. 암호화 된 ASCII 코드를 가지고 있는 p059_cipher.txt (우클릭하고 '다른 이름으로 링크 저장') 파일을 복호화하여 일반 영어 단어로 구성된 평문을 구하고 원문에 있는 ASCII 값의 합계를 구하시오.

--------------------------------------------------------------------------

 

포커 게임을 설계해보는 57번 문제에 이어 실제 상황에 필요할만한 프로그램을 만들어보는 문제이다. 이 문제도 간단해 보여 덤볐다가 생각보다 까다로워 나중에 풀어보기로 했던 것이다.

파일에 있는 숫자를 이진수로 변환하고 XOR 계산을 하려고 했는데, 계속 에러가 나서 이해하기 어려운 상황이 되었다. 이유를 찾다 보니 파이썬의 bin 함수로 변환한 이진수는 문자열로 처리가 되고, 파이썬의 경우 십진수를 대상으로 XOR 연산을 해도 이진수에 대한 XOR과 같은 결과가 나온다는 것이었다. 간단하게 진행할 수 있는 것을 멀리 돌아가고 있었다.

 

XOR을 적용한 내용이 영어 평문인지 확인하는 방법을 고민했는데, 처음에는 결과의 아스키코드 값이 숫자와 알파벳에만 있는 것으로 했는데 나오지 않아서, 영어 평문에 나올 수 없는 기호인 경우를 제외하는 형태로 했더니 3자리 글자 후보로 하나씩만 나왔다.

 

그 값을 이용해서 XOR을 적용하고 나온 아스키 코드 값을 더해서 답을 구할 수 있었다. 참고로, 그 결과를 파이썬 chr 함수를 이용해서 원문 형태로 바꾸니 말이 되지 않는 문장이 나온다. 찾아낸 복호화 코드가 맞는지 의심은 들었지만 결과값이 맞기에 넘어가기로 했다.

 

(유튜브로 해법을 올리는 영상을 확인하니 일반 영어문장이 나오는 것을 보면 키를 잘 못 찾았는데, XOR을 적용한 결과는 같아 정답을 맞춘 것으로 나온 것 같다. 괜히 복호화한 문장을 확인했다가 찝찝함을 남기게 되었다. 그리고, 유튜브에서는 내가 접근한 나올 수 없는 기호를 제외하는 방법이 아니라 복호화했을 때 가장 흔한 영어단어인 'the', 'and'가 있는지 확인하는 형태로 키를 찾고 있었다.)

 

 

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

  • High Card: Highest value card.
  • One Pair: Two cards of the same value.
  • Two Pairs: Two different pairs.
  • Three of a Kind: Three cards of the same value.
  • Straight: All cards are consecutive values.
  • Flush: All cards of the same suit.
  • Full House: Three of a kind and a pair.
  • Four of a Kind: Four cards of the same value.
  • Straight Flush: All cards are consecutive values of same suit.
  • Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following five hands dealt to two players:

Hand   Player 1   Player 2   Winner
1   5H 5C 6S 7S KD
Pair of Fives
  2C 3S 8S 8D TD
Pair of Eights
  Player 2
2   5D 8C 9S JS AC
Highest card Ace
  2C 5C 7D 8S QH
Highest card Queen
  Player 1
3   2D 9C AS AH AC
Three Aces
  3D 6D 7D TD QD
Flush with Diamonds
  Player 2
4   4D 6S 9H QH QC
Pair of Queens
Highest card Nine
  3D 6D 7H QD QS
Pair of Queens
Highest card Seven
  Player 1
5   2H 2D 4C 4D 4S
Full House
With Three Fours
  3C 3D 3S 9S 9D
Full House
with Three Threes
  Player 1

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

 

포커에서는 카드 5장을 다음 순서로 등급을 매긴다.

  • 하이 카드: 가장 높은 값의 카드
  • 원 페어: 2장의 카드가 같은 값
  • 투 페어: 2개 서로 다른 페어
  • 트리플: 카드 3장이 같은 값
  • 스트레이트: 모든 카드가 연속된 숫자
  • 플러쉬: 모든 카드가 같은 무늬
  • 풀 하우스: 트리플과 원 페어
  • 포카드: 카드 4장이 같은 값
  • 스트레이트 플러쉬: 연속된 숫자이며 같은 무늬
  • 로얄 플러쉬: 10, J, Q, K, A가 같은 무늬

카드의 순서는 다음과 같다.
2, 3, 4, 5, 6, 7, 8, 9, 10, J(잭), Q(퀸), K(킹), A(에이스)

두 플레이어의 등급이 같으면 가장 높은 카드로 구성된 플레이어가 이긴다. 예를 들어, 8 페어는 5 페어를 이긴다(아래의 예시1을 참조). 그러나, 두 등급이 동일한 경우 가장 높은 카드를 비교한다(아래의 예시4 참조). 가장 높은 카드도 동일한 경우에는 다음 높은 카드를 비교하는 식으로 계속 한다.

두 플레이어 간 다음 다섯 게임을 보면:

게임   플레이어 1   플레이어 2   승자
1   5H 5C 6S 7S KD
5 페어
  2C 3S 8S 8D TD
8 페어
  플레이어 2
2   5D 8C 9S JS AC
가장 높은 카드 A
  2C 5C 7D 8S QH
가장 높은 카드 Q
  플레이어 1
3   2D 9C AS AH AC
A 트리플
  3D 6D 7D TD QD
다이아몬드 플러쉬
  플레이어 2
4   4D 6S 9H QH QC
Q 페어
가장 높은 카드 9
  3D 6D 7H QD QS
Q 페어
가장 높은 카드 7
  플레이어 1
5   2H 2D 4C 4D 4S
풀 하우스
4가 3장
  3C 3D 3S 9S 9D
풀 하우스
3이 3장
  플레이어 1

poker.txt 파일에는 1천 개의 랜덤한 두 플레이어 간 게임이 있다. 파일의 각 중에는 스페이스로 구분된 10장의 카드가 있으며, 이 중 처음 5장은 플레이어 1의 카드이고, 다음 5장은 플레이어 2의 카드이다. 모든 카드는 유효하고, 각 플레이어의 카드에는 특정 순서가 없고, 각 게임에는 분명하게 승자가 있다고 가정하자.

 

플레이어 1은 몇 번 이겼는가?

--------------------------------------------------------------------------

 

포커 게임을 실제로 만들어 보는 문제인데, 문제를 해결하는 것은 어렵지 않았는데 포커 룰을 모두 프로그래밍하는 것에 시간이 많이 필요할 것 같아 천천히 풀어봤다. 어려운 문제들을 많이 풀었기 때문에 조건문이 많이 들어가고, 동점상황 때문에 길게 프로그램을 만들어야 했지만 쉬는 기분으로 해결할 수 있었다.

 

파일을 읽어 각 게임을 문자열 하나로 만들고, 플레이어1,2의 각 숫자 갯수와 무늬를 판별해서 등급을 매기고, 그것을 기준으로 누가 이기는지 결정하면 된다.

 

숫자 갯수와 무늬를 판별하고 등급을 매기는 것이 반복되어 함수로 만들었고, 숫자 갯수는 리스트의 각 숫자 위치에 몇장 있는지 기록을 하고, 무늬는 4장 모두 같은 무늬인지만 판별하게 했다. 등급은 특정 숫자가 4개면 포카드, 3개,2개이면 풀하우스, 3개면 트리플, 2개가 2개면 투페어, 5개면 원페어이고, 연속된 숫자가 있는데 숫자가 같은 무늬이며 10,J,Q,K,A면 로얄플러쉬, 무늬만 같으면 스트레이트 플러쉬, 무늬가 다르면 스트레이트, 숫자와 관계없이 무늬가 같으면 플러쉬로 판정하면 된다. 복잡하게 썼지만 조건문으로 만들기에는 까다롭지 않았다.

 

그런데, 동점 상황일 때 높은 카드를 가진 사람이 이기는 것을 적용하기 위해 추가로 작성한 부분이 전체 코드보다 더 길게 나오는 것을 보면, 예외처리 상황이 많아 논리가 복잡하게 나왔던 것 같다. 문제에서 요구하지 않은 예외상황까지 생각하면서 너무 복잡하게 구현한 것 갈은 느낌도 들었다.

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

 

숫자의 진약수는 자신을 제외한 약수이다. 예를 들어, 28의 진약수는 1, 2, 4, 7, 14이다. 진약수의 합계가 28이므로, 완벽수라 부른다. 흥미롭게도 220의 진약수의 합은 284이고, 284의 진약수의 합은 220이어서 두 숫자간에 체인을 만든다. 이런 이유로, 220과 284는 친화쌍(우애쌍, 친구쌍, amicable pair)이라 부른다.

더 긴 체인은 잘 알려져 있지 않다. 예를 들어, 12496으로 시작하면 5개 숫자의 체인을 만든다.

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

이 체인은 시작 지점으로 돌아오기 때문에, 친화 체인(amicable chain)이라 부른다.

요소가 1백만을 넘지 않는 가장 긴 친화 체인의 가장 작은 수를 구하시오.

--------------------------------------------------------------------------

 

친화쌍(amicable pair) 등 일부 명칭은 한글로 찾을 수 없어서 친화수(amicable number)와 연계해서 친화쌍, 친화 체인으로 임의로 번역을 했다.

 

파이썬을 이용해 진약수 구하기, 진약수의 합 구하기, 체인 만들기 등은 이제 어렵지 않는 부분인데, 테스트로 몇 개 숫자를 대상으로 실행해보니 몇 가지 추가로 고려해야 할 것이 있었다. 모든 수가 체인을 만든다고 생각을 하고 다른 예외상황을 생각하지 않았는데, 고려할 사항을 예로 들면 소수가 되면 다음 숫자는 1이 되면서 무한 반복하고, 6이 되어도 6을 무한반복하고, 562로 시작하면 중간에 220과 284를 반복하고 있었다.

 

이렇게 하고도, 1백만까지 반복하려 하니 시간이 너무 많이 걸리는 문제가 있어, 이미 체인으로 파악한 경우에는 다시 진약수를 구하고 체인을 만드는 과정을 반복하지 않도록 하고, 약수가 1밖에 없는 소수는 더 이상 계산하지 않도록 하는 등 속도를 빠르게 조정했지만, 수 시간 걸릴 것으로 예상되는 등 속도가 문제가 되는 상황이었다.

 

하지만, 검증을 위해 나온 중간결과값이 정답이 되어 버려서 느린 성능에도 불구하고 정답을 맞힐 수는 있었다. 다른 사람의 방법을 확인하니 역시나 소인수분해를 응용해서 해결하는 것이 정석인 것 같다.

 

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

 

변의 길이가 정수이고 정수 크기의 면적을 가지는 정삼각형이 없다는 것은 증명하기 쉽다. 그러나, 거의 정삼각형인 5-5-6의 면적은 12로 정수가 된다.

두 변이 같고 다른 변과 길이 차이가 1 이하인 삼각형을 "거의 정삼각형"으로 정의하고자 한다.

변의 길이와 면적이 정수이고 둘라가 10억을 이하인 모든 "거의 정삼각형"의 둘래의 합계를 구하시오.

--------------------------------------------------------------------------

 

"거의 정삼각형"을 다시 생각해보면 2개의 직각삼각형이 붙어 있는 구조이며, 직각삼각형의 빗변(가장 긴 변)이 "거의 정삼각형"에서 길이가 같은 변이 된다. 그리고 길이가 같은 변을 a, 나머지 변을 b라 하면, 문제에서 정의한 내용에 따라 b=a±1이 되고, "거의 정삼각형" 안에 있는 직각삼각형은 빗변이 a, 다른 변은 피타고라스 정리에 의해 각각 b/2=(a±1)/2, (a**2-(b/2)**2)**0.5가 된다.

 

문제에서 둘레와 면적이 모두 정수가 된다고 했으므로 b, b/2, (a**2-(b/2)**2)**0.5 모두 정수가 되어야 하며 a*2+b는 10억 이하가 되어야 한다. 그리고, b/2가 정수가 되기 위해서는 a는 홀수가 된다.

 

이런 전제조건에 따라 a가 커지면서 b, b/2, (a**2-(b/2)**2)**0.5가 정수이고, 둘레가 10억 이하인 "거의 정삼각형"을 계속 구했는데, 정상적으로 나와야 할 갯수보다 6개가 더 나와서 둘레의 합이 훨씬 크게 나오는 문제가 생겼다.

 

원인을 파악해 보니 (a**2-(b/2)**2)**0.5 값을 int(a**2-(b/2)**2)**0.5)와 비교해서 같으면 정수로 판별했는데, 제곱수와 차이가 매우 미세하면 제곱수가 아닌데도 두 값이 같게 나오는 문제 때문에 답을 6개나 더 구한 것으로 추정되었다.

 

is_integer() 등 몇 가지 방법을 적용했지만 해결되지 않아서, 제곱근을 씌운 상태에서 계산하지 않고 제곱인 상태에서 값을 비교해서 제곱수 여부를 판별하게 했더니 정답을 구할 수 있었다. 이전 문제에서 비슷한 경험이 있어 빨리 해결 가능했지, 로직의 문제가 아닌 프로그램 고유 특성에서 생기는 이런 현상은 찾기가 쉽지 않은 것 같다.

 

 

+ Recent posts