본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 10942] 팰린드롬? (python) https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 팰린드롬? 문제 주어진 수열에서 수열의 S번째부터 E번째까지 숫자들이 팰린드롬을 이루고 있는지 체크하는 문제 다이나믹 프로그래밍을 이용하여 해결할 수 있었다. 📌 문제 접근 포인트 1. 팰린드롬의 조건에 대해서 생각해보자. 팰린드롬의 경우 맨 앞에서부터 읽은 것이 뒤에서부터 읽은 것과 같은 경우이다. 2. 팰린드롬을 어떻게 구할지 생각해보자. 만약 단순하게 for문과 슬라이싱을 통해 모든 리스트를 탐색한다면 시간이 굉장히 많이 소요되기.. 2023. 4. 10.
[백준 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.
반응형

티스토리툴바