본문 바로가기
반응형

알고리즘 풀이164

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

티스토리툴바