밤이 블로그

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 ※ 주의할 점 - ..

BOJ#2609 최대공약수 최소공배수 * 문제https://www.acmicpc.net/problem/2609 * 풀이 두 자연수 a, b가 주어졌을 때 (a>b), 두 자연수의 최대공약수를 구하는 알고리즘 : 유클리드 호제법두 자연수의 최소공배수를 구하는 알고리즘 : a*b/최대공약수 유클리드 호제법유클리드 호제법(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.호제법이란, 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. m >= n일 때,① m을 n으로 나눈다. 나머지를 r이라고 한다.② 나머지 r이 0이면 n이 최대공약수이다. 나머지가 0이 아니라면 m의 값을 n으로 설정하고, n의 값은 r로 설정한 다음 ①로 되돌아가서 ..

BOJ#11403 경로찾기* 문제https://www.acmicpc.net/problem/11403 * 풀이 가중치 없는 방향 그래프가 행렬로 주어졌을 때, i에서 j로 가는 경로 유무를 행렬로 표현하라. bfs(Breadth First Search)를 이용하였다. 1. bfs(i, j) : i를 시작점으로 해서 연결된 모든 노드를 탐색한다. j를 찾을 경우 return.2. 위 과정에서 탐색한 노드는 중복해서 탐색하지 않도록 한다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311403_BFS_FindPath/src/Main.java Java (17.08.29)import java.io.*; import java.util.LinkedList;..

B-Tree #0. 시작하기- B-Tree는 외부 다진검색 트리 + 균형 트리이다.- 검색 트리가 내부 메모리가 아닌 외부(디스크 등)에 있는 상태로 사용되면 '외부 검색 트리'- 분기(자식수)가 2를 넘으면 '다진 검색 트리' #1. 개요º Balanced Tree란? - 이진 검색 트리의 문제점은 좌우 균형이 맞지 않으면 비효율적. 트리의 성능은 곧 트리의 depth인데, 좌 또는 우로 치우친 경우 O(logN) → O(n^2)까지 성능이 느려질 수 있다. - Balanced Tree는 삽입, 삭제 시 필요하면 스스로 균형을 유지한다. - ex) AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree 등 - 항상 (최악의 경우에도) O(logN) 성능을 보장 º B-Tre..

* 문제 https://www.acmicpc.net/problem/1007 * 풀이 평면 상에 N개의 점이 찍혀있다. (N은 짝수) N개의 점을 이용해서 벡터를 만든다. 벡터는 당연히 N/2개 나올 것이다. 문제를 자세히 보니, N개 점들의 좌표가 주어지고 평면벡터이다. 평면 상에 2개의 점 A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4)가 주어졌고 임의의 벡터를 구성했다고 가정해보자. 2개의 임의의 벡터이다. AB = (x1-x2, y1-y2) CD = (x3-x4, y3-y4) 위 2개의 벡터의 합은 아래와 같다. AD+CD = (x1+x3-(x2+x4), y1+y3-(y2+y4)) 위 벡터의 크기는 Math.sqrt((x1+x3-(x2+x4))^2, (y1+y3-(y2+..

* 조합 (Combination) : 서로 다른 n개에서 r개를 뽑는 것을 n개에서 r개를 택하는 조합이라 하고 이 조합의 수를 nCr로 나타낸다. : 조합은 배열을 생각하지 않으므로(순서X) 선택하여 배열하는 순열의 수를 배열의 수로 나눈 값이라고 생각해도 무방하다. 문제. 4개의 원소(0~3)에서 2개를 뽑는 모든 경우의 수를 출력하시오. (Java) 풀이.Combination을 구현하려면 어떻게 해야 할까? nCr = n-1Cr + n-1Cr-1위 식은 아래와 같이 이해할 수 있다. A,B,C,D,E 5명 중 3명을 뽑는 경우, 5C3이 경우는 A를 기준으로 나눌 수 있다. 1) A가 이미 정해진 경우 : A, x, x : 나머지 4명중 2명을 뽑아야 함. 4C22) A가 제외된 경우 : x, x,..