이 블로그는 더 이상 업데이트되지 않습니다.

최신 내용을 확인하시려면 여기를 클릭해주세요.

Programming (77)


프로젝트 오일러 24번

  • 2013/09/14
  • Perl

어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.

이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다.
0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.

012 021 102 120 201 210

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?

f는 팩토리얼, g는 자리수 구하기
내가짰지만 좀 복잡한 듯…




프로젝트 오일러 23번

  • 2013/09/14
  • Perl

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다.
따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다.
두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

배열을 하나 만들어, ‘체’처럼 사용했다.
실행시간은 약 5초정도.




프로젝트 오일러 22번

  • 2013/09/13
  • Perl

여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요).
이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.

  • 먼저 모든 이름을 알파벳 순으로 정렬합니다.
  • 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, …, Z=26)를 모두 더합니다.
  • 여기에 이 이름의 순번을 곱합니다.

예를 들어 “COLIN”의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.

names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?

ord로 문자의 아스키코드값을 구할 수 있다. (어떤 문자의 아스키코드 값 – 알파벳 A의 아스키코드값 + 1)을 하면 알파벳에 해당하는 숫자를 구할 수 있다.
그리고 정렬해서 샤바샤바하면 끝.




프로젝트 오일러 21번

  • 2013/09/13
  • Perl

n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때,
서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면
a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.

예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다.
또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다.
따라서 220과 284는 친화쌍이 됩니다.

10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요.

해쉬를 사용하여 구했다.
어떤 수 n에 대해 키는 n, 해쉬값은 d(n)으로 지정하여 끝까지 구한다.
그 후 ‘키’와 ‘키의 해쉬값을 키로 사용한 해쉬값’이 같은 경우를 찾아 모두 더한다.




프로젝트 오일러 20번

  • 2013/09/13
  • Perl

n! 이라는 표기법은 n × (n − 1) × … × 3 × 2 × 1을 뜻합니다.

예를 들자면 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800 이 되는데,
여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.

100! 의 자리수를 모두 더하면 얼마입니까?

bigint를 써서 해결




프로젝트 오일러 19번

  • 2013/09/13
  • Perl

다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다).

  • 1900년 1월 1일은 월요일이다.
  • 4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 31일까지 있다.
  • 2월은 28일이지만, 윤년에는 29일까지 있다.
  • 윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다

20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까?

DateTime 모듈을 사용하여 해결하였다.




프로젝트 오일러 18번

  • 2013/09/13
  • Perl

다음과 같이 삼각형 모양으로 숫자를 배열했습니다.

3
7 4
4 6
8 5 9 3

삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다.
다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

참고: 여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다.
하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.

참고의 말씀 받들어, 모든 경로를 구하는 방법 대신 다른 방법을 강구해 보았다.

밑에서 두번째 줄의 각 수에서, 그 아랫쪽 줄에 인접한 수 중 큰 수를 자신에 더한다.
그다음 밑에서 세번째 줄의 각 수에서, 그 아랫쪽 줄에 인접한 수 중 큰 수를 자신에 더한다.
이하 생략.

제일 윗줄까지 수행하면 답이 나온다.




프로젝트 오일러 17번

  • 2013/09/13
  • Perl

1부터 5까지의 숫자를 영어로 쓰면 one, two, three, four, five 이고,
각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다.
1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요?

참고: 빈 칸이나 하이픈(‘-‘)은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다.
예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자,
115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다.

프로그래머 입장에서는 정말 귀찮은 문제;;
하지만 Number::Spell 모듈과 함께라면 참 좋다.
spell_number로 해당 숫자를 영어로 바꾸어준다.
그 다음은 그냥 세기만 하면 끝.




프로젝트 오일러 16번

  • 2013/09/13
  • Perl

215 = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.
21000의 각 자리수를 모두 더하면 얼마입니까?

일반적으로는 Math::BigInt를 사용하여 큰 정수를 처리하겠지만 이번에는 bigint를 사용해봤다.
bigint는 기존 연산자를 그대로 이용하여 프로그래밍 할 수 있어 편하니까…




프로젝트 오일러 15번

  • 2013/09/13
  • Perl

아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).

프로젝트 오일러 15번 그림

그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?

중학교때(?) 배웠던 기억을 되살려 풀었다.