코딩테스트14 [이분 탐색] 백준 1789번 (파이썬) : 수들의 합 그리디 알고리즘을 활용하여 풀라고 적혀있습니다. 그리디 알고리즘이란, 실제 최적의 값을 떠나 단계 별로 가장 최고의 값을 골라가는 것입니다. 이를 문제에 활용해 본다면 당연히 작은 수들이 많아야 N이 높아지기 때문에 다음과 같이 코드를 짤 수 있습니다. s = int(input()) total = 0 num = 0 while True: num += 1 total += num if total > s: break print(num-1) 2023. 4. 5. [완전 탐색] 백준 5568번 (파이썬) : 카드 놓기 문제는 카드를 k장 골랐을 때 이를 나열하여 만들 수 있는 정수의 개수를 출력하는 문제이다. 당연히 중복은 제외된다. from itertools import permutations n, k = int(input()), int(input()) nums = [] result = set() for i in range(n): num = input() nums.append(num) for per in permutations(nums, k): result.add(''.join(per)) print(len(result)) 고른 카드들을 경우의 수를 다 따라 알아봐야 하기 때문에 combination을 쓰면 되지 않냐고 할 수 있는데 조합은 (A, B)와 (B, A)를 같은 것으로 취급하지만 이 문제에서는 1과 2를 .. 2023. 3. 24. [완전 탐색] 백준 14501번 (파이썬) : 퇴사 date = int(input()) t = [] p = [] max_gain = [] for _ in range(date): ti, pi = map(int, input().split()) t.append(ti) p.append(pi) for _ in range(date + 1): max_gain.append(0) for i in range(date-1, -1, -1): if t[i] + i > date: max_gain[i] = max_gain[i+1] else: max_gain[i] = max(max_gain[i+1], max_gain[t[i]+i] + p[i]) print(max_gain[0]) 먼저 예제 입력을 따라 date 변수를 입력받아줍니다. 그리고 퇴사 전 남은 날짜에 따라 상담 시간과 이익.. 2023. 3. 17. [완전 탐색] 백준 17626번 (파이썬) : Four Squares 문제 해석을 하는 것은 어렵지 않았습니다. 요약하가면 아무 숫자나 입력받고 그 숫자를 최대 4개 이하의 제곱수의 합으로 나타내기만 하면 된다는 것입니다. import math def four_squares(n): if int(math.sqrt(n)) == math.sqrt(n): return 1 for i in range(1, int(math.sqrt(n)) + 1): if int(math.sqrt(n - pow(i, 2))) == math.sqrt(n - pow(i, 2)): return 2 for i in range(1, int(math.sqrt(n)) + 1): for j in range(1, int(math.sqrt(n - pow(i,2))) + 1): if int(math.sqrt(n - pow.. 2023. 3. 16. 이전 1 2 3 4 다음
