늒네 기록

2557번: Hello World (acmicpc.net) 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net 인풋을 받을 필요 없는 단순한 출력 문제다. 1 console.log('Hello World!') cs

1000번: A+B (acmicpc.net) 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 1000번 문제는 boj help 페이지에 각 언어별로 솔루션이 나와있다. 이를 통해서 인풋을 받아서 연산을 하고 아웃풋을 출력하는 기본적인 방법에 대한 힌트를 얻을 수 있다. 언어 정보 (acmicpc.net) 언어 정보 section .data input: db "%d %d",0 output: db "%d",10,0 a: times 4 db 0 b: times 4 db 0 section .text global main extern scanf extern printf main: push rbp mov rdi, input lea rsi,..

프로젝트 오일러 41번은 어떤 소수 n이 x자리 수일때, 1부터 x까지의 숫자가 모두 등장하면 이를 pandigital prime이라고 부른다고 한다면, 이러한 조건을 만족하는 제일 큰 소수 p를 구하라는 문제다. pandigital 조건이 붙어있으므로 p는 아무리 커도 9자리여야 하는데, 1~9가 모두 등장하는 9자리 수는 각 자릿수를 다 더하면 45이므로 3의 배수가 되어 소수가 될 수 없다. 즉, p는 아무리 커봐야 8자리인 것이다. 문제에 나이브하게 접근하여 8자리 소수들을 전부 구한 뒤, 큰 소수부터 시작하여 위의 조건을 만족하는지 체크하는 루프를 도는 방식으로 문제를 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 n=10**8 p = [True ..

프로젝트 오일러 37번도 나이브하게 덤볐는데도 풀린 문제. 이 문제는 어떤 숫자 p가 주어졌을때, 이 숫자 자체도 소수이면서 좌측부터 숫자를 하나씩 제거하면서 만드는 숫자들도 전부 소수, 우측부터 숫자를 하나씩 제거하면서 만드는 숫자들도 전부 소수인 숫자를 truncatable prime이라고 정의하고, 딱 11개 존재하는 이 숫자들을 전부 찾아서 더하라는 문제다. 별 다른 테크닉 없이 10부터 시작하여 1씩 더해가면서 해당 숫자가 조건을 만족하면 리스트에 더하는 루프를 돌고, 리스트 크기가 11이 되면 루프를 빠져나오는 식으로 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def p_test(n): if n

프로젝트 오일러 27번에 처음 접근하면서 이거 나이브하게 풀어도 풀릴까 테스트 먼저 해보자고 생각하고 달려들었는데 바로 풀려버려서... 문제는 n^2 + a*n + b 꼴의 함수가 주어졌을때, 절댓값 1000 이하의 두 정수 a, b를 선택하여 n=0부터 i 이하의 숫자들을 대입했을 때 전부 소수가 되도록 하는 최대 i의 값이 최대가 되도록 하는 것이다. 즉, (a, b) 쌍에 대해 i가 결정되는데, 이 i값을 최대로 만드는 (a, b)쌍을 구하는 것. 나이브한 방법으로 풀 때에는 다음의 아이디어만 있어도 충분하다. - 어떤 수가 소수인지 판별하기 위해서는 2부터 그 수의 제곱근 이하의 모든 자연수에 대하여 나눠보면 된다. - 조금 탐색 공간을 줄이고 싶다면, n=0을 대입했을 때 값이 b가 되므로, b..

프로젝트 오일러 72번은 분모가 1,000,000 이하인 진분수의 전체 개수를 구하는 문제다. 이 문제를 풀기 위해서는 분모가 k로 주어져있을 때 진분수가 몇 개인지 구하는 방법을 알아야 하는데, 분자를 a, 분모를 b라 하면 진분수는 - gcd(a, b) = 1 - a

프로젝트 오일러 57번은 패턴만 찾으면 거저먹는 문제. i번째 분수가 b/a꼴로 생겼다고 하면, i+1번째 분수는 1+1/(1+b/a) = 1+1/((a+b)/a) = 1+a/(a+b) = (2a+b)/(a+b)가 되어, i번째 분수의 분자, 분모로 i+1번째 분수의 분자, 분모를 바로 구할 수 있으니 이를 활용하자. 1 2 3 4 5 6 sol=0 a,b=1,1 for _ in range(1000): a,b=a+b,2*a+b if len(str(a))

프로젝트 오일러 55번에서는 Lychrel number라는 것에 대해 먼저 설명해준다. 예를 들어 47이 주어졌을 때 이를 뒤집은 74를 더하면 121이 되어 1회 시행만에 palindrome이 된다. 349의 경우 349+943=1292 1292+2921=4213 4213+3124=7337 즉, 3회 시행만에 palindrome이 된다. Lychrel number는 이러한 뒤집기-더하기 시행을 아무리 반복해도 palindrome이 되지 않는 숫자를 뜻하는데, 이 문제에서는 10000보다 작은 숫자들 중에 이러한 뒤집기-더하기 시행을 50번 반복하는 동안 palindrome이 나오지 않으면 Lychrel number라고 친다 하고 이런 숫자가 몇 개나 있는지 구하라고 한다. 이 문제는 뒤집기-더하기 시행..

프로젝트 오일러 93번은 서로 다른 한 자리 숫자 4개가 주어졌을 때, 사이에 +, -, *, /, (, )를 적당히 끼워넣은 뒤 계산했을 때 나올 수 있는 숫자들을 전부 구한 다음, 그 안에 1부터 n 사이의 모든 숫자가 있다고 말할 수 있는 최대 n을 구하는 문제다. 예를 들어, 나올 수 있는 숫자들을 작은 순서대로 나열했을 때 1, 2, ..., 28, 30, ... 이런 리스트가 나온다면, 29를 만드는 방법이 없고 그보다 작은 자연수들은 모두 표현 가능하므로 답은 28. 계산식을 string으로 만든 뒤 이를 계산해주는 방법과, 숫자들의 순서, 사칙연산 기호의 순서를 조합해주는 방법을 알고 있으면 잘 활용해서 풀 수 있는 문제다. 아래의 두 글에 나온 함수들만 안다면 쉽게 풀 수 있을 것이다. ..

문제 링크: http://codeforces.com/contest/1408/problem/B 음이 아닌 정수로 이루어진, 감소하지 않는 순서로 정렬된 리스트 a_1, a_2, ..., a_n이 주어져있을 때, 크기 n짜리 리스트 m개를 만들어서 각 리스트의 i번째 아이템을 다 더해서 a_i가 되도록 만들고자 한다. 이때, m개의 리스트들 각각은, 최대 k개의 서로 다른 원소로 이루어질 수 있다. 예를 들어, n = 5, k = 3, a = [1, 2, 3, 4, 5]로 주어져있다고 하자. a는 [1, 2, 0, 0, 0], [0, 0, 3, 4, 0], [0, 0, 0, 0, 5]의 3개의 리스트들을 같은 위치에 있는 원소들끼리 더해서 만들 수 있다. [1, 2, 0, 0, 0], [0, 0, 3, 4,..