본문 바로가기
반응형

개발/알고리즘 문제56

[Project Euler 40] 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기 소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다. 0.123456789101112131415161718192021... 이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 (위에서 붉게 표시된 숫자). 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까? d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 꽤나 간단한 문제였는데 푸는 데는 좀 걸렸다. 식 자체는 바로 냈는데 그 식이 3분 넘게 걸린다는 게 문제였지... 처음엔 양의 정수를 뒤에 붙일 때마다 리스트에 추가하고, ''.join() 으로 나열했는데 이게 시간을 어마무지하게 잡아먹었다. 내가 삽질했다는 걸 깨닫고 나서 그냥 str로 계속.. 2016. 5. 6.
[Project Euler 39] 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는? 세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다. {20, 48, 52}, {24, 45, 51}, {30, 40, 50} 1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마입니까? 피타고라스 정의를 이용하는 문제.일단 수도코드 #1차) 101.58초(왓더...)#2차) 24.49초. a, b for loop를 전부 도는 대신 p/2로 변경#3차) 23.42초. math.ceil() 대신 round를 씀. 다른 것도 math.sqrt()를 써봤는데 안 쓰는 게 더 빠른 듯하다.#4차) 12.57초. 여기서부터는 로직이 아니라 수학(이걸 수학이라 부를 수 있다면.)이 .. 2016. 5. 5.
[Project Euler 38] 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자 숫자 192에 1, 2, 3을 각각 곱합니다. 192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 '곱해서 이어붙이기'라고 부르기로 합니다. 같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다. 어떤 정수와 (1, 2, ... , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1) 이 문제를 풀려고 미뤄뒀던 32번 팬디지털 문제를 풀었다. 예전에는 끙끙거리면서 결국 못 풀었는데 요즘 그래도 늘고 있는지 둘 다 .. 2016. 5. 4.
[Project Euler 32] 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합 1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다. 예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다. 7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다. 이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까? (참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다) 오늘 건...좀 멍청하게 짰다. 수도코드도 짜지 않았고... 풀기 귀찮아서 계속 미루다가 38번이 팬디지털을 응용하는 문제여서 풀었다. 좀더 예쁘게 짤 수 있을 것 같은데... 팬디지털.. 2016. 5. 2.
반응형