본문 바로가기
반응형

전체 글330

[백준 10830] 행렬 제곱 (python) https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱 문제 행렬의 곱을 연속해서 반복해서 결과를 출력하는 문제 분할정복을 이용하면 어렵지 않게 구현 할 수 있다. 📌문제 접근 포인트 1. 행렬의 제곱을 구하기 위해선 먼저 행렬의 곱셈 연산을 해줘야 한다. 행렬의 곱을 먼저 만들어주자. 2. 이제 행렬의 곱을 구했으니, 제곱은 이 곱을 반복하는 연산이고, 빠르게 곱을 하기 위해서 분할 정복 개념을 사용해서 제곱을 구성해주자. 3. 문제 요구조건대로 100.. 2023. 4. 9.
[백준 2740] 행렬 곱셈 (python) https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 행렬 곱셈 문제 행렬의 곱셈을 구해서 출력해보는 문제 행렬 연산 원리만 알면 쉽게 풀 수 있다. 📌 문제 접근 포인트 1. 행렬의 곱셈 연산에 대해 생각해보자. 2. 행렬은 A의 i 행 * B i 열 곱을 다 더한 형태로 되어있다. 3. 곱해서 출력하게 만들어주면 해결! ⚙ 내가 푼 정답 코드 def multi(a,b): X = [[0]*K for _ in range(N)] fo.. 2023. 4. 9.
[백준 15965] K번째 소수 (python) https://www.acmicpc.net/problem/15965 15965번: K번째 소수 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) www.acmicpc.net K번째 소수 문제 K번째 소수를 출력하는 문제, 에라토스테네스의 체를 이용해서 소수를 구하고, k번째 소수를 구해보자 에라토스테네스의 체 개념만 알면 어렵지 않게 풀 수 있다. 📌 문제 접근 포인트 1. K번째 소수를 구하는 알고리즘을 짜야하는데, K의 최대 요구사항이 40000인점을 생각해야한다. 2. 40000번째 소수까지 구해주려면 40000번째 소수가 약 700만이 넘어가는 숫자이기에, 어느정도 되는 수까지 소수를 먼저 구해줄 필요가 있다. 3. 에라토스테네스의 체로 소수를 구하면 빠르게 연산해서 구해줄 수 있다. 4. 요.. 2023. 4. 8.
[백준 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.
반응형

티스토리툴바