Algorithm
-
[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;..
-
[BOJ] 다음 순열, 이전 순열Algorithm/BOJ 2020. 2. 3. 13:16
순열(Permutation) 크기가 N인 수열은 총 N!개가 존재한다. 순열을 사전 순으로 나열했을 때, 첫 번째 순열은 오름차순, 마지막 순열은 내림차순이다. N = 3인 경우에 사전순은 다음과 같다. 123 132 213 231 312 321 [10972] 다음 순열 https://www.acmicpc.net/problem/10972 1. A[j-1] = i이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다. 3. A[j-1]과 A[j]를 swap 한다. 4. A[j]부터 순열을 뒤집는다. 소스코드 import java.util.Scanner; public class Main { public void go() { Scanner sc..
-
[BOJ] N과 M (1) ~ (8)Algorithm/BOJ 2020. 2. 2. 23:00
https://www.acmicpc.net/search#q=n%EA%B3%BC%20m&c=Problems [15649] N과 M (1) - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 input 4 2 output 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 소스코드 import java.util.Scanner; public class Main { // main function make_permutation(0, n, m); public void make_permutation(int idx, int n, int m) { if (idx == m) { print(a, m); return; } for (int i = 1; i
-
SW 역량 테스트 준비 - 기초Algorithm/SWEA 2020. 1. 6. 12:57
1. 수학 1-1. 수학 2. 브루트 포스 2-1. 브루트 포스 2-2 N중 for문 2-3. 순열 2-4. 재귀 함수 사용하기 2-5. 비트마스크 3. 브루트 포스 - N과M 3-1. N과 M 4. 그래프와 BFS 4-1. 그래프 4-2. 그래프의 탐색(DFS, BFS) 4-3. 플러그 필 4-4. BFS 4-5. 덱 사용하기 4-6. BFS 2 5. 다이나믹 프로그래밍 5-1. 다이나믹 프로그래밍 5-2. 다이나믹 프로그래밍 문제 풀이 - 1 5-3. 다이나믹 프로그래밍 문제 풀이 - 2 5-4. 다이나믹 프로그래밍 문제 풀이 - 3 5-5. 다이나믹 프로그래밍 문제 풀이 - 4 1. 수학 나머지 최대공약수와 최소공배수 최소공배수 GCD 합 소수 찾기 골드바흐의 추측 2. 브루트 포스 일곱 난쟁이 날..