algorithm

그래프 탐색의 기본인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하는 문제를 풀어보았다. 예전에 공부해서 잘 할 수 있으려나 하고 생각했는데 생각보다 잘 풀렸다. 역시 기본 개념을 이해하고 있다면 구현하기 쉬운 거 같다. DFS에서는 재귀를 이용한다는 점을 알고 구현하니 훨씬 순조로웠다. 또한 BFS에서 Queue를 사용한다는 키포인트를 알고있었기 때문에 쉽게 문제를 풀 수 있었다. DFS에서는 방문하지 않은 노드일 경우 출력을 하고, 해당 노드에서 갈 수 있는 노드를 하나씩 dfs()를 이용하여 재귀시키면 간단하게 풀린다. 그렇게 재귀 호출되어 탐색을 시작한 노드에서도 똑같은 작업을 수행하기 때문에 최대한 탐색할 수 있는 노드까지 최대한 순회한 뒤 반환되어 나머지 노드를 순회한다. BFS..

지난 포스트에 풀었던 다익스트라 알고리즘을 다른 문제로 다시 풀어 보았다. 저번의 실수를 만회하기위해 어제 틀린 부분을 집중해서 풀어보았다. 1트만에 맞았다 ㅎㅎㅎㅎ 0.5초라 시간 초과가 뜨지 않을까 했는데 다행히 뜨지 않았다. 지난 포스트에서는 모든 노드까지의 최단거리를 구하는 것인데 이번 문제는 그냥 도착 노드까지의 최소 비용만 구하면 된다. 즉, 도착 노드의 최소 비용만 출력하면 된다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class MinimumCost { public static void main(String[] args) { //..

다익스트라 알고리즘을 복습하기 위해 문제 카테고리에서 제일 첫 번째에 위치한 문제를 풀러 들어갔다. 처음에는 다익스트라만 적용하면 간단하게 풀릴 문제라고 생각했다. 하지만...... 오만했던 나를 발견했다..... 거의 하루를 쏟아 부었다..... 몇 틀을 한 건지 모르겠다..... 15트만에 드디어 풀었다. 중간에 맞은 문제는 구글에 돌아다니는 코드를 붙여 넣어 봤다. 내 코드만 안 되는 줄 알고.... 점심 나가버릴 거 같았다.... 문제풀이는 간단했다. 노드의 수와 간선의 수, 시작 노드를 입력받고 간선들의 시작점, 도착점, 가중치를 입력받아 시작 노드에서 다른 노드들까지의 최단거리를 구하면 되는 문제이다. 나는 다익스트라 알고리즘을 이용하여 최단 경로를 구하려 했다. 다익스트라 알고리즘은 아직 방..

DP 제일 위에 있는 문제를 풀어보았다. 3kg과 5kg의 설탕으로 목표 무게를 만드는 것이다. 만들지 못하면 -1을 만들 수 있으면, 최소한의 수의 설탕으로 목표 무게를 만드는 것이다. 메모제이션을 이용하여 0부터 목표 무게까지 최소한의 수를 쌓아가면 된다. 0 = -1 1 = -1 2 = -1 3 = 1 4 = -1 5 = 1 은 기저 조건으로 설정한다. 만약 기저 조건보다 낮은 목표 무게가 있다면 예외 처리를 한다. 그리고, 이제 무게를 6부터 쌓아갈 때 3을 뺀 수와 5를 뺀 무게 중, 적은 수의 설탕 봉지를 쓴 경우를 택해 1을 더하면 된다. 또한, 15같은 무게는 3kg으로도 5kg으로도 만들 수 있다. 이런 경우를 생각해 3kg을 쓴 경우와 5kg을 쓴 경우 모두를 생각해 비교해야 한다. 다..

최대공약수와 최소공배수를 구하는 문제이다. 선형적인 탐색법으로 작은 수전까지 하나씩 나누어 보고 둘 다 나누어 떨어지는 수 중 가장 큰 수를 구하면 되겠지만, 다른 수학적인 방법을 이용하여 최대공약수를 구한 뒤 그를 이용하여 최소 공배수까지 구하는 방법이 있다. 임의의 수 a, b가 있다 가정하자. (단, a > b) a를 b로 나누면 몫과 나머지가 있을 것이다. 그러면 그 나머지로 나누는 수 (b)를 또 나눈다. 이를 반복하다 나누는 수 (b)가 0이 되면 나누어지는 수 a를 return 한다. 그림을 보면 x가 최대공약수라 할 때, a = 8x b = 3x a% b = 2x이다. 우리는 x를 구해야 하기 때문에, 나머지가 0이 될 때, 즉 모든 수가 나누어 떨어질 때까지 계속해서 b를 나머지로 나눈다..

DP문제에 전형적인 풀이 방법인 메모제이션을 이용하여 문제를 풀었다. 처음에는 어떤 식으로 문제를 풀어 나가야 할지 감이 잡히지 않았다. 계속 생각한 결과 한가지만 주의하면 된다는 생각을 하게 되었다. 이웃한 집만 같은 색깔이 아니면 되기 때문에 하나의 집을 임의의 색으로 칠하면 다음 집에서는 선택할 수 있는 경우가 2가지로 좁혀지고, 그다음은 여전히 2가지의 선택의 경우가 생긴다. 즉, 소모 값들을 배열에 저장한다 생각하면, 같은 column에 있는 값만 선택하지 않으면 된다. 그렇다면 이제 index문제만 해결하면 문제는 풀린다. R은 [0]에, G는 [1]에, B는 [2]에 저장한다 하자. 2번 index의 요소를 처리한다 했을때, 0과 1에 접근할 수 있는 방법을 찾으면 된다. 링 버퍼의 개념을 ..

초등학교 수학 문제에서 많이 봤던 문제이다. 낮에 이동하고 밤에 미끄러지기 때문에 낮에 이동했을 때 목표 거리와 비교한 뒤 만족하지 않았다면 미끄러진 높이를 계산하는 계산을 반복하면 되는 문제라고 생각했다. 하지만 결과는 시간 초과... 그래서 다음엔 배열을 이용해 봤다. 배열일 연산이 제일 빠르기 때문에 시간 초과 문제를 해결할 거라 생각했다. 낮에 이동한 거리의 배열과 미끄러진 후의 거리 배열을 생성하여 낮에 이동한 거리가 목표 높이에 도달하기까지 반복하여 index를 출력하면 될 줄 알았다. 하지만 이번에는 메모리 초과.... 한참 고민하다 해답이 떠올랐다. 결국 마지막에는 앞으로 이동을 해야 하기 때문에, 앞으로 가는 거리를 목표 높이에서 뺀 뒤 실제로 이동하는 거리(앞 - 뒤)로 나누어 주면 정..

연속되는 수 중 가장 큰 합을 찾아내는 문제이다. DP로 간단하게 해결 가능하다 배열에 수들을 저장해 해당하는 index의 수가 선택되었을 경우, 이전까지의 합과 index의 요소 중 큰 수를 골라 저장하며 풀어 나간 뒤 가장 큰 수를 찾아 출력하면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class continuitySum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //수 배열 int[] arr = new int[num]; //큰 수 저장 배열 int[] solution = new int[num..

탐욕 법을 이용하여 풀이해야 하는 문제이다. 최대한 많이 회의실을 사용해야 하기 때문에 종료시간이 빠른 일정을 처리하는 게 유리하다. 그렇기 때문에, 입력을 종료시간을 우선으로 정렬하되 만약 종료시간이 같다면 시작시간이 이른 일정을 우선으로 정렬한다. 그 후, 차례로 비교해가며 종료시간이 가장 빠른 일정을 우선으로 처리하면서, 그 일정의 종료시간보다 크거나 같은 일정을 다음 일정으로 처리하며 나가면 된다. 다음은 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..