밤이 블로그

BOJ#2096 내려가기 * 문제https://www.acmicpc.net/problem/2096 * 풀이메모리 제한이 4MB 입니다. 저는 처음에 재귀 형식으로 풀었다가 바텀업 방식으로 다시 풀었습니다. 또한, [100001][3] 사이즈의 dp배열과 map 배열을 모두 제거하였습니다. 두가지 형태의 코드 모두 아래에 붙여놓았으니 참고하시면 좋겠습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/458582301c132e9a61af00c77068edac24669619/BOJ%232096/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream..

BOJ#1963 소수 경로 * 문제https://www.acmicpc.net/problem/1963 * 풀이- 구하는 것 :두 소수 변환에 필요한 최소 변환 횟수 (최단 경로, 가중치 1이고 경우의 수가 많지 않으므로 BFS 탐색 가능) - 조건 : 4자리수, 소수로만 이동 가능, 중복 방문 x - 예를 들어 Test Case가 '1033 8179'인 경우 step = 0;1) 1033에서 한자리수를 변경해서 만들 수 있는 모든 소수들을 구한 후 Queue에 넣는다. (step = 1)2) step == 1인 Queue에 들어있는 모든 수에 대해 반복 (step = 2)3) step == 2인 Queue에 들어있는 모든 수에 대해 반복 (step = 3)....결국 step == n에서 8179를 찾게 ..

BOJ#2698 인접한 비트의 개수 * 문제https://www.acmicpc.net/problem/2698 * 풀이문제가 어려울 때는 동적계획법의 정의에 대해 다시 생각해봅시다. 1. 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법 (하위 문제들의 답을 저장한다, 메모이제이션) 2. dp정의와 점화식을 도출해보자 , 1. 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법 일단 복잡한 문제란 길이가 긴 수열이라는 뜻이고 (우리가 손으로 풀 수 없음)간단한 하위 문제란 길이가 짧은 수열이라는 것입니다. (우리가 손으로 충분히 풀 수 있음) 결국 짧은 길이의 수열에서 점점 길이를 증가시키면서 우리가 원하는 답을 구하면 되는 것입니다. 이 문제의 경우수열의 각 자리는 0 또는 1이므로 이를 힌트로 하여 ..

BOJ#5015 ls * 문제https://www.acmicpc.net/problem/5015 * 풀이 재귀 형태로 풀었습니다. 입력 파라미터는 패턴 문자열 P의 index인 p와 검사할 문자열 S의 index인 s입니다. 반환값은 memoization값인 dp[p][s]이며, dp[p][s]는 P[p]와 S[s]를 비교한 결과(매칭 여부)를 의미합니다. dp[p][s] = TRUE(1) or FALSE(0)static int checkStringPattern(int p, int s) 일단 패턴은 와일드카드(*) 와 그 외 문자로 분류할 수 있습니다. 1. 와일드 카드(*)의 경우와일드카드는 어떤 문자의 0개 또는 그 이상에 해당하므로 아래의 3가지 경우로 나누어 탐색할 수 있습니다. 1) 0개에 해당하..

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#2042 구간 합 구하기 * 문제https://www.acmicpc.net/problem/2042 * 풀이 http://stack07142.tistory.com/216 * 나의 코드 https://github.com/stack07142/BOJ/blob/48ba119dd11b7779be8b2d1e05a64b723e334d54/BOJ%232042_RangeSumQuery/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#2042 구간의 합 구하기 * https://www.acmicpc.net/problem/2042 */ public class Main { static final int QUERY_CHANGE = 1;..

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