스파르타 알고리즘 트랙 문제(백준)/6일차 (3) 썸네일형 리스트형 스파르타 알고리즘 트랙 문제 6일차 - 3 #11047 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 해결 과정 DFS를 구현한 후 그리디 서치를 해야겠다는 생각을 했으나, 문제의 동전 조건이 1부터 시작하여 배수로 증가하는 배열이기에 금액이 큰 동전부터 고려한다면 큰 문제없이 해결할 수 있는 문제가 되었다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int .. 스파르타 알고리즘 트랙 문제 6일차 - 2 #1037 약수 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 해결 과정 1과 자기 자신을 제외한 모든 약수가 주어질 때, N을 구하는 것은 모든 약수 집합 중, 최댓값과 최솟값을 곱하면 간단히 값을 구할 수 있다. 인수분해 시 소수의 제곱 형태의 정수 N은 1과 자기 자신을 제외한 모든 약수의 갯수는 1개이기에 해당 수를 제곱하여야 하나, 최댓값과 최솟값이 동일한 약수 집합으로 생각하면 위 과정과 동일함을 알 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args).. 스파르타 알고리즘 트랙 문제 6일차 - 1 #1927 최소 힙 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 해결 과정 최대 힙 문제에서 힙의 정렬 순서를 값이 가장 작을 때로 변경한 것과 동일하다. 최대 힙 문제와 동일하게 Priority Queue를 사용하되, reverseOrder 구문만 제거해 정순으로 정렬되게 하였다. 그 외에는 최대 힙 문제와 동일한 알고리즘을 구현하였다. import java.io.*; import java.util.*; public class Main { public static void main(String[] ar.. 이전 1 다음