밤이 블로그

* 문제 https://www.acmicpc.net/problem/1003 * 풀이https://github.com/stack07142/BOJ/blob/master/BOJ%231003_FibonacciCount/src/Main.kt var dp = Array(41) { Node() } fun main(args: Array) { var T = readLine()!!.toInt() while (T-- > 0) { val N = readLine()!!.toInt() fibonacci(N) println("${dp[N].count0} ${dp[N].count1}") } } fun fibonacci(n: Int): Node { if (dp[n].num != -1) { return dp[n] } when (n) {..

BOJ#5670 휴대폰 자판 * 문제https://www.acmicpc.net/problem/5670 * 풀이카카오 블라인드 채용 - 3차 코딩테스트 5번 문제와 유사합니다. Trie를 사용하여 풀어보았습니다. 1. 모든 문자열을 Trie에 저장한 후2. child의 개수가 2 이상인 경우, terminal 노드인데 child가 존재하는 경우를 카운트하였습니다. 부족한 점이 있으면 댓글로 알려주세요. 감사합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/a3f55a12084c8b798e96dd86eedbdc8661595777/BOJ%235670/src/Main.java import java.io.BufferedReader; import java.io.IOExcep..

BOJ#5052 전화번호 목록 * 문제https://www.acmicpc.net/problem/5052 * 풀이저는 이 문제를 Trie를 이용해서 풀어보았습니다. Trie를 처음 공부하고 풀어보는 것이라서 부족한점이 있을 것 같습니다. 댓글로 알려주시면 감사하겠습니다. , 1. 일단 전화번호 목록을 배열에 저장한 후 정렬을 진행합니다.2. Trie 자료구조에 Insert합니다.3. 이 과정에서 terminal 노드인데 children이 추가되는 경우 '일관성 있지 않은' 목록으로 판단합니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%235052/src/Main.java import java.io.BufferedReader; import java..

BOJ#11049 행렬 곱셈 순서 * 문제https://www.acmicpc.net/problem/11049 * 풀이비슷한 문제 : 파일 합치기 https://www.acmicpc.net/problem/11066 행렬은 결합법칙이 성립합니다. (AB)C = A(BC)그러나 순서에 따라 곱셈 횟수는 달라집니다. 문제 풀이 방식은 파일 합치기 문제와 동일합니다. dp[start][end] = min(dp[start][end], dp[start][k] + dp[k+1][j] + (d_start * d_k+1 * d_end+1)), i

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