밤이 블로그

BOJ#11726 2xn 타일링 * 문제https://www.acmicpc.net/problem/11726 * 풀이동적계획법(Dynamic Programming)을 이용합니다. 2xN일 때, 아래와 같이 2개의 하위 문제로 나눌 수 있습니다. dp[N] = dp[N-1] + dp[N-2](dp[N] = 2xN 직사각형을 1x2, 2x1 타일로 채우는 방법의 수) static int go(int n) { if (n 0) { return dp[n]; } dp[n] = (go(n - 1) + go(n - 2)) % DIVISOR; return dp[n]; } * 나의 코드https://github.com/stack07142/BOJ/tree/master/B..

BOJ#1463 1로 만들기 * 문제 https://www.acmicpc.net/problem/1463 * 풀이 동적 계획법 (Dynamic Programming) 기초 문제입니다. * 동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다. : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. * 메모이제이션 (Memoization) : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. : 동적 계획법의 핵심이 되는..

BOJ#11656 접미사 배열 * 문제https://www.acmicpc.net/problem/11656 * 풀이 쉬운 문제이므로 풀이는 코드로 대체합니다. * 간단 Tip- ArrayList 오름차순 정렬 Collections.sort(suffixArr); - ArrayList 내림차순 정렬 Comparator reverseOrder = Collections.reverseOrder(); Collections.sort(suffixArr, reverseOrder); * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%2311656_SuffixArray

BOJ#1406 에디터 * 문제https://www.acmicpc.net/problem/1406 * 풀이 자바에 기초가 없어서 그런지 이번 문제는 꽤 어려웠습니다 1)자료구조 선택 시, ArrayList 대신 LinkedList를 선택합니다.왜냐하면 리스트 중간에서 삽입/삭제 시 LinkedList가 속도면에서 더욱 유리하기 때문입니다. 물론 index활용이 전제되어야 합니다. 중간에서 삽입/삭제 시 유리한 것은 맞지만, 그 전에 중간까지 가기 위한 검색 과정이 O(n)으로 오래 걸리기 때문입니다. 2) Iterator를 사용합시다.Iterator는 Java Collection에 저장된 요소에 접근하는데 사용되는 표준화된 인터페이스입니다. 이 문제에서는 ListIterator를 사용하는 것이 좋겠습니다...

BOJ#10799 쇠막대기 * 문제https://www.acmicpc.net/problem/10799 * 풀이초등부, 중등부 문제입니다. 어렵지 않고 재밌는 문제인 것 같아요. 저는 일단 입력받은 String에서 ()을 x로 치환했고,이후 Char Array로 변환해서 for loop을 돌렸습니다. 입력값 : (((()(()()))(())()))(()())치환값 : (((x(xx))(x)x))(xx) loop를 돌면서' ( ' 가 나오면 왼쪽 괄호 개수++, 조각 개수++' x ' 가 나오면 레이저 개수++ → 조각 개수 update → 레이저 개수 = 0' ) ' 가 나오면 왼쪽 괄호 개수-- inputStr = br.readLine(); replacedStr = inputStr.replace("()"..

BOJ#1041 주사위 * 문제https://www.acmicpc.net/problem/1041 * 풀이 - if (N == 1) 인 경우 : A~F 중 가장 큰 숫자가 써진 면이 바닥을 향해야한다. - if (N > 1) 인 경우 : N^3개의 주사위로 N*N*N 크기의 정육면체를 만들 때,정육면체를 구성하는 주사위는 3가지 경우로 구분할 수 있다. 1) 1면만 노출되는 주사위 2) 2면이 노출되는 주사위 3) 3면이 노출되는 주사위 위 3가지 경우의 각각의 최소값을 구한다. 그리고, N = 1, 2, 3, 4...인 경우를 직접 손으로 그려 규칙을 찾은 후 위의 값들을 대입하여 푼다. public void calculateSum() { if (numOfDice == 1) { for (int i = 0..

BOJ#9663 N-Queen * 문제https://www.acmicpc.net/problem/9663 * 풀이 유명하면서도 어려운 문제입니다. Queen을 1개~N개까지 배치하면서, 잘못 배치한 경우 되돌아가서 다른 시도를 해봐야 합니다. 따라서 backTracking을 이용합니다. 주의할 점 0. QueenQueen은 상하좌우, 대각선 모두 이동할 수 있습니다. 1. 꼭 행렬로 map을 만들 필요가 없습니다.보통 map 행렬을 만든 후 -1, 0, 1등의 숫자를 이용해배치할 수 있는 곳과 아닌 곳을 표시하고, 이 정보를 기반으로 다음 행동을 결정하는데 이 경우 불필요한 리소스와 시간이 소요됩니다. 2. Queen은 N개 이므로 행(row) 1개당 Queen 1개가 배치됩니다. = 각 행마다 Queen..

BOJ#2178 미로 탐색 * 문제https://www.acmicpc.net/problem/2178 * 풀이 bfs(Breadth First Search) 기본 문제입니다. 개념만 알면 풀 수 있는 문제이기 때문에설명은 생략하겠습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232178_MazeSearching/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringToke..

BOJ#4134 다음 소수 * 문제https://www.acmicpc.net/problem/4134 * 풀이 이 문제는 2가지 버전으로 풀어 보았다. Solution#1 (메모리 : 73836 KB, 시간 : 1308 MS)입력값이 0

BOJ#1929 소수 구하기 * 문제https://www.acmicpc.net/problem/1929 * 풀이 - 단순히 접근하면, 체크하려는 모든 수 x에 대해 2부터 x까지 %연산을 해보는 방법이 있겠다. 그러나 주어진 숫자가 커질 수록 많은 시간이 걸리기 때문에 시간을 줄일 수 있는 방법을 생각해야 한다. (정의) 소수 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. 에라스토테네스의 체 1. 2, 2를 제외한 모든 2의 배수를 제외한다.2. 3, 3을 제외한 모든 3의 배수를 제외한다.3. 4, 4를 제외한 모든 4의 배수를 제외한다....반복... 출처 및 공부 자료 : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ※ 주의할 점 - ..