본문 바로가기

알고리즘20

[Algorithm] Greedy 30 (백준) - 에이젠 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 공략 10^5개의 숫자로 구성된다라는 말은 예제를 보면 10^5보다 큰 숫자가 있었기에 자리수가 10^5 자리까지 있다는 것을 알 수 있었습니다. 완전탐색으로는 역시 풀 수 없겠죠. 1. 숫자 안에 0 이 꼭 필요하다. 30의 배수이기 때문에 0이 없으면 안 되는 것을 알 수 있었습니다. 1의자리 빼고는 3의배수가 나오도록 가장 큰 수를 찾아야하는데... 결국 힌트를 찾아보았습니다. 2. 모든 자.. 2022. 9. 12.
[Algorithm] Greedy 대회or인턴 (백준) - 에이젠 https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 실수 남자1명 여자2명인데 반대로 읽음... 낙오자 계산할때 팀매칭된 그룹 수를 갱신해 주지 않아서 틀림. 공략 알고리즘 중급 1/3 의 그리디 연습 문제입니다. 남자가 인원수가 훨씬 많다는 가정하에 과정을 설명해보겠습니다. 1. 각각 주어진 남 여 인원수를 팀에 필요한 인원수로 나눕니다. M / 2 : 몫1 + 나머지1 , N / 1 : 몫2 + 나머지2 2. 각각 나눈 몫중에 작은 값이 인턴이 없을 때 나올 수 있는 팀 개수입니다. 남자가 훨씬 많으니 몫2가 .. 2022. 9. 11.
[Algorithm] Greedy 수 묶기(백준) - 에이젠 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 실수 처음에 입출력 예제의 예상 값과 답이 다르게 나오길래 문제를 잘못이해했나? 하고 헤맸는데 알고보니 첫째줄은 수열의 길이를 입력하는 것인데 첫째줄까지 연산에 포함시키는 바보짓을 했네요. ㅎㅎ 공략 알고리즘 중급 1/3 의 그리디 연습 문제입니다. 1. 정렬 수행. 2. 묶는다 -> 큰 양수 x 큰 양수 (1이 아닌 양수) -> 작은 음수 x 작은 음수 -> 작은 음수 x 0 3. 덧셈 수행.. 2022. 9. 10.
[Algorithm] Greedy 잃어버린 괄호(백준) - 에이젠 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net '공략 알고리즘 중급 1/3 의 그리디 연습 문제입니다. + - 연산만으로 이루어진 식에 적절히 괄호를 사용하여 최솟값을 출력하는 것이 목표입니다. 가장 큰 수를 뺄셈해주면 최솟값이 나오는 것을 우리는 알고 있죠. 따라서 모든 +연산을 수행하고 마지막에 남은 - 연산을 해주면 답이 나오겠습니다. import java.util.*; public class Main { static Scann.. 2022. 9. 9.
[Algorithm] Greedy 동전0 (백준) - 에이젠 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 공략 백준 알고리즘 분류가 아닌 온라인 강의에 있는 문제를 따라가면서 풀기로 계획을 바꾸었습니다. 알고리즘 중급 1/3 의 그리디 첫번째 문제입니다. 그리디 알고리즘을 처음 소개한대로 이번 문제도 매 순간 최적의 값을 찾아 반복하면 되겠습니다. 목표한 K원만큼을 최소한의 동전으로 채우는 것이 목표입니다. 가치가 큰 동전을 최대한 많.. 2022. 9. 2.
[Algorithm] Greedy 설탕 배달 (백준) - 에이젠 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 공략 백준 알고리즘 분류에서 그리디 알고리즘 첫번째 문제 입니다. 그리디는 최적에 해에 가까운 값을 찾을 때 사용되며 매 순간 최적이라고 생각되는 경우를 선택하며 반복합니다. 문제에서 이와 같은 방식으로 풀어보겠습니다. 5kg 봉지와 3kg봉지에 Nkg의 설탕을 담아 배달한다고 합니다. 어떻게 담아야 봉지 개수를 최소로 할 수 있을까요? 직관적으로 5kg이 많을수록 봉지 개수가 최소한인 최적의 값인 것을 알.. 2022. 9. 1.
[Algorithm] Dijkstra 특정 거리의 도시 찾기 (백준) - 에이젠 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 공략 다익스트라 알고리즘 문제 입니다. 정답률은 28퍼센트로 낮아보이네요. 하지만 그동안 풀었던 다익스트라 문제유형과 거의 똑같아서 쉽게 풀 수 있었습니다. 특정거리 K 번째의 dist요소들을 찾아서 출력하면 되겠습니다. import java.util.*; public class Main { static Scanner sc .. 2022. 8. 31.
728x90

티스토리툴바