밤이 블로그

BOJ#2352 반도체 설계 * 문제https://www.acmicpc.net/problem/2352 * 풀이 LIS 기본 문제입니다. LIS 설명http://stack07142.tistory.com/56 비슷한 문제들http://stack07142.tistory.com/102http://stack07142.tistory.com/103http://stack07142.tistory.com/287 * 나의 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Mai..

BOJ#1495 기타리스트 * 문제https://www.acmicpc.net/problem/1495 * 풀이dp[idx][volume] : N번째 곡일때, volume 가능 여부(boolean) * 나의 코드https://github.com/stack07142/BOJ/blob/b5664bd70b97831cf6d21fa7d0c37919da9508ce/BOJ%231495/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, S, M; static int..

BOJ#1613 역사 * 문제https://www.acmicpc.net/problem/1613 * 풀이플로이드 와셜 알고리즘에 따라 Start -> 임의의 노드 -> End를 만족하는 임의의 노드가 존재할 때 (자기 자신을 포함하여) Start -> End 를 만족함을 알 수 있습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/644019c1ecb2b486c6597f4c2570edae8f97760f/BOJ%231613/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..

BOJ#2824 최대공약수 * 문제https://www.acmicpc.net/problem/2824 * 해설두가지 방법으로 풀어보았습니다. 1. BigInteger를 이용 2. A와 B를 다음과 같이 표현할 수 있습니다. 예를 들어 A = 30, B = 20일 때A = 2^(1) * 3^(1) * 5^(1)B = 2^(2) * 5^(1) 최대공약수는 위에서 볼 수 있듯이 gcd = 2^(min) * 5^(min) = 2^(1) * 5^(1) * 나의 코드 BigInteger를 이용한 풀이BigInteger a = BigInteger.valueOf(1); BigInteger b = BigInteger.valueOf(1); BufferedReader br = new BufferedReader(new Inpu..

BOJ#2593 엘리베이터 * 문제https://www.acmicpc.net/problem/2593 * 풀이다익스트라를 이용해서 풀었습니다. 처음에 그래프 모델링에서 당황했는데 아래와 같이 해보았습니다.문제에 나와있는 예제에서 ArrayList elevator = new ArrayList();elevator : 각 엘리베이터에서 갈 수 있는 층 엘리베이터 1번 : [4, 7, 10]엘리베이터 2번 : [7, 12]엘리베이터 3번 : [4, 8, 12] ArrayList floor = new ArrayList();floor : 각 층에서 탈 수 있는 엘리베이터 4층 : [1, 3]7층 : [1, 2]8층 : [ 3 ]10층 : [ 1 ]12층 : [2, 3] 그리고 정점을 각 층이 아닌 엘리베이터로 정하였..

BOJ#14391 종이 조각 * 문제https://www.acmicpc.net/problem/14391 * 풀이모든 경우의 수를 다 따져보아야 합니다.각 조각은 가로 또는 세로이므로 2^(N*M)의 경우의 수가 있습니다. 문제 풀이에 비트마스크를 이용하였습니다. 예를 들어, 3x3 종이에서 아래와 같은 경우라면 1 1 01 1 01 0 1 -> 1 1 0 1 1 0 1 0 1 으로 표현할 수 있습니다. 즉, 0 0 0 0 0 0 0 0 0 부터 1 1 1 1 1 1 1 1 1 까지모든 경우의 수는 아래와 같이 뽑아낼 수 있습니다. // 모든 경우를 다 해보기 : 2^NM for (int state = 0; state < (1

BOJ#10972 다음 순열 * 문제https://www.acmicpc.net/problem/10972 * 풀이 순열 설명http://stack07142.tistory.com/24 순열 설명(사전순)http://stack07142.tistory.com/155 쉬운 것 같으면서도 어려운 문제였습니다.문제 해결 알고리즘은 다음과 같습니다. 위 순열 설명 링크와 순열 설명(사전순) 링크를 다 읽으셨다는 가정 하에 설명해보겠습니다. , A = [1, 3, 4, 2] 주어진 순열의 끝을 idx로 지정하고, A[idx-1] 0 && A[idx - 1] > A[idx]) idx--; idx는 2가 되고 아래와 같이 두..

BOJ#11723 집합 * 문제https://www.acmicpc.net/problem/11723 * 풀이매우 쉬운 문제이지만 시간 제한과 메모리 제한을 모두 생각해야 합니다. 저는 비트마스크를 사용하여 풀어보았습니다.아니면 배열을 사용해서도 쉽게 풀 수 있습니다. * 나의 코드 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWri..

BOJ#2631 줄세우기 * 문제https://www.acmicpc.net/problem/2631 * 풀이일단 [4, 1, 2, 3, 5]인 경우의 문제를 손으로 풀어봅시다.거의 대부분 4를 3뒤로 옮겨서 한번만에 문제를 푸셨을 것입니다. 위 과정을 조금 더 상세하게 써보면 1. 수열에서 증가하는 가장 긴 부분 수열을 구하고 (이것들은 움직이지 않음)[4, 1, 2, 3, 5] 나머지 숫자를 적절한 자리로 이동시키면 옮겨지는 아이의 수를 최소로 하면서 줄을 세울 수 있습니다.[4, 1, 2, 3, 5] -> [1, 2, 3, 4, 5] 여기서 우리는 횟수만 구하면 되므로전체 길이 - LIS(Longest Increasing Subsequence) 길이 = 아이의 최소 이동 횟수 = 원하는 답 저는 LIS..

BOJ#2014 소수의 곱 * 문제https://www.acmicpc.net/problem/2014 * 풀이어려운 문제입니다. K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자.예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다. 즉, 주어진 소수가 [2, 5, 7]일 때2, 5, 7만을 약수로 갖는 숫자들 중 N 번째 숫자를 구하여라. 이 문제는 다음과 같은 알고리즘으로 해결을 할 수 있습니다. 1. 주어진 소수를 배열에 저장한다. 2. 주어진 소수를 PriorityQueue에 add 한다. 3. 아래 과정을 N-1 번 반복(loop) - Prio..