본문 바로가기

알고리즘/그리디10

[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] 백준 12931 두 배 더하기 🧑‍💻 [Python] 백준 12931 두 배 더하기 Gold 5 - 그리디 제일 중요하게 생각해야 하는 것은 B에서 배열 A를 만드는 것이다 즉 B에 있는 원소들을 다 0으로 만들어야 하는 것 즉 B에서 값 하나씩 1을 빼는 것 그리고 B에서 모든 값을 2로 나눠서 0을 만드는 것으로 반대로 생각하면 된다 문제풀이 최소를 구하는 것이니깐 모든 값을 2로 나누는 것을 먼저 생각한다 for문을 통해, 모든 숫자가 숫자 % 2 == 0 로 떨어지면, count에 1을 더한다 그리고 for문을 순회할 때에, 각 숫자들을 2로 나눈 것을 temp 리스트에 넣는다 그리고 만약에 for문을 아무 문제 없이 순회를 했다면, temp리스트를 B로 업데이트 한다 반대로 위에서 for문을 통해 순회를 했는데, 홀수를 구한.. 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.
[Python] 백준 1439 뒤집기 🧑‍💻 [Python] 백준 1439 뒤집기 Gold 5 - 그리디 문자열은 0과 1 밖에 없다 연속된 숫자들을 뒤집는 것이고, 최소한으로 뒤집는 것이 목표 즉 0000011111000001100 은 01010 과 똑같다 문제풀이 (처음 풀이, 틀림) one , zero라는 변수를 만들어 0으로 초기화 시켰다 문자열을 순회하며, 문자열이 바뀔 때 마다, 1이면 one에 1을 더하고, 0이면 zero에 1을 더했다 경우의 수 one이 0이고, zero가 0일 때에, 숫자를 뒤집지 않아도 되서 0을 출력 one만 0이면 zero 값인 1을 출력 zero만 0이면, one 값인 1을 출력 zero와 one이 0이 아니면, 둘 중에 작은 것을 출력 문제풀이 (두번째) 000001110000110110 은 010.. 2023. 1. 25.
[Python] 백준 1138 한 줄로 서기 🧑‍💻 [Python] 백준 1138 한 줄로 서기 Gold 4 - 그리디 입력값은 서있는 사람의 기준으로 왼쪽에, 자신보다 키가 큰 사람의 숫자를 의미한다 예) 키가 1인 사람 왼쪽에는 자신보다 큰 사람이 6명이 있다 문제풀이 result의 0의 개수를 세면서, index + 1 즉 키를 넣어주면 된다 코드 N = int(input()) result = [0] * N for index, num in enumerate(list(map(int, input().split()))): cnt = 0 i = 0 while True: if result[i] == 0 and cnt == num: result[i] = index + 1 break elif result[i] == 0: cnt += 1 i += 1 pri.. 2023. 1. 25.

티스토리툴바