밤이 블로그

BOJ#1509 팰린드롬 분할 * 문제https://www.acmicpc.net/problem/1509 * 풀이- Manacher 알고리즘을 통해 임의의 범위의 문자열이 팰린드롬인지 구한다. - dp[i] : 0 ~ i 범위의 문자열을 팰린드롬 분할할 때 최소 분할 수 j ~ i 범위 문자열이 팰린드롬일 때, dp[i] = min(dp[i], dp[j-1] + 1)(여기서 j는 0 부터 i 까지) dp[0] = 1이고 -> dp[1] -> dp[2] -> ... -> dp[N-1]을 차례대로 구한다 * 나의 코드https://github.com/stack07142/BOJ/blob/d4b527b666ba54f7f53c1128f5a1523cb261d2b9/BOJ%231509/src/Main.java impo..

BOJ#13706 제곱근 * 문제https://www.acmicpc.net/problem/13706 * 풀이 이분 탐색, BigInteger 사용 * 나의 코드https://github.com/stack07142/BOJ/blob/bcbfa3899c5c3acae75e515c8642eddcb3a9067e/BOJ%2313706/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { public static void main(String[] args) throws IOException { B..

BOJ#3019 테트리스 * 문제https://www.acmicpc.net/problem/3019 * 풀이- 게임 규칙 : 블럭이 떨어졌을 때, 블럭과 바닥 사이에 채워져있지 않은 칸이 생기면 안된다. - 풀이 방법 : 바닥 높이가 주어지고 블럭의 높이도 알 수 있으므로, 두 정보를 이용하면 빈 칸이 생기는지 알 수 있다. , 평평한 바닥에 블럭을 놓았을 때 다음과 같이 블럭의 높이를 표현할 수 있습니다. ㅗ -> "000"ㅓ -> "10"ㅏ -> "01"ㅜ -> "101" , 두 가지 경우를 그려보았습니다. 블럭 : "10"블럭이 높이 1인 바닥에 놓여졌으므로 "10" -> "21" 블럭과 바닥 사이에 빈 칸이 있는가? = 각 col에 대해 블럭과 바닥 높이의 차이가 일정한지 검사 2 - 1 != 1 ..

BOJ#4920 테트리스 게임 * 문제https://www.acmicpc.net/problem/4920 이전에 풀어봤던 14500번 테트로미노(삼성 기출)와 비슷한 문제입니다. * 풀이14500번의 경우 (ㅓ, ㅏ, ㅗ, ㅜ)를 제외하고 다른 모양은 전부 dfs로 탐색이 가능했지만,4920번의 경우 위 경우 이외에도 dfs로 탐색이 불가능한 경우가 있습니다. (예 : ㄱ 등등) 따라서 dfs 탐색을 사용하지 않고 패턴을 미리 정해놓은 후 매칭시키는 방법으로 시뮬레이션 하였습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/f0d9bf85e203ff075cbf53506fb38d625f5115a3/BOJ%234920/src/Main.java import java.io...

BOJ#1300 K번째 수 * 문제https://www.acmicpc.net/problem/1300 * 풀이- N이 10^5일 때, N*N은 10,000,000,000 이므로 시뮬레이션하여 답을 구하는 것은 시간 내에 불가능합니다.- 문제를 해결하기 위한 아이디어는 다음과 같습니다. 1. 어떤 수 x가 있을 때, x-1 이하의 수의 개수가 K개 미만이고 x 이하의 수의 개수가 K개 이상인 경우우리가 찾는 K번째 수는 x 이다. 2. 즉, x는 x 이하의 수의 개수가 K개 이상이면서 가장 작은 수이다. 3. 위 조건을 만족하는 x를 이분 탐색을 통해 찾는다. , 그러면 x까지 수의 개수는 어떻게 찾을 수 있을까요? - N이 4일 때 1 2 3 42 4 6 83 6 8 124 8 12 16 i번째 행은 i의..

BOJ#3653 영화 수집 * 문제https://www.acmicpc.net/problem/3653 * 풀이저는 팬윅 트리를 완전히 마스터하지 못해서이 문제를 세그먼트 트리를 이용해서 풀었습니다. 따라서 코드가 상당히 길고 최적화된 솔루션이 아닙니다. 다음에 기회가 되면 팬윅 트리를 이용해서 다시 풀어보도록 하겠습니다. , 3 3 3 1 1답 : 2 1 0 위 예제를 보면 일단 최초에는 아래와 같이 영화가 쌓여 있을 것입니다.[1번 영화, 2번 영화, 3번 영화] 문제를 쉽게 풀기 위해서 위 배열을 다음과 같이 변형해봅시다.사이즈를 n에서 n+m으로 늘렸습니다.[0, 0, 0, 1, 2, 3] 1) 3번 영화를 꺼낼 때, 앞에 영화 2개가 쌓여있다[0, 0, 0, 1, 2, 3] -> [0, 0, 3, ..

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#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] 그리고 정점을 각 층이 아닌 엘리베이터로 정하였..