493. Under The Rainbow

 

항아리에 일곱 가지 무지개 색의 공이 각각 10개씩, 총 70개의 공이 항아리에 있다.

랜덤하게 20개의 공을 선택할 경우 몇 가지의 색이 있겠는가?

소숫점 9자리까지 답을 구하시오(a.bcdefghij형태).

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

 

처음에는 조합(combination)을 이용해서 나오는 각 경우의 수에 대한 색상 종류를 구해서 전체 평균을 구하는 형태로 접근했는데, 가능한 조합인 70C20의 값이 161,884,603,662,658,000이어서 코딩을 정확하게 한 것은 자신있지만 시간 내에 답을 구하리라는 장담을 할 수 없는 상황이었다.

 

그래서 다른 형태의 접근이 필요한 상황이었는데, 구글의 도움을 받아 해결할 수 있었다. 특정 색이 있지 않을 확률은 70개 중 60개에서 20개의 공을 꺼내는 경우이므로(60C20/70C20), 특정 색이 있을 확률은 정반대가(1-60C20/70C20) 되며, 7개 공 각각에 대해 구하면(7*(1-60C20/70C20)) 된다.

 

이렇게 접근하는 논리를 생각해 내는 것이 쉽지 않은 문제이지, 이 논리를 구현하는 것은 정말 간단하다.

 

 

 

 

 

816. Shortest Distance Among Points

 

이차원 평면에 다음 랜덤 숫자 생성기를 이용하여 좌표의 배열인 Pn을 생성하자:
S0=290797
Sn+1=Sn2 mod 50515093

Pn=(S2n,S2n+1)

 

P0,⋯,Pk-1 중 임의의 (서로 다른) 두 좌표의 최단 거리를 d(k)라고 하면, d(14)=546446.466846479이다.

소숫점 9자리까지 나오도록 반올림하여  d(2000000)을 구하시오.

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

 

번호가 높은 문제여서 해결한 사람이 많지 않지만, 5% 난이도 문제여서 그렇게까지 까다롭지는 않다.

 

초기값과 값을 구하는 공식, 해당 값을 이용한 좌표를 구하는 공식이 있으므로 요구하는 대로 값을 계산하면 된다.

 

다만, 예시를 보고 정확하게 프로그램을 작성하지 않아 한가지 실수가 있었는데, mod함수를 사용해서 연속된 두 좌표의 거리 중 가장 짧은 것을 계산한 것이었다. n개 좌표가 있으면 n-1번 계산했는데, 하필이면 예시가 12번째, 13번째 사이가 최단거리인 경우여서 잘못된 프로그램으로도 예시의 답이 나와서 잘못된 부분을 찾는데 애먹었다.

 

하지만, 곰곰히 생각해 보면, 문제에서는 임의의 두 좌표에 대한 거리를 묻고 있으므로 생성가능한 모든 조합에 대해 거리를 계산해야 되어서 시간이 매우 많이 필요하다. 복잡도가 O(n)에서 O(n2)이 되면서 시간이 기하급수로 늘어나는 문제가 있었다.

 

몇시간이 걸려도 해결되지 않아 코드를 일부 개선해봤지만 시간이 더 걸리는 등 알고리즘에 대한 근본적인 해결책이 필요했다. 관련 내용을 검색해보다 복잡도를 낮출 아이디어를 구했다. 2백만개의 좌표가 mod 함수에 의해 구해져서 들쑥날쑥이어서 모든 좌표 간의 거리를 계산했는데, 원점을 기준으로 정렬하면 앞뒤 좌표간의 거리만 계산해도 해결 가능하게 되어 복잡도가 줄어든다.

 

전체 실행시간을 보면, Pn 좌표를 생성하는데 3.6초, 원점 기준으로 정렬하는데 6초, 좌표 간 거리를 계산하는데 10초가 걸려 20초 만에 답을 구할 수 있었다.

808. Reversible Prime Squares

 

169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.

다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:

  1. 회문(palindrome)이 아니며,
  2. 소수의 제곱이며,
  3. 반대로 한 것도 소수의 제곱이다.

169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.

처음 50개 reversible prime square의 합계를 구하시오.

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

 

프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.

 

50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.

 

100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.

 

문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.

 

일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.

 

그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.

 

추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.

751. Concatenation Coincidence

작아지지 않는 정수의 수열인 an은 다음 과정을 통해 양의 실수 θ에서 만들어 낼 수 있다.

    b1

    bn=└bn-1┘(bn-1-└bn-1┘+1) , n>=2일 때

    an=└bn

└ ┘은 버림을 나타낸다.

예를 들어, θ=2.956938891377988...는 피보나치 수열(2, 3, 5, 8, 13, 21, 34, 55, 89, ...)를 생성한다.

양의 정수의 수열인 an을 연결하면, τ로 표기하는 a1에서 시작해서 소숫점 아래의 연속된 요소를 결합한 a1.a2a3a4...모양의 실수가 된다.

예를 들어, θ=2.956938891377988...에서 나오는 피보나치 순열을 연결하면 τ=2.3581321345589...가 되며, θ 값에 대해 θ와 τ는 다르다.

a1=2에서 시작해서 수열을 결합했을 때 τ=θ가 되는 유일한 값 θ를 찾으시오. 답안은 반올림하여 소숫점 24자리까지 구하시오.

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

 

처음에는 고민을 많이 하고 접근했는데, 생각보다 어렵지 않게 해결 가능했다.

 

처음에는 θ=2로 시작해서, 공식을 소숫점 25자리까지 반복 적용해서 나온 숫자(τ)를 다시 θ로 설정하는 작업을 τ=θ가 나올때까지 반복하면 되는데 몇 번 반복하지 않고 답을 구할 수 있었다.

205. Dice Game

 

피터는 (피라미드 모양) 4면 주사위 9개를 가지고 있고, 각 주사위 면에는 1,2,3,4가 적혀 있다.

콜린은 (정육면체 모양) 6면 주사위 6개를 가지고 있고, 각 주사위 면에는 1,2,3,4,5,6이 적혀 있다.

피터와 콜린이 주사위를 굴려 합계를 비교해서 합계가 큰 사람이 이긴다. 둘의 합계가 같으면 무승부이다.

4면 주사위를 가진 피터가 콜린을 이길 확률은 얼마인가? 정답을 소숫점 7자리까지 반올림으로 나타내어 0.abcdefg 형태로 제시하시오.

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

 

처음에 랜덤 함수를 이용하여 둘의 주사위를 생성하고, 합계를 비교하는 몬테카를로 시뮬레이션 방법을 활용하여 천만번 게임을 운영한 승패를 구했는데 답이 맞지 않았다.

 

그래서 어쩔수 없이 단순하게 전체 경우를 구하는 형태로 접근을 바꿨다. 파이썬 라이브러리의 중복순열(from itertools import production)을 이용하여 피터와 콜린의 경우의 수를 각각 구하고, 그것을 합계로 바꿔 반복문을 통해 두 사람의 모든 경우를 비교하는 형태로 구현했다. 이렇게 설명하면 간단하지만 두 사람의 경우를 곱하면 122억이 넘기 때문에 보기보다 많은 시간이 걸리는 문제였다(몬테카를로 시뮬레이션을 활용하더라도 100억 번은 넘어야 결과에 가까운 답이 나올 수 있다는 뜻으로 이해되었다).

 

다시 생각해보니, 피터는 9~36, 콜린은 6~36의 합계가 나올 수 있지만 경우의 수는 각각 262,144, 46,656이므로 많은 경우 중복되어 나온다. 앞의 방식처름 122억 회 이상 비교하는 것 보다는 각 값에 대한 발생횟수를 가중치 형태로 만들어서 계산하니 2초 내외에 답을 구할 수 있었다.

 

문제를 잘못 이해해서 답을 abcdefg 형태로 구했는데 계속 틀리게 나와 알고리즘을 다시 검토하는 등 시간을 많이 소모했는데, 답은 이미 맞게 구했고 '0.abcdefg' 형태로 답을 쓰면 되는 것이었다.

+ Recent posts