밤이 블로그

BOJ#4485 녹색 옷 입은 애가 젤다지? * 문제https://www.acmicpc.net/problem/4485 * 풀이다익스트라 (Priority Queue 이용)개념만 알면 풀 수 있는 기본 문제이므로 설명은 생략합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/7abd485c7bdc3853570ff8d262afbd03b7234709/BOJ%234485/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenize..

BOJ#6549 히스토그램에서 가장 큰 직사각형 * 문제https://www.acmicpc.net/problem/6549 * 풀이세그먼트 트리 + 분할정복으로 풀었습니다.어려워서 많이 고생한 문제입니다. - 구하는 것 : 히스토그램에서 가장 큰 직사각형 - 히스토그램은 막대의 집합이고, 모든 막대 x에 대하여 막대 x의 높이로 하면서 만들 수 있는 가장 큰 직사각형들을 구해봅시다.- 어떤 막대 x에 대하여 양쪽으로 직사각형을 확장해나가면, 막대 x 높이로 만들 수 있는 가장 큰 직사각형을 구할 수 있습니다. - 우리는 그것들 중 가장 큰 직사각형을 구하면 됩니다. - 그렇다면 [2 1 4 5 1 3 3]의 히스토그램이 주어졌을 때, 어떤 순서로 막대를 검사하면 될까요- 가장 작은 막대부터 (높이가 작은 ..

BOJ#1992 쿼드트리 * 문제https://www.acmicpc.net/problem/1992 * 풀이- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다. 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)(출처 : 알고리즘 문제 해결 전략) 위 해결 전략을 염두하고 문제를 풀어보았습니다.쉬운 문제이므로 풀이는 생략하겠습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231992/src/Main.java import java.io.Buffer..

BOJ#1074 Z * 문제 https://www.acmicpc.net/problem/1074 * 풀이- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다. 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)(출처 : 알고리즘 문제 해결 전략) 위 해결 전략을 염두하고 알고리즘을 구상해봅시다. 1. 나눌 수 있는 경우 (divide & merge) (r, c)가 몇 사분면에 있는지 알아냅니다 만약 3 사분면이라면1, 2 사분면의 사각형의 개수는 쉽게 구할 수 있을 것입니다. 2. 나눌 수 없는 경우 (bas..

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개에 해당하..