알고리즘
-
[백준 15953] - [카카오 코드 페스티벌 예선 2018] - 상금헌터 (JAVA)알고리즘/카카오 코드 페스티벌예선 2018 2018. 12. 4. 17:01
문제 링크 : https://www.acmicpc.net/problem/15953 내 실력이 어디까지인지 확인해보고자 카카오 코드 페스티벌 예선 문제를 풀었다. 아직은 카카오에 갈 실력이 안되나보다. 그나마 이 문제는 쉽다. 2017년 본선진출자 100명 중 상금 수여 21명순위 상금 인원 1등 500만 1 2등 300만 2 3등 200만 3 4등 50만 4 5등 30만 5 6등 10만 6 2018년 본선진출자 64명 중 상금 수여 31명 순위 상금 인원 1등 512만 1 2등 256만 2 3등 128만 4 4등 64만 8 5등 32만 16 이 문제를 풀기 위해서 위의 상금 정보를 기반으로 배열을 만들었다. public static int[] reward17 = {500, 300, 200, 50, 30,..
-
[백준 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의 자식노드들은..