밤이 블로그

BOJ#1234 크리스마스 트리 * 문제https://www.acmicpc.net/problem/1234 * 풀이dp[N][R][G][B] : 레벨 N에서 장난감이 R, G, B개 남아있을 때 경우의 수 각 레벨에서는 3가지 경우를 탐색합니다. 1) 장난감을 1가지 종류만 쓰는 경우2) 장난감을 2가지 종류를 쓰는 경우 (N % 2 == 0일때)3) 장난감을 3가지 종류를 쓰는 경우 (N % 3 == 0일때) 그리고 각 경우의 수를 구한 뒤 장난감들의 순서도 생각해주어야 합니다. 참고 링크 : https://namu.wiki/w/순열(수학)3. 같은 것이 있는 경우의 순열(동자 순열)[편집]n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 ..

BOJ#2309 일곱 난쟁이 * 문제https://www.acmicpc.net/problem/2309 * 풀이오름차순 정렬 후 순열 -> 문제 조건(합이 100)인 경우 return * 나의 코드 (Kotlin)https://github.com/stack07142/BOJ/blob/master/BOJ%232309/src/Main.kt import java.util.* fun main(args: Array) { val input = Scanner(System.`in`) var numArr = Array(9, { 0 }) for (i in 0..8) { numArr.set(i, input.nextInt()) } numArr.sort() permutaion(numArr, 0) for (i in 0..6) { p..

BOJ#10429 QUENTO * 문제https://www.acmicpc.net/problem/10429 * 풀이 dfs 탐색으로 풀었습니다. 개인적으로 문제가 너무 재미있었습니다. 어렵지 않아서 풀이는 생략. * 나의 코드https://github.com/stack07142/BOJ/blob/646def24b7052ba5f4f933c5bfbc7fa9c1b65ce3/BOJ%2310429_QUENTO/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - D. 수학 퍼즐 게임 * BOJ#10429 QUENTO * https://www.acmicpc.net/problem/10429 */ public class ..

BOJ#14438 수열과 쿼리 17 * 문제https://www.acmicpc.net/problem/14438 * 풀이Segment Tree - RMQ설명 : http://stack07142.tistory.com/216 * 나의 코드 (Java, Kotlin)https://github.com/stack07142/BOJ/blob/cd23ff130cc6e28b7f30aea5c4bc8932dad8688b/BOJ%2314438_SequenceQuery17/src/Main.java (Java)import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - E. 수열의 최소값 * BOJ#14439 수열과 쿼리 17 * https://www.acmic..

BOJ#3665 최종 순위 * 문제https://www.acmicpc.net/problem/3665 * 풀이위상 정렬 문제입니다. - 위상 정렬 설명 : http://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093 첫 예제를 통해 어떻게 문제를 풀지 생각해보겠습니다. 5 4 3 2 1 1. 간선과 indegree를 아래와 같이 추가합니다. 간선의 경우 인접리스트보다는 인접행렬로 구현하는게 더 효율적일 것 같습니다. 5->4, 5->3, 5->2, 5->14->3, 4->2, 4->13->2, 3->12->1 [0, 4, 3, 2, 1, 0] int[][] graph = new int[n + 1][n + 1];// n^2 으로 인접행렬..

BOJ#1152 단어의 개수 * 문제https://www.acmicpc.net/problem/1152 * 풀이1. 문자열을 입력받습니다. 앞, 뒤 공백이 있을 수 있으므로 trim 함수를 이용하여 공백을 제거합니다.2. 문자열을 정규표현식을 이용하여 분리합니다. (정규표현식 : \\{Blank}+ : 공백이 하나 이상)3. 분리한 문자열의 개수를 출력합니다. * 나의 코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * BOJ#1152 단어의 개수 * https://www.acmicpc.net/problem/1152 */ public class Main { public stati..

BOJ#2887 행성 터널 * 문제https://www.acmicpc.net/problem/2887 * 풀이 MST, 최소 스패닝 트리 문제입니다.최소 스패닝 트리의 특성상 (문제에도 명시되어 있듯이) 행성이 N개 이므로, 간선은 N-1개가 됩니다. 이 문제를 풀 때 어려웠던 점은 간선 정보가 직접적으로 주어지지 않고직접 간선 정보를 만들어야 한다는 점입니다. 주의할 점으로는N이 최대 100,000 이므로 모든 간선을 입력하려면 100,000 * 100,000이 됩니다. (시간 초과) 따라서 모든 간선을 추가할 수 없으므로, 아래 방법대로 최소 간선만 추가해줍니다. 간선 비용은 문제에 주어진대로 min(x좌표 차이, y좌표 차이, z좌표 차이) 이므로1. x좌표를 기준으로 정렬 -> i-1 노드와 i 노..

BOJ#1010 다리 놓기 * 문제https://www.acmicpc.net/problem/1010 * 풀이풀이 #1. 조합이 문제는 단순히 M개의 사이트 중에서 N개를 고르는 경우의 수를 구하는 문제입니다. 조합 : mCnmCn = m! / {(m-n)! * n!} 풀이 #2. 동적계획법dp[N][M] : 사이트가 각각 N개, M개일 때, 주어진 조건에 맞게 다리를 건설할 수 있는 경우의 수dp[N][M] = dp[N-1][M-1] + dp[N-1][M-2] + ... + dp[N-1][N-1] * 나의 코드https://github.com/stack07142/BOJ/blob/d8bb015604a276ecd8643e16c9ae052c2c36a2fa/BOJ%231010_BuildBridge/src/Mai..

BOJ#11729 하노이 탑 이동 순서 * 문제https://www.acmicpc.net/problem/11729 * 풀이 처음에는 bfs + 비트마스크를 이용하여 풀었습니다.하노이탑의 각 상태를 비트마스크를 이용하여 long 정수 하나로 구현하고, bfs 탐색을 해가면서 목표 정점을 찾는 방식(각 원판은 3개의 장대 중 하나에 존재할 수 있으므로 원판의 위치는 2비트로 표현할 수 있습니다.) 그러나 정점의 최대 개수가 3^20이고, 각 정점마다 3^2 loop를 통해 탐색을 하므로총 시간복잡도 3^22로 시간초과 발생합니다. , - 분할 정복법 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하고, 그 결과들을 합병하면서 본 문제를 해결하는 방식- 단점 : 보통 재귀 방식으로 구현되는데, 재..

BOJ#1525 퍼즐 * 문제https://www.acmicpc.net/problem/1525 * 풀이종만북을 참고하여 풀었습니다.To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기 저는 이번에 bfs와 비트마스크를 이용해보았습니다. 맵은 하나의 정점으로 볼 수 있습니다. (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다) 그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다. 문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.저는 비트마스크를 이용해보았습니다. 각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면..