본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 9735] 삼차 방정식 풀기 (python) https://www.acmicpc.net/problem/9735 9735번: 삼차 방정식 풀기 첫째 줄에 테스트 케이스의 개수 N (0 < N < 100)이 주어진다. 다음 N개 줄에는 삼차 방정식의 계수 A, B, C, D가 한 줄에 하나씩 주어진다. www.acmicpc.net 삼차방정식 문제 정수해 1개가 확정적으로 존재하는 삼차방정식의 해를 구해 출력해 보는 문제 삼차방정식의 수학적 개념을 이해해야 풀 수 있었다. 📌 문제 접근 포인트 1. 요구사항을 보면, x 중에 1개는 정수(α)로 주어짐을 알 수 있다. 즉, 정수의 숫자 1개를 이용해서 3차 방정식의 차원을 낮출 수 있다. 2. 정수값 1개 (α) 를 알고 있으면 삼차방정식은 (x-α)(a'x^2+b'x+c')의 꼴로 나타낼 수 있고, 나.. 2023. 4. 8.
[백준 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.
반응형

티스토리툴바