algorithm

우선적으로 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 ..

자연수 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..

다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘(Dijkstra's algorithm)은 벨만-포드 알고리즘처럼 특정한 노드에서 시작하여 그래프의 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라는 벨만-포드 알고리즘에 비해 좀 더 효율적이기 때문에 그래프가 큰 경우에도 사용할 수 있다는 장점이 있다. 하지만, 이 알고리즘은 음수인 가중치를 가진 간선이 있는 경우에는 사용할 수 없다는 단점이 있다. 다익스트라 알고리즘도 벨만-포드 알고리즘처럼 각 노드까지의 거리를 저장하고 탐색 과정에서 값을 줄여나간다. 각 단계에서는 아직 처리하지 않는 노드 중 거리가 가장 작은 노드를 찾고, 그 노드에서 시작하는 모든 간선을 쭉 살펴보며 노드까지의 거리를 줄일 수 있다면 줄인..

동적 계획법의 예제이다. 우선, 몇 개의 정수를 처리할지 입력받은 후 입력받은 개수만큼의 입력을 받는다. 그 후, 입력받은 수들을 1, 2, 3의 합으로만 나타내는 방법의 총 개수를 구하는 문제이다. 예를 들어 4는 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1로 총 7개이다. 규칙은 간단하다. 1과 2 그리고 3을 선택한다는 가정을하면 만들려는 수에서 선택한 수를 뺀 수를 만드는 경우의 수를 모두 더하면 되는 것이다. 1을 먼저 선택한 경우 1 + 3을 만드는 경우( 1+1+1, 1+2, 2+1, 3) => 4가지 2를 먼저 선택한 경우 2 + 2를 만드는 경우( 1+1, 2) => 2가지 3을 먼저 선택한 경우 3+ 1을 만드는 경우( 1 ) => 1가지 모두 더하면 ..

입력받은 수를 3으로 나누기, 2로 나누기, 1 빼기 이 세 가지 연산을 이용하여 1로 만드는 최소의 연산 횟수를 구하는 문제이다. 얼핏 보면, 3으로 나누는 연산이 가장 수를 많이 줄여주니까 3으로 나누고, 3으로 나누지 못하면 2로 나누고, 그러지 못하면 1을 빼는 식으로 구할 수 있는 간단한 문제인 것 같이 보인다. 하지만 이것은 탐욕 법으로 계산하는 방법이며, 항상 최적해를 구할 수 없다. 예를 들어, 10을 1로 만드는 방법을 탐욕법으로 구한다면 10 -> 5 -> 4 -> 3 -> 1으로 총 4회의 연산이 필요하다. 하지만, 동적 계획법으로 연산을 하면 10 -> 9 -> 3 -> 1 로 총 3회의 연산만으로 1로 만들 수 있다. 따라서, 모든 경우의 수를 살펴 보아야 한다. import ja..