땀두 블로그

그리디 알고리즘 중 거스름돈 알고리즘을 이용한 간단한 문제이다. 가장 큰 금액부터 비교해가며 금액을 제외하고, 그 카운트를 출력해주어서 해결하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p11047 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

그리디 알고리즘을 이용하여 푸는 문제이다. 첫번째로 만난 행렬값이 다른 인덱스에서 부터 3*#크기의 값을 모두 바꾸어 주는 식으로 진행하면 된다. 처음에는 N*M에서 3보다 작은 부분이 남으면 그 부분만 바꾸어주어도 되는 줄 알아서 오답을 제출했는데 추후에 수정하여 맞았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p1080 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub B..

이 문제는 아이디어가 떠오르지 않아 다른 블로그들의 답을 보고 문제를 풀었다. 그리디 알고리즘은 구현 자체는 어렵지 않았지만 아이디어를 캐치하는게 어려운 것 같다. 이 문제에서 주의할 점은 + 기호로 split할 때 \\+를 이용해야 한다는점 이외에는 크게 어렵지 않게 구현할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class p1541 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new Buff..

탐욕법의 가장 대표적인 알고리즘으로 문제에 필요한 금액이 입력되면 가지고 있는 동전의 조합으로 해결하는 문제이다. 주어진 숫자 N을 충족하기 위해 동전의 배열에서 가장 큰 값부터 조건에 만족하면 추가하는 식으로 문제를 해결한다. public class coinChange { public static void main(String[] args) { // TODO Auto-generated method stub int N = 164; int ary[] = { 1, 5, 10, 50 }; int cnt = 0; for (int i = ary.length - 1; i >= 0; i--) { while (N > 0) { if (N >= ary[i]) { N -= ary[i]; cnt++; } else { brea..

그리디 알고리즘을 이용한 문제이다. 이러한 문제를 푸는 방식을 '활동 선택 문제'라고 한다. 활동 선택 문제에 대해 간략한 설명은 아래 링크를 참고하면 된다. https://ddamdoo.tistory.com/159 탐욕법 - 활동 선택 문제(Activity Selection Problem) 우리가 흔히 알고리즘에서 사용하는 탐욕법은 현재 위치에서 가장 최적의 해를 구해가는 과정을 연속해서 진행하는 문제이다. 이러한 문제 유형 중에는 활동 선택 문제가 있는데 이는 n개의 시 ddamdoo.tistory.com 이 문제를 활동 선택 문제로 풀게되면 먼저 종료시간 순으로 오름차순하고, 만약 종료시간이 같은 경우 시작시간을 기준으로 오름차순을 진행하여 해결하면 된다. import java.io.Buffered..