본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 4134] 다음 소수 (python) https://www.acmicpc.net/problem/4134 4134번: 다음 소수 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. www.acmicpc.net 다음 소수 문제 n보다 크거나 같은 소수 중에서 가장 작은 소수를 찾는 문제 에라토스테네스의 체를 이용해서 풀 수 있었다 📌 문제 접근 포인트 1. n보다 크거나 같은 소수를 찾아야 하므로, n이 소수인지 아닌지 판별하고 +1씩 늘려가도록 알고리즘을 고려해보자. 2. 소수를 판별하는 과정에서 숫자가 굉장히 크므로 에라토스테네스의 체를 이용해서 빠르게 찾아내주고, 이를 활용하여 소수 판별을 해주자. 3. 소수를 판별하는 과정에서 n의 제곱근 만큼 탐색을 진행하게 되는.. 2023. 4. 14.
[백준 2885] 초콜릿 식사 (python) https://www.acmicpc.net/problem/2885 2885번: 초콜릿 식사 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ... www.acmicpc.net 초콜릿 식사 문제 2의 n제곱 개의 정사각형으로 이루어진 초콜릿을 쪼개면서 원하는 개수만큼 먹고 싶을 때, 어느 크기의 초콜릿과 몇 번 쪼개야 가능한지 찾는 문제 while문을 통해 그리디하게 찾아서 해결할 수 있었다. 📌 문제 접근 포인트 1. 초콜릿의 크기를 먼저 정해야한다. 초콜릿의 크기를 정해주기 위해서 초콜릿은 1, 2, 4, 8... 즉 2의 n제곱으로 이루어진 .. 2023. 4. 13.
[백준 24058] Coprime (python) https://www.acmicpc.net/problem/24058 Coprime (서로소) 문제 n*k 이하의 자연수와 n의 서로소 들의 합을 구하는 문제 소수 개념과 포함 배제의 원리를 통해 해결할 수 있었다. 📌 문제 접근 포인트 더보기 1. N과 서로소인 것의 개수를 구해야하는데, 서로소의 정의상 두 정수를 나눌 수 있는 양의 정수가 1밖에 없다는 뜻은 소수들의 집합으로 비교하는 것을 의미한다. N 그 자체를 이용하기보단 N을 포함하고, N보다 작은 소수들을 이용해서 찾아서 계산해야한다. 2. 에라토스테네스의 체 개념을 이용해서 빠르게 소수를 구할 수 있게 구성해주자. 단순히 소수를 구하기만 해선 N의 값이 10**9에 해당하는 숫자이므로 시간이 오래걸릴 수 있다. 그렇기에 N의 크기를 작게 만들.. 2023. 4. 12.
[백준 9359] 서로소 (python) https://www.acmicpc.net/problem/9359 9359번: 서로소 첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109) www.acmicpc.net 서로소 문제 A 2023. 4. 11.
[백준 17436] 소수의 배수 (python) https://www.acmicpc.net/problem/17436 17436번: 소수의 배수 첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다. www.acmicpc.net 소수의 배수 문제 자연수 M 이하의 수 중에서 주어진 N개의 소수 중에 적어도 하나로 나누어 떨어지는 수의 개수를 세는 문제 포함배제의 원리에 대해 알고 있다면 어렵지 않게 해결 할 수 있다. 부분 집합을 찾는 과정에서 백트래킹을 이용했다. 📌문제 접근 포인트 1. 포함 배제의 원리에 대해 생각해보자. n(A∪B) = n(A) + n(B) - n(A∩B) 가 대표적인 예시로,.. 2023. 4. 11.
[백준 18429] 근손실 (python) https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 근손실 문제 주어진 용량 키트를 사용하여 운동을 할 때, 근손실로 인한 중량이 500보다 작아지지 않게 할 수 있는 경우의 수를 모두 찾는 문제 백트래킹을 이용하여 해결 할 수 있었다. 📌 문제 접근 포인트 1. 근손실로 인한 중량이 500보다 작아지지 않게 하도록 경우의 수를 탐색해보자. 2. 매일같이 근손실이 일어나므로 K를 빼줄 수 있게 구성하고, 각 키트를 중복으로 선택하지 않도.. 2023. 4. 11.
반응형

티스토리툴바