본문 바로가기
반응형

알고리즘 풀이164

[백준 4673] 셀프 넘버 (python) https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 셀프 넘버 문제 n과 n의 각 자리 수를 더하는 함수 d(n)에 대해 10000보다 작은 셀프 넘버들을 출력해보는 문제 구현 문제라 요구사항 대로 풀어주면 어렵지 않게 풀 수 있다. ⚙️ 내가 푼 정답코드 def self_num(n): # 생성자 만들기 x = list(str(n)) result = 0 for i in range(len(x)): r.. 2023. 4. 7.
[백준 11440] 피보나치 수의 제곱의 합 (python) https://www.acmicpc.net/problem/11440 11440번: 피보나치 수의 제곱의 합 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수의 제곱의 합 문제 피보나치 수를 분할 정복을 이용해서 구하고, 규칙을 찾아서 구해주면 해결할 수 있는 문제 분할 정복만 잘하면 어렵지 않게 해결 가능! ⚙️ 내가 푼 정답 코드 import sys N = int(sys.stdin.readline()) x = [[1,1],[1,0]] def mult(a,b): # 행렬의 곱을 구하자 A = [[0,0],[0,0]] # 2차원 행렬 for i in range(2): for j in range(2): for .. 2023. 4. 7.
[백준 13977] 이항 계수와 쿼리 (python) https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 이항 계수와 쿼리 문제 이항 계수를 10**9+7로 나눈 나머지를 구하는 문제 모듈러 연산, 페르마의 소정리, 분할 정복에 대한 개념에 대한 이해가 있어야 풀 수 있던 문제 ⚙️ 내가 푼 정답 코드 import sys M = int(sys.stdin.readline()) p = 1000000007 factorial = [1]*4000001 for i in range(2,4000001): # 펙토리얼 구.. 2023. 4. 7.
[백준 13949] 쉬운 문제 (python) https://www.acmicpc.net/problem/13949 13949번: 쉬운 문제 1보다 큰 정수 k가 주어졌을때, 다음 식을 만족하는 양의 정수 (a,b,c)는 무수히 많다는 것을 증명할 수 있다: a2 + b2 + c2 = k (ab + bc + ca) + 1. 양의 정수 n과 k가 주어졌을때 위 식을 만족하는 임의 n개 www.acmicpc.net 쉬운 문제 문제 식을 만족하는 임의의 n개의 양의 정수를 찾는 문제 수학적 개념에 대한 이해와 시도를 통해서 해결할 수 있었다 📌 문제 접근 포인트 1. 공식에 대해 생각해보자 a^2 + b^2 + c^2 = k*(ab+bc+ca) + 1 이란 공식을 변형시킬 방법을 생각해야 한다. 2. 임의로 a = 0, b = 1을 대입해보자. 그러면 c .. 2023. 4. 7.
[백준 1515] 수 이어 쓰기(python) https://www.acmicpc.net/problem/1515 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 수 이어 쓰기 문제 이어 써 나간 숫자의 일부를 가 빠졌을 때, 이 숫자로 만들 수 있는 최소 이어 붙인 수 N의 값을 구하는 문제 구현 + 브루트포스 문제로 하나씩 더해나가면서 대조해 가면서 찾는 문제이다. ⚙️내가 푼 정답 코드 import sys S = sys.stdin.readline().strip() n = 0 while len(S): n += 1 # 1칸씩 찾기 num = str(n).. 2023. 4. 3.
[백준 11402] 이항 계수 4(python) https://www.acmicpc.net/problem/11402 11402번: 이항 계수 4 첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수) www.acmicpc.net 이항 계수 4 문제 이항 계수를 소수로 나누었을 때의 나머지를 구하는 문제 뤼카의 정리를 이용하여 해결할 수 있다. ⚙️정답 코드 def Lucas(n,k): #뤼카의 정리 if n < k : # nCk 에서 K가 더 클 경우 return 0 elif n == k : # nCk 에서 n과 k가 같을 경우 return 1 x = 1 for i in range(1, k+1): # 그외 k가 더 큰 경우 k까지 늘려.. 2023. 4. 3.
반응형

티스토리툴바