밤이 블로그

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가 되고 아래와 같이 두..

카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java) 이 문제는 n이 5000이므로 O(N^2)으로 풀어야 합니다.N^3으로 풀 수 있습니다만,, 최적화 과정이 들어가야 통과됩니다. 문제 출제 목적에 맞게 O(N^2)으로 푸셔야 맞습니다. (문제는 프로그래머스에서 다시 풀 수 있습니다.) O(N^2)의 해법은 다음과 같습니다. 1. 세그먼트 트리 개념과 비슷하게 주어진 범위의 직사각형 내부에 쐐기가 몇개 있는지를 먼저 구해놓습니다. -> O(N^2) S[i][j] : (0, 0) ~ (i, j) 범위의 직사각형 내부에 존재하는 쐐기의 개수 2) 그리고 모든 쐐기의 쌍에 대하여 -> O(N^2) 미리 구해놓은 S 배열의 값을 검사하여값이 0인 경우 (내부에 쐐기가 없음) 텐트를 설치할 수 있음을 쉽게..

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..