그리디

👉🏻 10775번: 공항import sys; input=sys.stdin.readlinegates = int(input())N = int(input())airplanes = [int(input()) for _ in range(N)]parent = list(range(gates+1))def find(x): if parent[x] == x: return x else: parent[x] = find(parent[x]) return parent[x]def union(x, y): x = find(x) y = find(y) if x != y: parent[x] = ycnt = 0for i in range(N): gate =..

👉🏻 2294번: 동전 2n, k = map(int, input().split())money = [int(input()) for _ in range(n)]dp = [float('inf')] * (k+1)dp[0] = 0for i in range(1, k+1): for coin in money: if i - coin >= 0: dp[i] = min(dp[i], dp[i-coin] + 1)print(-1 if dp[k] == float('inf') else dp[k]) 🤔 왜 이렇게 풀었을까?전형적인 DP 문제입니다. 사실 처음에는 아래처럼 '거스름돈 문제다!!' 생각해서 냅다 그리디로 풀어봤는데, 당연하게도 시간이 초과했습니다.n, k = map(int, inpu..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krdef compress(s, n): result = '' cnt = 1 prev = s[:n] for i in range(n, len(s), n): cur = s[i:i+n] if cur == prev: cnt += 1 else: result += (str(cnt) + prev) if cnt > 1 else prev prev = cur cnt = 1 result += (str(cnt) + prev) if cnt..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krdef convert_time(time): h, m = map(int, time.split(':')) return h * 60 + mdef cal_time(time): total_m = convert_time(time) total_m += 10 h, m = divmod(total_m, 60) return f'{str(h).zfill(2)}:{str(m).zfill(2)}'def solution(book_time): answer, rooms = 0, 0 l = len(boo..

👉🏻 27961번: 고양이는 많을수록 좋다n = int(input())cat = 1cnt = 0if n == 0 or n == 1: cnt = n print(cnt)else: while cat != n: if cat >= n - cat: cat += n - cat cnt += 1 else: cat += cat cnt += 1 print(cnt + 1)단순 그리디 문제로 현재 고양이 수에 따라 while문 내에서 더하는 수를 조절하며 카운트를 늘려주기만 하면 되는 간단한 문제였습니다!

👉🏻 13413번: 오셀로 재배치for _ in range(int(input())): n = int(input()) initial = input() target = input() b_diff = sum(1 for i in range(n) if initial[i] != target[i] and initial[i] == 'B') w_diff = sum(1 for i in range(n) if initial[i] != target[i] and initial[i] == 'W') print(max(b_diff, w_diff))초기 문자열과 목표 문자열 간의 차이를 계산하고, 더 큰 차이를 나타내는 문자의 카운트를 출력하면 됩니다.이것이 가능한 이유는 두 문자의 자리를 바꿔야 하..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krdef solution(storey): answer = 0 while storey: digit = storey % 10 next_digit = (storey // 10) % 10 if digit > 5 or (digit == 5 and next_digit >= 5): answer += (10 - digit) storey += 10 else: answer += digit ..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krdef solution(number, k): stack = [] for num in number: while k > 0 and stack and stack[-1] 저는 그리디 방식을 사용해서 각 숫자에 대해 최적의 해를 구하도록 노력해봤습니다.또한 스택을 이용하여 효율적으로 숫자를 비교하고 제거할 수 있습니다.각 숫자에 대해 스택의 마지막 요소와 비교하는데, 이때 현재 숫자(num)가 더 큰 경우에만 스택에서 숫자를 제거합니다.number를 왼쪽에서 오른쪽으로 순회하므로, 결과적으로는 왼쪽의..