전체 글
-
[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] 부등호카테고리 없음 2020. 2. 4. 15:45
[2529] 부등호 https://www.acmicpc.net/problem/2529 부등호 기호 ''가 나열된 수열 A가 있다. 기호의 앞 뒤에 한 자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 이 때, 선택된 수는 모두 달라야 한다. k개의 부등호 관계룰 모두 만족시키는 (k+1)개 자리의 정수 중에서 최대값과 죄소값을 구하는 문제 Solution 순열을 사용한 문제해결 input : 2 입력으로 주어진 부등호가 ''이고 가장 큰 수를 구하는 경우를 생각해봤을 때 이 부등호에는 숫자가 총 3개 필요하기 때문에, 가장 큰 숫자인 9, 8, 7로 구성되는 것이 정답임을 알 수 있다. 반대로 가장 작은 수를 구하는 경우에는 0, 1, 2로 구성되는 것이 정답이 된다. 소스코드 impor..
-
[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..
-
SW 역량 테스트 준비 - 연습Algorithm/SWEA 2020. 2. 3. 15:39
1. 브루트 포스 1-1 브루트 포스 1-2 건너 뛰며 해보기 1-3 순열 사용하기 1-4 백트래킹 1-5 비트마스트 1-6 일부 경우만 해보기 1-7 중간에서 만나기 2. BFS 2-1 BFS 3. 다이나믹 프로그래밍 3-1 문제 풀이 1 3-2 문제 풀이 2 3-3 문제 풀이 3 1. 브루트 포스 리모컨 카잉 달력 수 이어 쓰기 1 부등호 단어 수학 스타트와 링크 맞춰봐 N-Queen 스도쿠 알파벳 종이 조각 가르침 구슬 탈출 2 2048 (Easy) 수들의 합 2 부분합 소수의 연속합 부분집합의 합 2 두 배열의 합 합이 0인 네 정수 2. BFS 숨바꼭질 4 DSLR 퍼즐 물통 숨바꼭질 2 탈옥 열쇠 로봇 청소기 레이저 통신 0과 1 점프 게임 3. 다이나믹 프로그래밍 이동하기 점프 팰린드롬? 1..
-
[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;..