알고리즘
-
[백준-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..
-
[백준-1931]-[그리디알고리즘]-회의실배정알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 17:09
문제링크 : https://www.acmicpc.net/problem/1931 이문제를 풀때 가장 햇갈리는 부분은 시작시간과 종료시간의 기준이라고 생각한다. 시작시간으로만 배정 하게 되면 아래와 같은 제약 사항이 발생한다. 1 2 3 4 5 6 7 8 9 시작시간을 기준으로 시작시간이 2인 회의를 배정 하게되면 하나의 회의만 가능하다. 또 회의시간이 짧은것으로 배정을 하게 되면 아래와 같은 제약 사항이 발생한다. 12 3 4 5 6 7 8 9 회의시간이 짧은것으로만 배정을 하게 되면 또다시 하나만 선택 되게 된다. 이렇게 반례가 나오게 되면 그리디 알고리즘을 풀 수가 없다. 이 문제를 푸는 방법은 종료시간을 오름차순으로 정렬하게 되면 쉽게 풀수가 있다. 11 1 4 3 5 0 6 5 7 3 8 5 9 6..
-
[백준-11047]-[그리디알고리즘]-동전 0알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 15:08
문제링크 : https://www.acmicpc.net/problem/11047 이문제는 그리디 알고리즘로 풀면 된다. 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 입력은 위에 처럼 들어오는데 위에는 동전의 수 N, N개의 동전들에서 i개의 최소 조합으로 만들어야 하는 금액 K 이다. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 위의 입력에서 마지막줄에 조건을 볼 수 있다.N개의 동전의 가치 Ai가 오름차순으로 주어진다는 것과 Ai는 Ai-1의 배수 것..
-
[백준-1912]-[다이나믹프로그래밍] - 연속합알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 11. 14:29
문제경로 : https://www.acmicpc.net/problem/1912 이문제는 굉장이 간단하게 접근 할 수 있다. 제공된 예제를 바탕으로 문제를 풀어보자. 10 10 -4 3 1 5 6 -35 12 21 -1 총 10개의 정수가 제공 되고 연속된 구간의 합 중에서 제일 큰 값이 무엇인지 출력해주면 된다.출력은 33이 출력이 돼야 한다. 이문제를 간단하기 풀기 위해선 배열의 크기를 입력받은 사이즈 보다 한칸 더 크게 생성하면 쉽고 짧게 풀 수 있다. 첫번째 입력을 배열의 인덱스 0에 저장하지 말고 1에 저장하면 된다. 이문제를 풀기위해 필요한 변수는 구간합의 최대값을 저장하는 max 라는 변수와 입력받은 값들을 저장할 long 타입의 일차원 배열만 있으면 풀 수 있다. 1234567 public ..
-
[백준-1932]-[다이나믹프로그래밍] - 정수 삼각형알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 15:45
문제링크 : https://www.acmicpc.net/problem/1932 이문제는 백준-1149번 RGB 구하는 문제와 비슷한 형식을 가진다. 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 한칸 한칸 내려가면서 본인의 최대값을 지니고 있고 좌우 대각선 위의 값들을 비교해서 그중 큰 값에 자신의 값을 더한게 본인의 최대값이다. 순서대로 가보면 첫번째 값이 7 이 들어오고 7의 최대값은 7이다. 두번째 줄에 3 8 이 들어오고 각각의 최대 값을 구하면3 의 왼쪽 위 03 의 오른쪽 위 7 8 의 왼쪽 위 78 의 오른쪽 위 0 3의 최대값은 108의 최대값은 15로 아래와 같은 삼각형이 나온다. 710 15 세번째 줄은 8, 1, 0 이 입력 됐고 같은 방법으로 계산하면 정수 피라미드는 아래..
-
[백준-11726]-[다이나믹프로그래밍] - 2 x N 타일링알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 14:58
문제링크 : https://www.acmicpc.net/problem/11726 이 문제는 문제만 그림이지 1과 2로 입력받은 수 N을 만드는 문제이다. 이런식으로 길이 2 * 5의 타일에 2 * 1 타일 로 길이 1을 1 * 2 타일 두개로 길이 2를 채울 수 있다. 그럼 1,2로 5를 만드는 경우의 수를 구하면 된다. 5를 1 또는 2로 만들 수 있는 경우의 수는1 + 1 + 1 + 1 + 11 + 1 + 1 + 21 + 1 + 2 + 11 + 2 + 1 + 11 + 2 + 22 + 1 + 22 + 2 + 1여기서 끝이 1로 끝나는 것들 2로 끝나는 것들을 모아보면- 1로 끝나는 것들 1 + 1 + 1 + 1 + 11 + 1 + 2 + 11 + 2 + 1 + 12 + 2 + 1끝자리 1을 제외하고 나..
-
[백준-2193]-[다이나믹프로그래밍] - 이친수알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 9. 14:11
문제링크 : https://www.acmicpc.net/problem/2193 이 문제는 흠.. 좀 여기에 정리해 가면서 풀어봐야겠다. 머리가 딸리니 연습장에 그려가면서 하기엔 악필이라 영 내가 알아보기가 힘들다 어느정도 풀이법이 보인다. 하나 하나 정리해가면서 해봐야지 자 친절하게 문제에서 이친수가 무엇인지 설명을 해주었다. 이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.위의 두 조건은 잊지 말아야지. 그리고 N 자리 이친수가 몇개 존재하는지 알아봐 달라고 한다. 별걸 다 알고 싶어하네 또다시 빡친다.그래도 뭐 풀어야지 일단 자리수 별로 이친수를 구해보면서 규칙을 찾아봐야겠다. 1 자리는 1 2 자리는 1 03 자리는 1 0 ..