알고리즘
-
알고리즘: 백준 1037번 약수(feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 14:35
백준 1037번 링크입니다. 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 방법 1 #include using namespace std; int main() { int n; int x; int max = -1; int min = 1000000; cin >> n; for (int i = 0; i > x; if (max x) { min = x; } } int answer = min * max; cout n; for (int..
-
알고리즘: 백준 10610번 30 (feat. Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 17:55
백준 10610번 링크입니다. https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 30의 배수가 되기 위한 조건은 어떤수 N이 10의 배수이고 3의 배수인 경우이다. N이 10의 배수가 되기 위한 조건 = N안에 0이 포함되어 있으면 성립 N이 3의 배수가 되기 위한 조건 = N의 모든 자리수를 더했을 때 3의 배수이면 성립 이 두 조건만 성립하면 최대값은 N을 그냥 그대로 내림차순 정렬한 값이다. import sys input = sys.std..
-
알고리즘: 백준 2217번 로프 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 16:51
백준 2217번 링크입니다. https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 로프들이 견딜 수 있는 리스트를 만들어 오름차순으로 배열한다. 만약 10, 25, 30가 로프가 버틸 수 있는 최대중량으로 주어진다면 10 x 3 = 30 25 x 2 = 50 30 x 1 = 30 으로 최대 버틸 수 있는 중량은 50이 된다. ropes[i] * (n - i) 들로 이루어진 리스트의 최대 값을 찾으면 되는 것이다. import sys input ..
-
알고리즘: 백준 1932번 회의실 배정 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 16:22
백준 1932번 링크입니다. https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 최대 사용할 수 있는 회의의 수를 구하기 위해서는 가장 빨리 회의가 끝나는 순으로 회의를 나열한다. 회의의 끝나는 시간을 오름차순으로 배열한 후 전 회의의 시작시간과 다음 회의의 끝나는 시간을 비교하여 리스트를 담는다. 처음에 2차원 리스트의 두번째 요소만 배열하기 위해서 이중 for문을 사용했지만 O(n) = n^2가 되기 때문에 시간초과가 되었다. 그래서 lambda x: x[1]를 key로 받아 sort 함으로써 문제를 해결하였다. import sys input = sys.stdi..
-
알고리즘: 백준 11047번 동전0 (feat.Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 15:27
4200원을 만드는데 필요한 동전의 갯수가 최소가 되게하기 위해선 가장 큰 동전으로 나누어 나가면 된다. 4200원 다음으로 가장 동전은 1000원이므로 4200 // 1000 = 4 ... 200 200 //100 = 2 ... 0 이므로 4 + 2 = 6이다. import sys input = sys.stdin.readline n, k = map(int, input().split()) money_list = [] for i in range(n): money_list.append(int(input())) change_count = 0 for i in range(n - 1, - 1, -1): if k == 0: break tmp = (k // money_list[i]) change_count += tmp..
-
알고리즘: 백준 11399번 ATM (feat. Python)알고리즘/백준(BaekJoon) 2020. 8. 8. 15:19
3 1 4 3 2을 입력으로 받을 때 돈을 인출하는데 걸리는 시간의 합은 3 x 5 + 1 x 4 + 4 x 3 + 3 x 2 + 1 x 1 입니다. 직관적으로 3 1 3 4 2를 오름차순으로 배열해서 각각 5부터 1까지 곱한다면 돈을 인출하는데 걸리는 시간이 최소가 됨을 알 수 있습니다. import sys input = sys.stdin.readline n = int(input()) get_time = list(map(int, input().split())) total = 0 get_time.sort() for i in range(n): total += (n - i) * get_time[i] print(total) 5 3 1 4 3 2 32 Process finished with exit code 0
-
알고리즘: 백준 2193번 이친수 (feat.Python)알고리즘/백준(BaekJoon) 2020. 7. 29. 15:09
예시를 들어서 문제를 좀 더 자세히 뜯어 봅시다. f(N) = N 자리 이친수의 개수 라고 할때, N = 5 인 상태 즉, f(5)는 어떻게 구성되어 있을까요? 우선 N = 5 일때 이친수는 다음과 같습니다. 10101 10100 10010 10001 10000 이것들을 가장 처음 1을 제외한 그 다음 1을 기준으로 쪼개보면 다음과 하나의 규칙을 발견할 수 있습니다. 10101 10100 f(3)과 모양이 같고 100010 f(2)와 모양이 같고 100001 f(1)과 모양이 같습니다. 100000 N = 0 는 정의되어 있지는 않지만 f(0) = 1이라고 합시다. 이렇게 봤을 때 f(5) = f(3) + f(2) + f(1) + f(0) 이라고 할 수 있겠군요! 그런데 여기서 또 살펴보면 f(2) + ..
-
알고리즘: 백준 1932번 정수 삼각형 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 22. 07:21
최적 부분 구조와 중복되는 부분이 보인다. 다이나믹 프로그래밍으로! 점화식: n 번째 줄 0번째까지의 합 = n - 1번째 줄 0번째까지의 합 + n 번째 줄 0번째 값 n 번째 줄 1번째까지의 합 = max(n - 1번째 줄 0번째까지의 합, n - 1번째 줄 1번째까지의 합) + n번째 줄 1번째 값 n 번째 줄 2번째까지의 합 = max(n - 1번째 줄 1번째까지의 합, n - 1번째 줄 2번째까지의 합) + n번째 줄 2번째 값 ... n 번째 줄 n - 1번째까지의 합 = max(n - 1번째 줄 n - 2번째까지의 합, n - 1번째 줄 n - 1번째까지의 합) + n번째 줄 n - 1번째 값 n 번째 줄 n번째까지의 합 = n - 1번째 줄 n - 1번째까지의 합 + n 번째 줄 n번째 값..