baekjoon

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

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에 접근할 수 있는 방법을 찾으면 된다. 링 버퍼의 개념을 ..

입력받은 숫자 중 소수가 몇 개인지 찾아내는 문제이다. 기본적인 문제 풀이 개념은 다음과 같다. 어떠한 수를 n이라 하자. 만약 n이 소수라면 n의 제곱근 이하의 어떠한 수로도 나누어 떨어지지 않는다. 약수는 제곱근을 기준으로 대칭적인 성질을 갖기 때문이다. n까지의 소수를 모두 세는 방법은 O(n^2)의 시간 복잡도를 갖지만 이 규칙을 사용하면 O(nlogn)까지 줄일 수 있다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class primeNumber { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); //수 ..

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

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