목록Greedy (3)
나의 개발일지
문제 : https://www.acmicpc.net/problem/24337 🔑 a, b를 만족하는 건물 먼저 세우기 n, a, b = 10, 6, 3 일 때 1 ~ a-1까지 건물을 먼저 짓는다. [1, 2, 3, 4, 5] 그다음 가장 높은 건물을 짓는다. max(a, b) = 6 [1, 2, 3, 4, 5, 6] b-1 ~ 1까지 건물을 마저 짓는다. [1, 2, 3, 4, 5, 6, 2, 1] 10개를 세워야 하는데 8개의 건물이 세워져 있다. 건물 2개를 현재 만족하고 있는 조건을 해치지 않고 추가해야 한다. 출력되는 숫자를 가장 작게 만들기 위해서는 1을 왼쪽 편에 추가해야 한다. 하지만 가장 왼쪽에 1을 추가하는 것이 아닌 1번 인덱스에 추가해야 한다. n, a, b = 10, 1, 9 일 ..
문제 : https://www.acmicpc.net/problem/1417 그리디, 최대 힙 사용 from heapq import heapify n = int(input()) dasom = int(input()) heap = [-int(input()) for _ in range(n-1)] # 최대 힙 구현을 위해 -를 붙여 저장 cnt = 0 heapify(heap) if n == 1: print(0) exit() while dasom
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42883 Greedy Stack 현재 위치 값(p)과 이전 값(p-1)을 비교해서 이전 값이 더 작으면 빼준다. 제거 횟수(k)가 남아있으면 완성된 스택에서 남아있는 제거 횟수만큼 제일 뒤의 값을 빼준다. def solution(number, k): num = list(map(int,number)) # 문자열을 정수 리스트로 변환 stack = [] # 스택 리스트 p = -1 # 스택 포인터(위치) for i in range(len(num)): stack.append(num[i]) # 스택에 요소 추가 p += 1 # 스택 위치 증가 if p >= 1: # 스택에 두 개 이상 있을 때 wh..