Algorithm/BOJ
-
[BOJ] 숨바꼭질 4Algorithm/BOJ 2020. 2. 6. 21:49
[13913] 숨바꼭질 4 https://www.acmicpc.net/problem/13913 수빈이의 위치 : N 동생의 위치 : K 동생을 찾는 가장 빠른 시간과 이동하는 방법을 구하는 문제 수빈이가 할 수 있는 행동 (위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동 (1초) 2. 순간이동 : 2 * X로 이동 (1초) Solution BFS 풀이 방법 d[] 배열에 이전 위치를 기억 하면서 걷기, 순간 이동을 한다. 동생을 찾으면 K 위치에서 N 위치까지 역학적으로 경로를 path 리스트에 추가한다. 소스코드 import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanne..
-
[BOJ] 숨바꼭질 3Algorithm/BOJ 2020. 2. 5. 17:36
[13549] 숨바꼭질 3 https://www.acmicpc.net/problem/13549 수빈이의 위치 N 동생의 위치 K 동생을 찾는 가장 빠른 시간을 구하는 문제 수빈이가 할 수 있는 행동(위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동 (1초) 2. 순간이동 : 2 * X로 이동(0초) Solution 덱을 사용한 BFS 풀이 방법 걷기와 순간이동의 가중치(시간)가 다르기 때문에 덱을 사용해 순간 이동은 덱의 앞에, 걷기는 덱의 뒤에 넣는 방법도 생각해 볼 수 있다. 소스코드 import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public clas..
-
[BOJ] 스타트와 링크Algorithm/BOJ 2020. 2. 5. 14:14
[14889] 스타트와 링크 https://www.acmicpc.net/problem/14889 N명을 N/2명씩 두 팀으로 나누려고 한다. (4 = a[i]) i -= 1; if (i = a[j]) j -= 1; swap(a, i - 1, j); j = n - 1; while (i < j) { swap(a, i, j); i += 1; j -= 1; } return true; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public void print(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + "..
-
[BOJ] 단어 수학Algorithm/BOJ 2020. 2. 4. 19:11
[1339] 단어 수학 https://www.acmicpc.net/problem/1339 단어 수학은 0부터 9까지의 수를 알파벳 하나로 나타낸 것이다. N개의 간어를 수로 바꾼 다음에, 합의 최대값을 구하는 문제이다. (1 0 && a[i - 1] >= a[i]) i -= 1; if (i = a[j]) j -= 1; swap(a, i - 1, j); j = n - 1; while (i < j) { swap(a, i, j); i += 1; j -= 1; } return true; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args)..
-
[BOJ] 리모컨Algorithm/BOJ 2020. 2. 4. 12:45
[1107] 리모컨 https://www.acmicpc.net/problem/1107 TV 채널을 리모컨을 이용해 바꾸는 문제 버튼 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - 일부 숫자 버튼이 고장났다. 현재 보고 있는 채널 : 100 이동하려고 하는 채널 : N 이 때, 리모컨 버튼을 누르는 횟수를 최소로 하는 문제 Solution - Fail 처음에 생각 했던 방법은 내가 이동 가능한 버튼의 집합을 S라고 했을 때, 예를 들어 N이 5457이라면 S 집합의 숫자를 사용해 가능한 모든 네 자리 숫자를 만든다. // M 최악의 경우는 100에서 시작해서 +나 -로만 이동했을 때의 횟수로 초기화 한다. // answer = Math.abs(N-100) 그러면 모든 경우에 대해 ans..
-
[BOJ] 로또Algorithm/BOJ 2020. 2. 3. 15:23
[6603] 로또 집합 S와 k가 주어 졌을 때, 6개의 숫자를 고르는 모든 방법을 구하는 프로그램 Solution 다음 순열을 사용해서 구하는 방법과 재귀를 사용해서 구하는 방법을 생각했다. 다음 순열을 사용할 때는 크기가 k인 a[] 배열에 공을 고르는 경우인 0을 6개, 고르지 않는 경우인 1을 k-6 개 담았다. 그리고 next_permutation()을 돌리면서 a[] 배열의 요소가 0인 index를 집합 S에서 찾아 출력하였다. StringBuffer를 사용했더니 시간이 아주 많이 줄었다. 소스코드 - 순열 import java.util.Scanner; public class Main { public void go() { Scanner sc = new Scanner(System.in); whi..
-
[BOJ] 외판원 순회2Algorithm/BOJ 2020. 2. 3. 14:25
[10971] 외판원 순회2 https://www.acmicpc.net/problem/10971 영어로 Travelling Sales Problem (TSP) 1번 부터 N번까지 번호가 매겨져있는 도시가 있다. 한 도시에서 시작해 N개의 모든 도시를 거쳐 다시 원래 도시로 돌아오려고 한다. (한 번 갔던 도시로는 다시 갈 수 없다.) 이때, 가장 적은 비용을 구하는 문제 W[i][j] : i -> j 비용 Solution 0~N-1 까지 담고 있는 a[] 배열을 사용해 다음 순열을 구한다. W[i][j] 배열의 비용을 a[] 배열의 바뀌는 순서에 맞게 더해 최소 비용을 구한다. 소스코드 import java.util.Scanner; public class Main { int[][] w; public vo..
-
[BOJ] 차이를 최대로Algorithm/BOJ 2020. 2. 3. 13:21
[10819] 차이를 최대로 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 순열을 사용해서 문제를 풀 때는 모든 순서를 구했을 때 N! 가지가 나오기 때문에 시간 복잡도를 고려서 N = a[i]) { i -= 1;..