그리디 알고리즘을 알아보자 . java.python -> 센서, 동전,강의실,파일합치기

그리디 알고리즘의 정의

그리디 알고리즘은 각 단계에서 최선의 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다.

📌 가장 대표적인 예시로 동전이 500원 , 100원 , 50원 ,10원이 충분히 있을때 동전을 최소한으로 사용해서 거스름돈을 주어야한다묜?

예) 650원 기준 → 500원: 1개 , 100원 :1개 , 50원 : 1개
예) 730원 기준 → 500 + 100_2 + 10_3

그리디 알고리즘은 각 단계에서 최선의 선택을하는 방식으로 문제를해결해야하는데

바꿔서 말하면 각단계에서 최선의 선택을 모두 합쳤을때 전체의 최선의 선택과 다르다면 풀이는 성립하지않습니다.

📌 만약 동전이 500원 400원100원이있다고하면

예) 800원 기준은 500_1 + 100_3 과 400*2 는 같은 800원이지만 풀이가 다르고 선택도 다르니 성립하지않습니다.

파이썬 버전 그리디 알고리즘 연습 문제

백준 2212 센서 문제입니다.

# 센서
# https://www.acmicpc.net/problem/2212

import sys
input = sys.stdin.readline

n = int(input())  # 센서 개수
k = int(input())  # 집중국 개수
sensors = list(map(int, input().split()))  # 센서 좌표
sensors.sort()

# 센서 간 거리 리스트 생성 및 내림차순 정렬
dist = list(sensors[i] - sensors[i - 1] for i in range(1, n))
dist.sort(reverse=True)

# 센서 간 거리가 가장 먼 k-1개를 제외하고 나머지 거리의 합 출력
print(sum(dist[k-1:]))

백준 11000 강의실 배정문제입니다.

# https://www.acmicpc.net/problem/11000
#
# 강의실 배정
import heapq

N = int(input())
time = []
for _ in range(N):
    time.append(list(map(int,input().split(' '))))

print(time)
time.sort(key=lambda x : (x[0],x[1])) # 0번순으로 정렬하고 같으면 1번순으로?

print(time)

heap = [time[0][1]] # 힙에 첫 번째 강의의 끝나는 시간을 저장

for i in range(1,N):
    if heap[0] <= time[i][0]:
        heapq.heappop(heap) # 현재 강의의 시작 시간이 지금힙 시작시간 보다 크거나 같으면, 힙에서 해당 시간을 제거
    heapq.heappush(heap,time[i][1]) # 현재 강의의 끝나는 시간을 힙에 추가

print(len(heap)) # 힙의 크기 출력 (필요한 최소 강의실의 수)

자바버전 그리디 연습문제

백준의 동전문제입니다.

public class B11047 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int money = Integer.parseInt(st.nextToken());

        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int ans =0;

        for (int i = n - 1; i >= 0; i--) {
            ans += money / coins[i];
            money %=coins[i];
        }
        System.out.println(ans);
    }

백준의 파일 합치기3 문제입니다.

public class B13975 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine().trim());

        for (int t = 0; t < tc; t++) {
            int n = Integer.parseInt(br.readLine().trim());
            PriorityQueue<Long> file = new PriorityQueue<>();

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                file.add(Long.parseLong(st.nextToken()));
            }

            long ans = 0;
            while (file.size() > 1) {
                long a = file.poll();
                long b = file.poll();
                ans += a + b;
                file.add(a + b);
            }
            System.out.println(ans);
        }

    }
}

느낀점.

각 문제를 읽고 그리디 알고리즘 적으로 생각을 하는 부분이 제일 어려운것같습니다.

딱히 정해져있는 탬플릿 코드가 있는것이아니라

여러 알고리즘을 먼저 습득후 그리디 문제가 나오면 여러 알고리즘중 알맞는것을 가져와 사용하는 연습이 필요할것 같습니다.

그리디 알고리즘을 연습하며 정리했던 레포 입니다.

https://github.com/kimjongha99/codeplus-v2/tree/main/codingTest/3week-assignment/day2