밤이 블로그

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

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

BOJ#10164 격자상의 경로 * 문제https://www.acmicpc.net/problem/10164 * 풀이카카오 블라인드 채용 - 1차 테스트의 모의 테스트에 나온 문제와 유사합니다. 점화식은 간단하게 dp[row][col] = dp[row-1][col] + dp[row][col-1] 임을 알 수 있습니다. 단, K가 0이 아닌 경우 경유지가 1개 있는 것이므로이 경우 시작점->경유지, 경유지->도착점의 경우의 수를 각각 구한 뒤 곱해주면 원하는 답을 얻을 수 있습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/4cccafbf34e20c197249ac96c20b33f15e644bb1/BOJ%2310164/src/Main.java import java.i..

BOJ#1904 01타일 * 문제https://www.acmicpc.net/problem/1904 * 풀이수열은 끝이 1 또는 00인 2가지 경우로 나눌 수 있습니다.따라서 dp 점화식은 dp[i] = dp[i-1] + dp[i-2] * 나의 코드https://github.com/stack07142/BOJ/blob/a028fa1300ba4112e41be95b11d5daed4b71e8b8/BOJ%231904/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static final int MOD = 15746; static int[]..

BOJ#11051 이항 계수 2 * 문제https://www.acmicpc.net/problem/11051 * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311051/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int MOD = 10007; static int[][] dp = new int[1001][1001]; public static void main(String[] args) th..

BOJ#1915 가장 큰 정사각형 * 문제https://www.acmicpc.net/problem/1915 * 풀이카카오 모의 테스트에서 나온 문제와 동일합니다. 풀이 아이디어는 다음과 같습니다.검사 위치에서 인접한 3방향(위쪽, 왼쪽, 왼쪽위 대각선 )의 값을 검사하여검사 위치의 값을 최소값 + 1으로 갱신해줍니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231915/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class M..