분류 전체보기

탐욕 법을 이용하여 풀이해야 하는 문제이다. 최대한 많이 회의실을 사용해야 하기 때문에 종료시간이 빠른 일정을 처리하는 게 유리하다. 그렇기 때문에, 입력을 종료시간을 우선으로 정렬하되 만약 종료시간이 같다면 시작시간이 이른 일정을 우선으로 정렬한다. 그 후, 차례로 비교해가며 종료시간이 가장 빠른 일정을 우선으로 처리하면서, 그 일정의 종료시간보다 크거나 같은 일정을 다음 일정으로 처리하며 나가면 된다. 다음은 Java로 작성한 코드이다. import java.util.PriorityQueue; import java.util.Scanner; public class MeetingRoom { public static void main(String[] args) { //Pair class 정의 class P..

오랜만에 DP 문제를 풀어보았다. 정수 삼각형을 입력받아 저장한 뒤, 최종적으로 가장 큰 수를 만들어 가는 문제이다. 단, 선택할 수는 다음행의 수 중, 왼쪽, 오른쪽 둘 중 하나만 선택 가능하다. 즉, 7에서 선택할 수 있는 수는 3, 8 둘 중 하나이다. 이런 방식으로 하나씩 더해 나가 가장 큰 수를 만들면 된다. 얼핏 보면, 선택할 수 있는 수 중에 큰 수를 선택해서 진행하면 되는 탐욕 법 문제로 볼 수 있다. 하지만, 그 다음 상황은 모르기 때문에 탐욕 법은 항상 올바른 답을 주지 않는다. 따라서, 동적 계획법을 이용하여 답을 구해내면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class Triangle { public static voi..

우선적으로 y를 기준으로 정렬하고 같다면 x를 기준으로 정렬하는 문제이다. 좌표를 저장할 때, 이차원 배열에 저장할까, x배열, y배열을 이용하여 index로 관리할까 고민해 봤지만, Pair라는 class를 정의해 문제를 풀면 간단할 거라고 생각이 들었다. Pair라는 클래스를 정의하는데 Comparable interface를 구현하게 만들어 우선순위 큐를 이용하여 출력한다면, 한번에 문제를 풀 수 있다. 다음은 Java로 작성한 코드이다. import java.util.PriorityQueue; import java.util.Scanner; public class Coordinate { public static void main(String[] args) { //Pair class 정의 class P..

동전의 종류와 목표금액을 입력받은 뒤 동전들을 이용하여 가장 적은 수의 동전으로 목표금액을 만드는 문제이다. 동전의 종류에 따라 무엇을 선택하는지에 따라 개수가 달라지지만, 이런 문제에는 항상 탐욕법이 정답이 되지는 않는다. 하지만, 이 예제는 그러한 상황은 배제한 문제인 것 같다. 문제 풀이는 간단하다. 목표금액과 동일하거나 넘지 않는 동전 중 가장 큰 동전을 선택하여 목표금액을 줄여 나가면 되는 문제이다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class Coin { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int count = 0; int n ..

대기 인원을 입력받고 각 인원들의 대기 시간을 최소한으로 만드는 문제이다. 생각해보면 간단한 문제이다. 대기시간의 합을 최소한으로 만들기 위해서는 자신의 앞사람들의 인출하는데 필요한 시간이 적게 만들면 된다. 즉, 시간이 적게 걸리는 사람들을 우선으로 처리하면 된다. 운영체제에서 배웠던 스케줄링 방식 중, SJF(Shortest Job First)방식을 떠올릴 수 있다. 입력을 받을 때, 우선순위 큐를 이용하여 저장한 뒤 하나씩 out 시키며 배열에 저장한다. 그러면 시간이 적은 순서대로 배열에 저장 할 수 있다. 그 후, 마지막 요소부터 자신 전까지의 요소를 모두 더해나가면 답을 구해낼 수 있다. 다음은 Java로 작성한 코드이다. import java.util.PriorityQueue; import ..

자연수 N을 입력받아 자연수 안에서 각 자릿수를 내림차순으로 정렬하는 문제이다. 우선 각 자리수로 수를 나누어 크기 순으로 정렬한 뒤 다시 합치면 된다. 다음은 Java로 작성한 코드이다. import java.util.Collections; import java.util.PriorityQueue; import java.util.Scanner; public class SortInside { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //역전된 우선 순위 큐 PriorityQueue solution = new PriorityQueue(Collections.rev..

플로이드 알고리즘을 이용하여 최단거리를 구해내는 문제이다. 입력받는 값들은 도시의 개수, 버스의 개수, 버스의 시작, 도착, 가중치이다. 최단 거리를 구하기 위해서는 입력받을 때부터 시작 노드와 도착 노드가 동일한 노드 중 가중치가 작은 노드를 택해서 입력받아 저장해야 한다. 따라서 입력받을때 비교하여 인접 행렬을 만들어야 한다. 인접 행렬을 만든 다음에는 직접 연결되어 방문이 가능한 노드는 플로이드 알고리즘을 이용하여 최솟값을 찾아 나가고 직접 연결이 되어 있지 않은 노드는 다른 노드를 거쳐 이동하게 하여야 한다. 하지만, 이 때, 인접 행렬에서 0인 노드로는 접근이 아예 불가능하기 때문에, 이를 고려하여 알고리즘을 작성해야 한다. 다음은 Java로 작성한 코드이다. import java.util.Sc..

플루이드-워셜 알고리즘의 원리를 이용하여 정답을 구해내는 문제이다. 입력값으로 N개의 도시와 미리 계산해놓은 최솟값들을 입력받기 때문에 플루이드-워셜 알고리즘을 역으로 돌리며 인접 행렬을 구해내면 문제를 풀어낼 수 있다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class RoadSum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[][] map = new int[n][n]; int[][] adj = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = ..

플루이드 - 워셜 알고리즘(Floyd - Warshall algorithm) 플루이드-워셜 알고리즘은 최단 경로를 구하는 또 하나의 알고리즘이다. 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 구할 수 있다. 인접 행렬을 이용하여 초기값을 설정한다. 가중치를 포함한 인접 행렬이 다음과 같다고 하자. 이 인접 행렬을 이용해서 다음과 같은 초기값을 만든다. 자신에서부터 자신까지의 거리는 항상 0이며, 직접 연결되어 있지 않은 경우에는 ∞로 초기화 한다. 초기값을 설정한 후에는 n번째 노드부터 중간 노드가 되어, 중간 노드를 거쳐 다른 노드로 갈 수 있는 값들을 업데이트시킨다. n번 반복하면 모든 노드까지의 최단 거리를 알 수 있다. 다음은 Java로 작성한 코드이다. public class Flo..

섬의 크기를 입력받고, map을 입력받은 뒤, 1은 섬, 0 은 바다라 가정한다. 섬에서는 상, 하, 좌, 우, 네방향의 대각선을 포함하여 총 8가지의 이동경로를 가질 수 있다. 하지만, 바다인 경우에는 움직일 수 없다. 즉, 0, 0 위치부터 섬을 찾은 후, 움직일 수 있는 위치까지 모두 방문한 뒤 방문 여부를 기록하면 섬을 중복하여 셀 경우를 피할 수 있고, 방문하지 않은 섬을 새로 발견할 경우 같은 방식으로 진행하면 지도의 모든 섬의 수를 셀 수 있다. 섬을 발견한 경우 깊이 우선 탐색을 이용하여, 갈 수 있는 모든 섬을 방문한 뒤 기록하는 방식으로 문제를 푸는 것이다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.Scanner..