Programming (77)


프로젝트 오일러 54번

  • 2013/09/21
  • Perl

포커라는 카드게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너뛰셔도 좋습니다)

카드 한 장은 아래와 같은 순서대로 값이 높아집니다.

2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A

다섯 장으로 이루어진 패의 계급(세칭 “족보”)은, 낮은 것부터 높은 순서로 아래와 같습니다.

  • High Card : 가장 높은 카드의 값으로 비교.
  • One Pair : 한 쌍이 같은 카드.
  • Two Pairs : 서로 다른 두 쌍이 같은 카드.
  • Three of a Kind : 세 장이 같은 카드.
  • Straight : 모든 카드가 연속된 숫자.
  • Flush : 모든 카드의 무늬가 같음.
  • Full House : 세 장이 같고, 또 한 쌍이 같음 (Three of a Kind + One Pair).
  • Four of a Kind : 네 장이 같은 카드.
  • Straight Flush : 모든 카드가 연속된 숫자이면서 무늬도 같음.
  • Royal Flush : 10, J, Q, K, A가 무늬도 같음.

두 사람의 패가 같은 종류의 계급이라면, 계급을 구성하는 카드 중 높은 쪽을 쥔 사람이 이깁니다. 예를 들면 8 원페어는 5 원페어를 이깁니다.
계급을 이루는 카드 숫자까지 같으면 (예: 둘 다 Q 원페어), 다른 카드를 높은 순서대로 비교해서 승부를 정합니다.

텍스트파일 poker.txt 에는 두 선수가 벌인 1,000회의 승부가 저장되어 있습니다. (우클릭해서 다운로드 받으세요)
한 줄에는 10장의 카드가 공백으로 분리되어 들어있는데, 앞의 다섯 장은 1번 선수 것이고 뒤의 다섯 장은 2번 선수의 패입니다. 잘못되거나 중복된 데이터는 없으며, 무승부도 없습니다.

카드 숫자는 2, 3, … , 9, T, J, Q, K, A 로 (숫자 10은 T로 표시),
무늬는 C (Club – ♣), D (Diamond – ♦), H (Heart – ♥), S (Spade – ♠) 로 표시되어 있습니다.
예를 들면 3C 3D 3S 9S 9D 의 경우 3 풀하우스가 됩니다.

이 데이터를 분석하고, 1번 선수가 이긴 횟수를 구하세요.

참 문제가 길다.

포커 규칙에 따라서 핸드에 있는 패의 점수를 부여하고, 두 사람의 핸드를 비교해서 이긴사람을 구하는 방식으로 문제를 해결 할 수 있을 것이다.
물론 점수를 부여하는 함수를 만드는 부분이 매우 귀찮은(…) 부분이 될 것 같았다.

프로젝트 오일러 시작에서 설명했던 것과 같이, 나는 함수 구현보다 문제를 푼다는 것에 집중하기로 했으므로, 모듈을 찾아봤다.

그 결과 아주 적절한 Games::Cards::Poker 모듈을 발견하여 사용하기로 했다.
내가 원하는 함수가 모두 구현되어 있었으므로, 아주 간단했다.

추가로, 이전까지는 문제에서 주어진 데이터를 코드에 직접 삽입하여 문제풀이를 하였으나, 이번 파일부터 그 크기가 감당할 수 없이 커져버렸다.
따라서 외부 파일에서 데이터를 불러와 사용하기로 하였는데, 나는 명령행 인자로 파일 경로를 넘겨주는 방식으로 구현했다.




프로젝트 오일러 53번

  • 2013/09/21
  • Perl

1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345

조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.

nCr    =
n!
r!(n−r)!
,         단 rn 이고, n! = n×(n−1)×…×3×2×1 이며 0! = 1.

이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.

1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)




프로젝트 오일러 52번

  • 2013/09/20
  • Perl

125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.

2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?

사실 내 부족한 수학적 직관으로도 1/7과 관계가 있을거라 짐작을 하긴 했지만…
아무튼 문제는 그냥 풀었다. 오랫만에 쉬운 문제.




프로젝트 오일러 51번

  • 2013/09/20
  • Perl

두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.

56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.

이래저래 고생을 좀 한 문제.
자꾸 120383이 나오는데 이게 오답이여서 왜 그럴까 왜 그럴까 고심했다.

실행 소요시간은 약 10초




프로젝트 오일러 50번

  • 2013/09/18
  • Perl

41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

백만 이하의 소수를 모두 구해 배열에 넣어 놓고 구하자.




프로젝트 오일러 49번

  • 2013/09/18
  • Perl

1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.

  • 세 수는 모두 소수입니다.
  • 세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.

1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.

그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?

등차수열인 세 소수를 구해 순열인지 확인했다.




프로젝트 오일러 48번

  • 2013/09/18
  • Perl

11 + 22 + 33 + … + 1010 = 10405071317 입니다.

11 + 22 + 33 + … + 10001000 의 마지막 10자리 숫자는 무엇입니까?

Math::BigInt를 이용하여 구했다.
사실 마지막 10자리만 끊어서 계산해도 무방하지만, 약 10초 내로 결과가 나오기에 그냥 풀기로 했다.




프로젝트 오일러 47번

  • 2013/09/18
  • Perl

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?

해쉬를 이용하여 좀 더 빠르게 구한다.




프로젝트 오일러 46번

  • 2013/09/18
  • Perl

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

우변의 2×제곱수 항을 좌변으로 넘겨, 좌변이 소수인지 확인한다.




프로젝트 오일러 45번

  • 2013/09/17
  • Perl

삼각수, 오각수, 육각수는 아래 식으로 구할 수 있습니다.

삼각수   Tn = n (n + 1) / 2   1, 3, 6, 10, 15, …
오각수   Pn = n (3n − 1) / 2   1, 5, 12, 22, 35, …
육각수   Hn = n (2n − 1)   1, 6, 15, 28, 45, …

여기서 T285 = P165 = H143 = 40755 가 됩니다.

오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요.

이전 44번 문제를 풀었다면, n각수 판별식을 쉽게 만들 수 있다. 이를 이용하면 된다.

이 때, 변수가 정수인지 판별하는 함수가 필요한데, Scalar::Util::Numeric 모듈의 isint 함수를 사용해도 되겠지만, 정규식을 이용하여 판별하여도 성능상 크게 관계가 없다.