본문 바로가기
반응형

알고리즘 풀이164

[백준 25974] 거듭제곱의 합1 (python) https://www.acmicpc.net/problem/25974 25974번: 거듭제곱의 합 1 $1$부터 $n$까지 모든 자연수의 $p$ 거듭제곱의 합을 $10^9+7$로 나눈 나머지를 구하시오. 다시 말해, $$\left(\sum_{k=1}^{n}k^p\right)\mod\left(10^9+7\right)$$ 을 구하시오. www.acmicpc.net 거듭제곱의 합1 문제 백준의 1492 합 문제와 동일한데 제곱의 단위수가 20배나 높은 문제. 파스칼의 삼각형 개념과 다이나믹 프로그래밍을 통해서 해결할 수 있었다. 📌 문제 접근 포인트 0. 제곱 수들의 합 아이디어에 대해서 참고하면 좋을 사이트 https://www.mathpages.com/home/kmath279/kmath279 아래 내용이 이.. 2023. 4. 9.
[백준 1492] 합 (python) https://www.acmicpc.net/problem/1492 1492번: 합 N과 K가 주어졌을 때, 1K + 2K + 3K + ... + NK를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 합 문제 1부터 N까지 각각 k제곱한 수들의 합을 구하는 문제 k의 수가 작아서 처리 시간이 오래 걸리지 않는 문제 이항계수, 분할정복, 다이나믹 프로그래밍 등의 개념을 적절하게 섞어서 해결 할 수 있는 문제로 수식을 연산하고 떠올리는 과정이 생각보다 어려워서, 쉽게 접근하기는 어려웠다. 오랜 시간 고민하고, 수식 변형해서 해낼 수 있던 문제! 📌 문제 접근 포인트 0. 제곱 수들의 합 아이디어에 대해서 참고하면 좋을 사이트 https://www.mathp.. 2023. 4. 9.
[백준 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.
반응형

티스토리툴바