분류 전체보기
-
[백준 3036] - [수학 최대공약수] - 링 (JAVA)알고리즘/수학 2018. 12. 4. 11:14
문제 링크 : https://www.acmicpc.net/problem/3036 이문제는 높은 정답률을 자랑한다.그렇다는건 너무 쉽다는 거고 깊은 생각을 할 필요가 없는 문제다. 4 12 3 8 4 예제와 같이 12 3 8 4가 입력이 되고 첫번째 링인 12가 한바퀴 돌았을때 다른 링들은 볓바퀴 돌것이냐 라는 말이다. 그럼 12와 각 링들의 최대 공약수를 구해서 나눠 주면 되겠구나 생각했다. 최대공약수 나눈다면 자연스럽게 기약분수로 만들어 질것이다. 12와 3의 최대 공약수는 3 -> 12 / 3 + "/" +3 / 3 하면 4/112와 8의 최대 공약수는 4 -> 12 / 4 + "/" + 8/4 하면 3/212와 4의 최대 공약수는 4 -> 12 / 4 + "/" + 4/4 하면 3/1 다 구했다 아..
-
[백준 2981] - [수학 최대공약수] - 검문 (JAVA)알고리즘/수학 2018. 12. 4. 11:07
문제 링크 : https://www.acmicpc.net/problem/2981 이 문제는 정답률에서도 나오듯이 극악의 문제이다. 왜 극악이라 하냐면 쓸데없는데서 시간을 낭비 했기에 극악의 문제로 생각한다. 6 34 38 총 3개의 수가 주어지고 종이에 적은수 M으로 나누었을때 나머지가 모두 같게 되는 모든 M을 찾아 보기위해 노력 해봤다. 처음에는 시간초과가 발생했다. 시간초과를 발생하게한 방식은 다음과 같다. 입력 받은 수의 배열 arr에서 인덱스 1번부터 arr.length-2 까지 반복하면서 i 기준 arr[i] - arr[i-1] , arr[i+1] - arr[i] 두 수의 최대 공약수를 구하고 그 최대 공약수중에서 제일 작은 최대 공약수의 약수를 반환했다. 결과는 제대로 나왔다. 하지만 시간 ..
-
[백준 1850] - [ 수학 최대공약수 ] - 최대공약수 (JAVA)알고리즘/수학 2018. 12. 4. 01:42
문제 링크 : https://www.acmicpc.net/problem/1850 이 문제는 어려움을 가장한 쉬운 문제이다. 낮은 정답률에 겁을 먹고 다들 시도를 하지 못한거 같다. 예제 입력 3번의 값이 이 문제는 변태적인 문제다 겁을 먹어라 하는거 같다. 500000000000000000 500000000000000002예제 입력 1번의3 4로 보면 111과 1111의 최대 공약수를 구하면 되겠구나!! 하겠지만 예제 입력 3번은 어떻게 하라고.. 1을 저만치 쓰라고?? 하면서 겁을 먹게 하는거 같다. 그냥 단번에 아 낚시구나 생각했고 두 수의 최대 공약수를 구해보았다. 예제 입력 1 의 입력값 3 4의 최대 공약수는 1예제 입력 2 의 입력값 3, 6의 최대 공약수는 3예제 입력 3의 입력값 무진장 큰..
-
[백준 13241] - [수학] - 최소공배수 (JAVA)알고리즘/수학 2018. 12. 4. 01:33
문제링크 : https://www.acmicpc.net/problem/13241 이 문제는 쉬운 문제이므로 이전글을 첨부하면서 설명을 마친다.아래 두 문제를 푼다면 이문제는 너무 쉬워서 심지어 눈감고 풀 수도 있겠다. 2018/12/03 - [알고리즘/수학] - [백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA) 2018/12/04 - [알고리즘/수학] - [백준 1934] - [수학] - 최소공배수 (JAVA) 소스 123456789101112131415161718192021222324import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = ne..
-
[백준 1934] - [수학] - 최소공배수 (JAVA)알고리즘/수학 2018. 12. 4. 01:30
문제 링크 : https://www.acmicpc.net/problem/1934 이 문제는 백준 2609문제를 먼저 풀었다면 문제 푸는데 걸리는 시간은 금방일 것이다. 이번문제에 대한 설명 최소 공배수와 최대 공약수에 대한 설명은 백준 2609번 문제 링크와 풀이 링크로 대체하겠다. 백준 2609 문제 2018/12/03 - [알고리즘/수학] - [백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA) 소스123456789101112131415161718192021222324252627282930313233343536import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReade..
-
[백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA)알고리즘/수학 2018. 12. 3. 15:35
문제 링크 : https://www.acmicpc.net/problem/2609 이문제는 입력 받는 두 수의 최대 공약수와 최소 공배수를 구하는 문제이다. 최대 공약수는 두 개 이상의 수가 공통으로 가지는 약수 중 가장 큰 수를 말한다. 두 수 18과 24가 있다 하면 각각의 약수는 다음과 같다.18의 약수 : 1, 2, 3, 6, 9, 1824의 약수 : 1, 2, 3, 4, 6, 8, 12, 24이들 약수중에 공통으로 가지는 약수는 {1, 2, 3, 6}이고 이들 중 가장 큰 수는 6이 된다. 먼저 18의 약수를 구하고 24의 약수를 구한다음 각 각 의 약수중에서 공통 약수를 추려낸 뒤 그중 제일 큰 수를 찾았다. 수의 크기가 작은 경우 빠르게 구할 수 있겠지만 만약 수가 큰 수라면 어떻게 될까?각각..
-
[백준 1260] - [DFS BFS] DFS와 BFS (JAVA)알고리즘/BFS_DFS 2018. 12. 2. 15:02
문제 링크 : https://www.acmicpc.net/problem/1260 이 문제는 DFS와 BFS를 제대로 이해하고 있는지 파악하는 문제로 보면 된다. 이미 여러개의 DFS BFS 문제를 포스팅을 했지만 이번에 푼 문제가 이 문제여서 DFS와 BFS의 개념을 한번 복습을 해보자. DFS는 깊이 우선 탐색(Depth First Search)의 약자이고 BFS는 너비 우선 탐색(Breadth First Search)의 약자이다.노드들을 탐색할때 먼저 탐색된 노드의 자식노드를 우선적으로 탐색하는것을 말한다. 만약 위의 노드들을 1을 기준으로 DFS로 조회한다고 하면 어떻게 될까? 먼저 기준점 1의 자식노드들을 확인한다. 1의 자식노드들은 {2, 3} 이 있고 2부터 탐색을 시작한다. 2의 자식노드들은..
-
[백준 10845] - [큐] - 큐 (JAVA)알고리즘/큐(Queue) 2018. 12. 2. 14:02
문제 링크 : https://www.acmicpc.net/problem/10845 이 문제는 큐를 제대로 이해하고 있는지 파악하는 문제로 보인다. 근데 내가 기억하는 큐는 선입선출이고 탐색은 front 할 수 있다고 알고 있었는데 이 문제는 back도 탐색을 하라고 한다. 그래서 push로 큐에 삽입할때 back의 값을 변경하고 POP으로 큐에서 추출할때 추출한 이후에 큐가 비어 있으면 큐의 크기를 -1로 변경했다. 큐는 선입선출이니 딱 이 두 상태에서만 back의 값을 변경해주면 문제는 없다. 소스12345678910111213141516171819202122232425262728293031323334353637383940414243444546import java.io.BufferedReader;imp..