밤이 블로그

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

BOJ#1890 점프 * 문제https://www.acmicpc.net/problem/1890 * 풀이dp + dfs로 풀었습니다.정답 비율에 비해 문제가 굉장히 쉽습니다. N 범위와 경로의 개수 범위(long)만 주의하면 될 것 같습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231890/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int[] dRow = {0, 1}; stat..

BOJ#10216 Count Circle Groups * 문제https://www.acmicpc.net/problem/10216 * 풀이주어진 노드들은 결국 disjoint sets를 형성합니다. 따라서 Union-Find 자료구조를 이용해보았습니다. Two sets are said to be disjoint if they have no element in common. (출처 : https://en.wikipedia.org/wiki/Disjoint_sets) 해야 할 일은 3가지입니다. 1. 노드 간 거리 비교 : 거리 비교 시 양변을 제곱하여 비교하였습니다. 2. 비교 결과에 따라 노드를 그룹으로 묶기 : Union-Find 자료구조 사용 3. 그룹 개수 출력하기 : UnionFind Class에 c..

BOJ#1927 최소 힙 * 문제https://www.acmicpc.net/problem/1927 * 풀이- Heap 설명 : http://stack07142.tistory.com/198 - 2가지 방법으로 풀어 보았습니다. 1) 제공되는 PriorityQueue 이용하기 2) Min Heap 구현하기 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231927_MinHeap/src 1) Priority Queue 이용하기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; /** ..

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

알고리즘 공부 리스트 및 순서 (Algorithm Problem Solving Roadmap) 제 Github 계정입니다. 많이 놀러오세요~https://github.com/stack07142/BOJ ▼ 대충 어떤 것들을 공부해야하는지 그려보았습니다. 잘못된 정보가 있을 수 있으니 참고해주시고, 고칠 점 있으면 댓글 남겨주세요. Inspired Byhttps://github.com/kamranahmedse/developer-roadmaphttps://github.com/godrm/mobile-developer-roadmaphttp://blog.naver.com/wnsgh224/220897329629

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