본문 바로가기

greedy7

그리디 알고리즘, 원인과 결과 찾기 🧑‍💻 그리디 알고리즘, 원인과 결과 찾기 멀티잇 코딩테스트 러닝클래스'Python 5월반 거스름돈 1, 5, 10, 20, 40 원이라는 동전이 있다 N원을 거슬러 주기 위한 최소의 동전의 개수를 구하는 것 기본적으로 40부터 시작해서, 남은 나머지를 계산해주면 된다 N = int(input()) coin = [40, 20, 10, 5, 1] count = 0 for c in coin: if c temp_end: count += 1 temp_end = end print(count) 2023. 5. 23.
[Python] 백준 25418 정수 a를 k로 만들기 🧑‍💻 [Python] 백준 25418 정수 a를 k로 만들기 Silver 3 - 그리디 A에서 K를 찾는 것이 아닌, K에서 A를 찾는 것이 제일 쉽다 제일 큰 수에서, 짝수이면 2를 나누고, 홀수이면 1을 빼준다 단 짝수에서 2를 나눴을 때에 항상 A보다 커야 한다 문제풀이 K를 A로 만들어야 하고, 2로 최대한 많이 나누어야지, 최소로 연산을 할 수 있다 while 문을 통해 K가 A가 될때까지 순회를 한다 K가 짝수이거나, 2로 나누었을 때 A보다 커야지만 2로 나눌 수 있다 그게 아니고, 홀수이거나 K를 2로 나누었는데, A보다 작으면 계속 1로 빼준 코드 end, start = map(int, input().split()) count = 0 while start != end: if start .. 2023. 2. 10.
[Python] 백준 1083 소트 🧑‍💻 [Python] 백준 1083 소트 Gold 5 - 그리디 문제풀이 최대한 제일 큰 숫자가 앞으로 와야 한다 숫자의 움직임에 제한이 있다 일단 swap만큼의 숫자들을 슬라이스를 통해 슬라이스 안에 제일 큰 숫자를 가지고 온다 그리고 i까지, 뒤로 그 큰 숫자를 앞으로 가지고 온다 이것을 swap이 0이 될때까지 반복을 한다 코드 N = int(input()) array = list(map(int, input().split())) swap = int(input()) for i in range(N): max_num = max(array[i : i + swap + 1]) max_num_index = array.index(max_num) for j in range(max_num_index, i, -1):.. 2023. 2. 1.
[Python] 백준 2212 센서 feat. Shark_상어 https://wlgustlra.tistory.com/ 🧑‍💻 [Python] 백준 2212 센서 Gold 5 - 그리디 문제풀이 센서들을 내림차순으로 정렬을 한다 그리고 센서들 사이의 거리를 계산해서 새로운 리스트에 넣는다 그 리스트를 오름차순으로 정렬을 하고, 세울 수 있는 집중국에서 1을 뺀만큼, 리스트에서 거리를 빼준다 거리를 빼면, 해당 센서는, 자기 자신만의 집중국을 가지는 것이 코드 censor_num = int(input()) center_num = int(input()) censors = list(map(int, input().split())) censors.sort(reverse=True) # 설치할 수 있는 집중국이 센서보다 많거나, 같으면, # 각 센서에게 집중국을 설치하면 된다 i.. 2023. 1. 29.
[Python] 백준 1783 병든 나이트 🧑‍💻 [Python] 백준 1783 병든 나이트 Silver 3 - 그리디 나이트는 무조건 오른쪽으로 움직이는 것을 핵심적으로 생각하면 된다 즉 if문에는 1번부터 4번까지 한번씩 사용을 못 하는 경우들을 넣는다 문제풀이 위의 내용을 if문을 통해 해결을 하면 된다 코드 import math N, M = map(int, input().split()) if N == 1: print(1) elif N == 2: print(min(4, int(math.ceil(M/2)))) elif M 2023. 1. 29.
[Python] 백준 1026 보물 🧑‍💻 [Python] 백준 1026 보물 Silver 4 - 그리디 A는 재배열이 가능하고, B는 재배열을 하면 안 된다고 하지만, 둘 다 정렬을 해야 한다 A는 오름차 순으로, B는 내림차 순으로 정렬을 해야 한다 문제풀이 A는 오름차순으로 B는 내림차순으로 정렬을 한다 즉 나중에 같은 인덱스끼리 곱할 때, A의 작은 수는 B의 큰 수와 곱한다 그리고 그것을 나중에 다 더하면 최소 값이 된다 코드 N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort() B.sort(key=lambda x: -x) answer = 0 for i in range(N): answer += A[i] * B[.. 2023. 1. 27.
[Python] 백준 1339 단어 수학 🧑‍💻 [Python] 백준 1339 단어 수학 Gold 4 - 그리디 문자열들이 주어진다 문자열들의 알파벳에 숫자를 배정해서, 더해서 최대 수를 만드는 것이다 A에 9를 배정했으면, 모든 문자열에 A가 들어가 있으면, 그 A들은 9이다 문제풀이 문자열을 어떻게 딕셔너리에 넣어서, 어떻게 숫자를 배정할지 많이 고민을 했다 알파벳들이 십의 몇번째 자리인지 찾고, 그 자리에 따라서 내림차순으로 9부터 배정하는 것이다 각 단어들의 알파벳들을 딕셔너리에 넣는다 여기서 10 ** (times - 1)을 하여서, 해당 알파벳이 몇 번째 자리인지 value로 넣는다 그리고 다 구했으면 딕셔너리의 값들을 리스트로 변환해서, 내림차순으로 정렬을 한다 정렬한 리스트를 순회하면서 9부터 내려가면서 곱해주고, result에 .. 2023. 1. 26.

티스토리툴바