[그리디] 이코테 만들 수 없는 금액(Java)
📚 문제 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N=5이고 동전이 각각 3원, 2원, 1원, 9원짜리라고 가정합시다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 또 다른 예시로, N=3이고 동전이 각각 3원, 5원, 7원짜리라고 가정합시다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 target = 2 + 2 = 4로 업데이트한다. target = 4를 만족할 수 있는지 확인한다. 화폐 단위가 3인 동전이 있다. -> target = 4 + 3 = 7로 업데이트한다. target = 7을 만족할 수 있느닞 확인한다. 이보다 큰 화폐..
[동적 계획법] 이코테 금광(Java)
📚 문제 nxm 크기의 금광이 있다. 금광은 1x1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오. 만약 다음과 같이 3x4 크기의 금광이 존재한다고 가정한다면, (2,1) -> (3,2) -> (3,3) -> (3,4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값이다. 첫째 줄에 테스트 케이스 T가 입력된다. (1
09. 최단 경로 - 플로이드 위셜 알고리즘
플로이드 위셜 알고리즘이란? '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용 플로이드 위셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다. (모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문) 노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하여 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다. 각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. ex) 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다. 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1 개의 노드 중에서 서로 다른 노드 (..
[그래프 이론] 이코테 어두운 길(Java)
📚 문제 한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작..