백준
-
[백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)알고리즘/수학 2018. 11. 27. 13:58
문제링크 : https://www.acmicpc.net/problem/1929 이 문제는 간단한 소수 구하기 소스로 구한다면 굉장히 오랜 시간이 걸리고 시간 초과가 발생하는 문제다. 이문제의 입력되는 수의 범위는 1 ~ 1,000,000 인데 기존 소수 구하는 방식은 2 ~ N-1 까지 반복하면서 나누어 지는 수가 있는지 판단하는 소스 였다. 그럼 최악의 상황에서 1에서 1,000,000 까지 구해야 한다면 상상할 수 없는 연산 수가 발생한다. 이렇게 큰 수들에도 소수가 있을거고 그럼 이 큰 수들을 소수인지 판별하는 방법도 있을것이다. 그게 바로 에라토스테네스의 체 라는 방식인데 노가다라 비효율적인 방식이라고는 하는데 지금 문제에는 제일 적합한 방식이다. 출처 : wiki 백과 에라토스테네스의 체를 구하..
-
[백준 2581] - [수학] - 소수알고리즘/수학 2018. 11. 27. 12:51
문제 링크 : https://www.acmicpc.net/problem/2581 이 문제는 소수이 먼저 확인하고 소수인 수를 합하고 최소값만 구하면 되는 문제이다. 입력받는 수의 최대값은 10000 이기 때문에 int 타입으로 처리가 가능하고 int 타입의 최대 수를 MIN 값으로 초기화 한 뒤에 풀면 소수일경우 최소값을 판단하는데 쉽게 판단 할 수 있다. 그리고 마지막에 결과를 반환할때 최소값의 값이 아직 int의 최대값이면 소수가 발견되지 않은거기 때문데 -1을 출력하면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOExceptio..
-
[백준-2250]-[트리]-트리의 높이와 너비알고리즘/트리 2018. 11. 27. 12:10
문제링크 : https://www.acmicpc.net/problem/2250 이 문제는 중위 순회법으로 문제를 풀면 된다. 중위순회법으로 문제를 접근하는 이유는 노드의 위치를 알기위해선 본인 기준 왼쪽에 있는 모든 노드들의 수를 알아야 하기 때문이다. 그리고 이 문제에서 주의해야 할 점은 1이 무조건 루트가 아니라는거다. 1이 루트가 아니라는 힌트를 먼저 얻은 다음에 문제에 접근해서 어렵지 않게 문제를 풀었다. 먼저 Node 클래스를 하나 만들었다. 12345678910111213class Node{ int num; int left; int right; int parent; public Node(int num, int left, int right, int parent) { this.num = num; ..
-
[백준-4307]-[그리디알고리즘]-개미알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 19:08
문제링크 : https://www.acmicpc.net/problem/4307 이문제는 그림으로 보면서 풀면 이해가 제일 쉬울거 같다. 길이 10의 막대기가 있고 개미 3마리가 있다.개미들의 위치는 2, 6, 7에 있다. 개미1 개미2 개미3 1(지나면 끝) 2 3 4 5 6 7 8 9 10 (닿으면 끝) 여기서 무시해야될 조건이 있다. 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. 위의 조건은 무시하고 각 개미가 떨어지는 시간의 최소와 최대를 구해보면 최소 최대 개미12 8 개미24 6 개미33 7 각 개미의 최소 시간중 제일 큰 값은 4, 최대 시간의 제일 큰 값은 8 주어진 예제의 원하는 값과 같다.각 개미들이 만나는 상황은 신경 쓸 이유가 없다는 뜻이다. 즉 이문제를 푸는 방법은..
-
[백준-2217]-[그리디알고리즘]-로프알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 18:54
문제링크 : https://www.acmicpc.net/problem/2217 이문제는 병렬로 연결된 로프가 버틸 수 있는 최대 중량이 얼마나 되는지 물어보는 문제이다. 로프가 한개일 때는 로프가 버틸 수 있는 한계가 최대 중량이다. 그럼 로프가 두개일 때는? 로프의 최대중량이 작은 로프의 힘 * 2 가 로프가 두개일때 최대 중량이다. 왜그럴까?? 문제에 다음 조건이 존재하기 때문이다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 중량이 20 일때 로프 두개를 사용하면 한 로프당 걸리는 중량은 10 이다. 최대중량이 10, 12 의 로프 두개가 있을때 최대 중량이 12인 로프가 아무리 10보다 더 들 수 있어도 그 이상의 무게를..
-
[백준-11399]-[그리디알고리즘]-ATM알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 18:36
문제 링크 : https://www.acmicpc.net/problem/11399 이문제는 아주 쉽게 계산했다. 최선과 최악의 경우의 수만 설명하면 어떻게 풀지 감이 올것이다.5 3 1 4 3 2위와 같이 입력이 되고 각 사람별 인출하는 시간이 3, 1, 4, 3, 2 라고 한다. 1번 사람은 3분 2번 사람은 1분 3번 사람은 4분 4번 사람은 3분 5번 사람은 2분 i 번 사람이 인출하는데 걸리는 시간은 i - 1번 사람이 걸린 시간에 i 사람이 인출하는데 소요되는 시간이다. 아래에 최악과 최선의 순서를 보면 어떻게 풀어야 할지 감이 온다. 최악3번, 1번, 4번, 5번, 2번 순으로 인출을 한다.3번 사람은 4분1번 사람은 4 + 3 = 7분 4번 사람은 7 + 3 = 10분5번 사람은 10 + 2..