[2025 1학기 알고리즘 스터디] 김민주 #3주차

알고리즘 스터디 3주차 : 그리디 알고리즘

 

1. 회의실 배정

https://www.acmicpc.net/problem/1931

---

💡문제 분석 및 알고리즘 설계

가장 대표적인 그리디 문제인 회의실 배정은 최초 아이디어만 떠올리면 구현하기는 어렵지않은 것 같습니다.

(근데 이제 처음에는 절대 생각안나는 ㅠㅡㅠ)

저는 이미 풀이 방법을 알고있어서 바로 구현해봤습니다.

 

회의 시작시간과 끝나는 시간을 pair로 갖도록 배열을 생성하고,

끝나는 시간을 비교해서 최대 회의가 가능하도록 알고리즘을 설계했습니다.

 

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

int n, a, b;
int num =1;
pair <int,int> arr[100001];

int main(){
    cin >> n;

    for (int i=0; i<n; i++){
        cin >> a >>b;
        arr[i] = {b,a};
    }
    sort(arr, arr+n);

    int f = arr[0].first;

    for (int i=1; i<n; i++){
        if (f <= arr[i].second){
            num +=1;
            f = arr[i].first;
        }
    }
    cout << num;
}

---

 

2. 잃어버린 괄호

https://www.acmicpc.net/problem/1541

---

💡문제 분석 및 알고리즘 설계

연산 식에 괄호를 추가해야하는 이 문제는 파이썬으로 풀었습니다

지금 자료구조 재수강....... 중이라 파이썬으로 스택, 큐 등을 구현하면서

이런 연산 문제들에 많이 익숙해졌기 때문입니다 ㅜ_ㅜ

 

그리디인만큼 모두 연산할 수 있도록 길이만큼 for문을 돌아줍니다.

 

n = str(input())
data = n.split('-')

nums = []

for i in data:
    sum = 0
    tmp = i.split('+')
    for j in tmp :
        sum += int(j)
    nums.append(sum)

num = nums[0] 

for i in range(1,len(nums)) :
    num -= nums[i]
print(num)

---

 

3. 동전 0

https://www.acmicpc.net/problem/1931

---

💡문제 분석 및 알고리즘 설계

동전 개수의 최소값을 구하는 문제입니다.

이 문제가 그리디인걸 몰랐다면 다른 방법을 찾기위해 헤맸을거 같은데

그리디인걸 알고 푸니까 오히려 생각안하고 for문을 돌도록 한 것 같습니다.

 

#include<iostream>
using namespace std;

int coin[10];
int n, k;
int cnt = 0;

int main(){
	cin >> n >> k;

	for (int i = 0; i < n; i++){
		cin >> coin[i];
	}
    
	for (int i = n-1; i >= 0; i--){
		if (coin[i] <= k){
			cnt += k /coin[i]; 
			k %= coin[i];
		}
	}
	cout << cnt;
}