[백준] 10870번 피보나치 수 (Python) Source https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net How to solve? 피보나치 규칙에 따라서 0일 경우 0, 1일 경우 1, 2일 경우 1로 예외처리를 해준 후 fib(n-1) + fib(n-2) 재귀함수를 만든다. Code import sys N = int(sys.stdin.readline()) def fib(n): if n == 0: r..
Problem solve
[백준] 10872번 팩토리얼 (Python) Source https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net How to solve? 자기 자신을 호출하는 재귀함수를 사용해 문제를 해결한다. Code import sys N = int(sys.stdin.readline()) def factorial(n): if n == 0: return 1 return n * factorial(n-1) print(factorial(N))
[백준] 4948번 베르트랑 공준 Source https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net How to solve? 1929번 문제 풀이 같이 하나하나 대입하여 나누고, 소수인지를 판별하면 시간초과가 발생한다. 따라서 에라토스테네스의 체 원리를 이용하여 문제를 풀이한다. 만약 X를 a*b라고 표현했을 때 X의 제곱근 n에 대하여 a와 b 둘 다 n보다 큰 경우는 없기 때문에 제곱근까지만 판별을 해주면 된다. 이후 파이썬의 리스트 슬라..
[백준] 1193번 분수찾기 (Python) Source https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net How to solve? 지그재그 변경을 따라가면서 문제를 해결하면 시간초과가 나게 된다. 1/1을 첫번째 대각선(총 1개) 1/2, 2/1을 두번째 대각선(총 2개), ...으로 보게 된다면 N번째 대각선이 되기 위해서는 입력된 수 X가 N(N-1)/2 초과, N(N+1)/2 이하일 것이 필요하다. while True: if line*(line+1)/2 >= X: break line += 1 이때 N(line)이 홀수라면 입력 수가 늘어남에 따라 a가 하나씩 줄어들기 때..
[백준] 1929번 소수 구하기 (Python) Source https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net How to solve? 제곱근 범위 나누기법을 사용하여 계산 시간을 단축시킨다. 예를 들자면 9의 약수는 1 3 9이고 16의 약수는 1 2 4 8 16이다. 약수는 제곱근을 기준으로 대칭적으로 짝을 이루기 때문에, 소수임을 판별하기 위해 제곱근까지만 검사해도 답을 낼 수 있다. Code start, end = map(int, input().split()) if st..
[백준] 2581번 소수 (Python) Source https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net How to solve? 1. 시작하는 숫자가 0이나 1일 경우 소수 리스트에 포함되면 안되기 때문에 예외처리를 해준다. 2. 2중 for문을 작성하여 2부터 해당 숫자까지 나머지가 0인 경우가 발생한다면 (나누어 떨어진다면) 소수가 아니므로 is_prime을 False로 바꾸고 for문에서 빠져나간다. 3. 어떠한 숫자에도 나누어 떨어지지 않은채 루프가..
[백준] 11653번 소인수분해 (Python) Source https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net How to solve? 소인수분해 규칙에 따라서 N을 i로 나눌 수 있다면 나누고 나눌 수 없다면 i를 1씩 증가시킨다. Code N = int(input()) i = 2 while True: if N%i == 0: print(i) N = N/i if N%i != 0: i += 1 if N == 1: break if N == i: print(i) break
[백준] 1978번 소수 찾기 Source https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net How to solve? 숫자x와 1이 아닌 x보다 낮은 숫자로 나눈 값이 나누어 떨어진다면 소수가 아니다. 이 점을 이용하여 반복문을 만들고 리스트의 숫자를 하나씩 검사한다. Code import math T = int(input()) num_list = list(map(int, input().split())) count = 0 for i in range(T): flag = False for j in range(1, nu..
[백준] 10757번 큰 수 (Python) Source https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net How to solve? A,B를 입력받은 후 더하기 값 출력 Code A, B = map(int, input().split()) print(A + B) One step more ...
[백준] 2839번 설탕 배달 (Python) Source https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net How to solve? N을 5로 나눈 값 부터 시작하여 5씩 내려가는 반복문과, 3씩 증가하는 반복문을 중첩시켜 프루트포스 알고리즘으로 문제를 해결한다. Code n = int(input()) def sugar_bag(n): a = 5 b = 3 j = 0 an = n // a for i in range(an+1): ans = a*an - a*i..
