SK네트웍스 Family AI 캠프 1기 2주차 알고리즘 스터디

SK Networks AI Camp

알고리즘 스터디 - 2주차

---

안녕하세요
1주차 알고리즘 스터디 글 이후로 2달이 지나고 나서야 2주차 알고리즘 스터디 글을 작성하네요.
그 사이에 스터디는 계속 진행해왔는데 블로그 글을 정리할 시간이 없어서 뒤로 미루다보니 여기까지 미루게 됐습니다..
지금부터라도 시간 날 때마다 지난 스터디 내용을 정리해서 올려보도록 할게요!
2주차 알고리즘 스터디 주제는 그리디(Greedy) 알고리즘이었습니다.

그리디(Greedy)란?

그리디 알고리즘은 문제를 해결하는 과정에서 매 순간 최적이라고 생각되는 선택을 하는 알고리즘입니다. 그리디는 현재 상황에서 가장 좋은 선택만 진행하면서 결과에 도달하게 되는데, 그 과정에서 지역적으로 선택된 최적의 값이 전역적으로 최적의 결과를 도출할 수 있는지 주의하면서 풀이를 진행해야합니다.

위와 같은 그래프에서 최댓값을 찾기 위해 항상 최댓값을 선택하는 그리디 알고리즘은 최적의 결과를 보장하지 않습니다!
또한, 이전에 선택한 결과가 이후 선택에 영향을 주지 않아야 그리디 알고리즘을 사용할 수 있으니 이 부분도 유의해주세요!
아래에 간단한 예제를 통해 그리디 알고리즘의 사용법을 알아보도록 합시다.

예 제

동전 거스름돈 문제

동전의 종류는 500원, 100원, 50원, 10원이 있다고 할 때, 거스름돈으로 줄 수 있는 최소 동전의 개수를 구하라.

입력 예시: 760
출력 예시: 4

그리디를 이용해서 위의 문제를 해결한다면, 아래와 같은 절차를 거치게 됩니다.

1. 가장 큰 단위의 동전부터 최대한 많이 사용합니다.
2. 나머지 금액에 대해 다시 가장 큰 단위의 동전부터 최대한 많이 사용합니다.
3. 위의 과정을 반복합니다.

이 과정을 반복하면 맞는 결과에 도달할 수 있는지 예시를 통해 확인해봅시다.

1. 760원에서 500원을 최대한 사용합니다. 1개 사용. 남은 금액 260원
2. 260원보다 작으면서 가장 큰 금액인 100원을 최대한 사용합니다. 2개 사용. 남은 금액 60원
3. 60원보다 작으면서 가장 큰 금액인 50원을 최대한 사용합니다. 1개 사용. 남은 금액 10원
4. 10원 하나를 사용하면 거스름돈을 전부 돌려줄 수 있습니다. 1개 사용. 남은 금액 0원

위와 같이 작동하면 필요한 동전 개수는 4개가 되고 4개보다 적은 개수로는 거스름돈을 돌려줄 수 없다는 것을 알 수 있습니다. —

연습 문제

• 세탁소 사장 동혁
  2720번 문제 링크
  위의 거스름돈 문제와 동전의 유형만 다른 유사한 문제입니다.

T = int(input())

for _ in range(T):
    x = int(input())
    ans = [0, 0, 0, 0]
    ans[0] += x // 25
    x %= 25
    ans[1] += x // 10
    x %= 10
    ans[2] += x // 5
    x %= 5
    ans[3] += x
    print(*ans) 

• 수리공 항승
  1449번 문제 링크
  일단 물이 새는 곳의 위치를 오름차순으로 정렬하고, 앞에서부터 테이프를 붙이면 됩니다.
  이 때, 주의해야할 점은 앞에서 붙인 테이프가 이미 뒤의 물 새는 곳까지 막고 있다면 그 곳에는 테이프를 새로 붙이지 않고 지나가도 된다는 것입니다.

import sys

n, l = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()

tmp = arr[0] - 0.5
result = 1

for i in range(1, n):
    if arr[i] + 0.5 > tmp + l:
        result += 1
        tmp = arr[i] - 0.5

print(result)

• 회의실 배정
  1931번 문제 링크
  그리디 + 정렬을 이용하는 유명한 문제입니다.
  정렬을 이용한다는 것 자체가 힌트가 될 수 있는데, 종료 시간이 빠른 것부터 오름차순으로 회의를 정렬하고 지금 선택한 회의가 끝나는 시간보다 다음 회의의 시작 시간이 늦거나 같다면 다음 회의를 지금 선택한 회의로 바꾸어주면 됩니다.

import sys

N = int(sys.stdin.readline().strip())
arr = []

for _ in range(N):
    arr.append(tuple(map(int, sys.stdin.readline().strip().split())))

arr.sort(key=lambda x: (x[1], x[0]))

ans = 1
now = arr[0]

for i in range(1, N):
    if now[1] <= arr[i][0]:
        now = arr[i]
        ans += 1

print(ans)

더 궁금한 내용이 있다면, 댓글 남겨주세요!
감사합니다.