개발/알고리즘 문제
[Project Euler 56] ab 형태의 자연수에 대해 자릿수 합의 최대값 구하기
2017.08.17구골(googol)은 10100을 일컫는 말로, 1 뒤에 0이 백 개나 붙는 어마어마한 수입니다. 100100은 1 뒤에 0이 2백 개가 붙으니 상상을 초월할만큼 크다 하겠습니다. 하지만 이 숫자들이 얼마나 크건간에, 각 자릿수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다. a, b < 100 인 자연수 ab 에 대해서, 자릿수의 합이 최대인 경우 그 값은 얼마입니까? 0.2초 정도 걸림
[Project Euler 42] 주어진 텍스트 파일에 들어있는 '삼각단어'의 개수는?
2016.07.06n번째 삼각수는 tn = ½ n (n + 1) 이라는 식으로 구할 수 있는데, 처음 10개는 아래와 같습니다. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... 어떤 영어 단어에 대해서, 각 철자의 알파벳 순서(A=1, B=2, ..., Z=26)를 모두 더한 값을 '단어값'이라 부르기로 합니다. 예를 들어 'SKY'의 단어값은 19 + 11 + 25 = 55가 되는데, 이것은 우연히도 t10과 같습니다. 이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 '삼각단어'라 부르기로 합니다. 약 16KB의 텍스트 파일 words.txt에는 2000개 정도의 영어 단어가 수록되어 있습니다. 이 중에서 삼각단어는 모두 몇 개입니까?
[Project Euler 41] n자리 팬디지털 소수 중에서 가장 큰 수
2016.07.061부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다. 2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다. n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까? 팬디지털엔 수열을 써왔는데...수열은 아무래도 수가 많아질수록 좀 느리다.
[try helloworld level 5] 124나라의 숫자
2016.06.021,2,4 세 개의 숫자만 쓰는 124나라가 있습니다. 124나라에서 사용하는 숫자는 다음과 같이 변환됩니다.10진법의 1 → 110진법의 2 → 210진법의 3 → 410진법의 4 → 1110진법의 5 → 1210진법의 6 → 1410진법의 7 → 2110진법의 수 N이 입력될 때, 124나라에서 쓰는 숫자로 변환하여 반환해주는 change124 함수를 완성해 보세요. 예를 들어 N = 10이면 “41”를 반환해주면 됩니다. 리턴 타입은 문자열입니다. itertools 만세!!!
[try helloworld level 3] 다음 큰 숫자
2016.06.02어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다. N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.
[try helloworld level 3] 시저 암호
2016.06.02어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다. 보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.“a B z”,4를 입력받았다면 “e F d”를 리턴합니다. string 모듈을 import해보는 건 처음이다!!저번 주에 일을 하면서 api response를 받아올 때, request 파라미터를 정렬시켜 key를 암호화한 적이 있는데(굉장히 신기했음. hashlib.sha256, hmac, base64 등을 썼었다), 그래선지 꽤 재밌게 풀었다. 근데 tryhelloworld에서는 왜 오류가 난다냐....
[try helloworld level 2] 행렬의 곱셈
2016.06.02행렬의 곱셈은, 곱하려는 두 행렬의 어떤 행과 열을 기준으로, 좌측의 행렬은 해당되는 행, 우측의 행렬은 해당되는 열을 순서대로 곱한 값을 더한 값이 들어갑니다. 행렬을 곱하기 위해선 좌측 행렬의 열의 개수와 우측 행렬의 행의 개수가 같아야 합니다. 곱할 수 있는 두 행렬 A,B가 주어질 때, 행렬을 곱한 값을 출력하는 productMatrix 함수를 완성해 보세요. 신기하게도(?) 로직은 맞게 짰는데 처음 0으로 채워진 행렬을 만들어줄 때 잘못 코딩했다. answer = [[0]*col_b]*row_a 을 사용했는데, 이건 행렬이 아니었다.(그냥 row_a 개 복사된 리스트였음) 깊은 복사(deepcopy)에 대해서는 차차 더 알아가도록 하고... 정말 기초적인 알고리즘에서 의외의 것을 배우게 된다.
[try helloworld level 1] 최대공약수와 최소공배수
2016.06.02두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환해주는 gcdlcm 함수를 완성해 보세요. 배열의 맨 앞에 최대공약수, 그 다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 gcdlcm(3,12) 가 입력되면, [3, 12]를 반환해주면 됩니다.
[Project Euler 40] 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기
2016.05.06소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다. 0.123456789101112131415161718192021... 이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 (위에서 붉게 표시된 숫자). 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까? d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 꽤나 간단한 문제였는데 푸는 데는 좀 걸렸다. 식 자체는 바로 냈는데 그 식이 3분 넘게 걸린다는 게 문제였지... 처음엔 양의 정수를 뒤에 붙일 때마다 리스트에 추가하고, ''.join() 으로 나열했는데 이게 시간을 어마무지하게 잡아먹었다. 내가 삽질했다는 걸 깨닫고 나서 그냥 str로 계속..
[Project Euler 39] 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?
2016.05.05세 변의 길이가 모두 자연수 {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초. 여기서부터는 로직이 아니라 수학(이걸 수학이라 부를 수 있다면.)이 ..
[Project Euler 38] 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자
2016.05.04숫자 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번 팬디지털 문제를 풀었다. 예전에는 끙끙거리면서 결국 못 풀었는데 요즘 그래도 늘고 있는지 둘 다 ..
[Project Euler 32] 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합
2016.05.021부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다. 예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다. 7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다. 이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까? (참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다) 오늘 건...좀 멍청하게 짰다. 수도코드도 짜지 않았고... 풀기 귀찮아서 계속 미루다가 38번이 팬디지털을 응용하는 문제여서 풀었다. 좀더 예쁘게 짤 수 있을 것 같은데... 팬디지털..