알고리즘

문제 ✨ 문제의 개수 N(1

문제 ✨ N개의 여러 단위 동전이 주어질 때 거스름돈 M을 거슬러 줄 동전의 최소 개수를 구해라 Cf. 첫 번째 줄에는 동전 종류 수 N(1

문제 ✨ 풀이 ✨ 좌표(Point)를 저장하는 큐를 생성한다. 처음에 각 좌표의 값(0 또는 1 또는 -1)을 입력받을 때 1인 경우에는 미리 큐에 넣어두어 첫 날에 4방위를 토마토를 익게 하는 기준점들이 되게 한다. 상하좌우의 좌표를 확인하기 위해 y축에서 이동해야 하는 수와 x축에서 이동해야 하는 수를 크기가 4인 배열로 각각 만들어서 그 좌표가 1 ~ N 또는 1 ~ M의 크기이고, 그 값이 0이라면 1로 변화시킨다. 주의해야 할 점은, 검사한 좌표의 값이 -1일 경우에는 변화할 수 없으며 처음에 입력받을 때 좌표 값이 -1인 경우 1일 때와 같이 cnt를 올린다. 작성 코드 ✍️ import java.util.LinkedList; import java.util.Queue; import java.u..

주요 개념 ✨ 가중치 방향 그래프 방향을 지닌 그래프로, 각 edge에 가중치를 가진다. 다익스트라 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 알고리즘이다. 가중치 방향 그래프에서 다익스트라 알고리즘을 이용할 때는 간선의 가중치가 음수이면 안되는 점을 유의해야 한다. (0은 될 수 있다.) 문제 ✨ 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소비용을 출력하시오. (2번 정점부터 출력) 풀이 ✨ 메모이라이즈할 배열 변수를 두어 1부터 각 노드로의 거리비용을 저장한다. 해당 배열에 해당 노드의 거리비용 값이 있는 경우 새로운 값이 더 작을 때에만 그 값을 대체한다. 이 때 문제는 N개의 노드를 대상으로 각 노드로의 거리 비용을 구하기 위해서는 ${n}*{n}$만..

Priority Queue Java에서는 PriorityQueue라는 클래스를 그대로 사용하면 된다. 이진 트리로 구성되어 있어, $nlog(n)$의 시간만에 가장 우선순위가 높은 요소를 찾아준다. 이 때 우선순위는 그 값이 작을수록 높은 것이 기본이며, 반대로 큰 수가 곧 높은 우선순위로 여겨지려면 Collections.reverseOrder()을 인자로 전달한다. 예를 들어, 아래와 같이 일련의 수를 우선순위 큐에 넣는 경우를 보면 더욱 이해가 잘 될 것이다. PriorityQueue q = new PriorityQueue(); q.offer(7); q.offer(3); q.offer(1); q.offer(11); while (!q.isEmpty()) { System.out.print(q.poll()..

문제 ✨ 결혼식 피로연을 장소를 3일 동안 빌려 쉬지 않고 진행하려고 한다. 이에 참석하는 친구들 N명의 도착 시간과 떠날 시간을 전달받아 피로연 장소에 동시에 존재하는 최대 인원수를 구해 그 인원을 수용할 수 있는 장소를 빌리려 한다. 만약 도착 시간 13시이고 떠날 시간 15시라면, 이 친구는 13시에는 피로연 장소에 존재하나 15시에는 존재하지 않는다고 가정한다. 피로연장에 동시에 존재하는 최대 인원을 출력해야 한다. 피로연은 0시부터 72시까지 진행한다.) 풀이 ✨ 시간의 범위를 0부터 72까지 변화시키며(아래 코드에서는 정렬된 배열의 첫 번째 요소 - 친구 - 의 도착 시간을 출발값으로 정의) 당시의 시간과 출발 시간이 겹치는 친구가 있을 때에는 동시에 존재하는 인원(cnt)를 증가시키고, 당시..

문제 ✨ 한 개의 회의실과 이를 사용하고자 하는 n개의 회의들에 대해 회의실 사용표를 만들려고 한다. 각 회의는 시작시간과 끝나는 시간이 주어지고, 이를 통해 회의실을 사용할 수 있는 최대 수의 회의를 출력한다. (회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다른 회의가 시작될 수 있다. 또한, 회의시간은 0시부터 시작한다.) 풀이 ✨ 먼저 시작하는 것부터 선택하는 것이 아니라 빨리 끝나는 것 부터 선택해야 한다. 만약 끝나는 시간이 일치하는 경우에는 시작하는 시간으로 오름차열 정렬을 해야한다. 작성 코드 ✍️ import java.util.*; public class Main { static int cnt = 0; static int n; static Item[] lis..

그리디 알고리즘 순간 순간에 가장 최선이라고 여겨지는 선택을 하는 알고리즘을 뜻한다. 전반적인 결과도 최선이라는 보장을 할 수 없다. 문제 ✨ N명의 지원자의 키와 몸무게 정보를 입력받아 각 지원자가 다른 지원자와 일대일 비교해서 키와 몸무게 모두 높은 지원자가 존재할 경우에는 떨어트리고, 그렇지 않으면 선발한다고 했을 때 N명의 지원자가 주어지면 최대 몇 명의 선수를 선발할 수 있는지 출력한다. 풀이 ✨ 키와 몸무게 정보로 구성된 클래스를 생성한다. 두 가지 속성으로 비교하기 때문에 기본적으로 키를 기준으로 인스턴스들을 역순으로 정렬한 후 순서대로 해당 인스턴스의 몸무게가 여태까지 나온 최대 몸무게보다 클 때에만 탈락하지 않는다고 여긴다. 작성 코드 ✍️ import java.util.*; public..

문제 ✨ N x N 크기의 지도가 있고, 이는 1 x 1 크기의 격자칸으로 구성되어있다. 각 격자칸에 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 집의 피자배달거리는 해당 집과 도시에 존재하는 피자집들과의 거리 중 최소값을 해당 집의 피자배달거리라고 한다. M개의 피자집만 살리고 나머지는 폐업시킨다고 할 때, 도시의 피자배달거리 최소값을 구하라. (도시의 피자배달거리는 각 집의 피자배달거리를 합친 값이다.) 풀이 ✨ 인접 행렬을 구성하는 값들을 입력받을 때 피자 가게(2)들과 집(1)들을 리스트로 구성하고 피자 가게 리스트의 내부 요소들을 가지고 루프를 돌게 했다. 해당 순서의 피자 가게를 선택하는 경우(checked[idx] = true)와 그렇지 않은 경우(checked[idx] = fals..

문제 N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 만약 위와 같다면 섬의 개수는 5개입니다. 첫 번째 줄에 자연수 N(3