책 이야기

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

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

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:

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 참조). 가장 높은 카드도 동일한 경우에는 다음 높은 카드를 비교하는 식으로 계속 한다.

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

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