[WEEK 04] 알고리즘 - 그리디 문제풀이

11047. 동전 0

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

그리디 기초 문제. 가치가 큰 동전을 먼저 사용하여 가장 적은 동전을 사용한다. 문제에서 주어진 동전이 작은 동전의 배수로 이루어져 있기 때문에 이러한 방법을 적용할 수 있다.

import sys

sys.stdin = open("11047_동전 0.txt", "r")
input = sys.stdin.readline

N, K = map(int, input().split())
arr = [int(input()) for _ in range(N)][::-1]
cnt = 0

for num in arr:
    cnt += K // num
    K %= num
    
print(cnt)

---

1541. 잃어버린 괄호

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

문제에서 주어진 덧셈과 뺄셈으로만 이루어진 식을 괄호를 적절하게 배치하여 가장 작은 결과값을 출력하는 문제이다. 문자열에 괄호를 추가하여 eval()을 이용해 수식을 계산하는 방법을 사용하였지만, 수가 0으로 시작하는 경우 예외가 발생하여 결과값 'result'에 순서대로 계산하는 방법을 사용하였다.

import sys

sys.stdin = open("1541_잃어버린 괄호.txt", "r")
input = sys.stdin.readline

# 문제에서 주어진 식을 '-' 부호를 기준으로 나눈다.
arr = input().split('-')
result = 0

# 나누어진 부분을 '+' 부호를 기준으로 나눈다.
for i in arr[0].split('+'):
    # '+' 부호의 앞의 수를 결과값에 더한다.
    result += int(i)

for i in arr[1:]:
    # 괄호에 포함되야 하는 부분을 '+' 부호를 기준으로 나눈다.
    for j in i.split('+'):
        # 괄호 안에 포함되는 값들을 결과값에서 뺀다. 
        result -= int(j)

print(result)

---

1931. 회의실 배정

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

주어진 회의 일정을 회의가 끝나는 시각과 회의가 시작하는 시각 순으로 정렬하는 것이 중요했다. 평소에 좀 더 자세히 알고 싶었던 람다 함수를 사용해 볼 수 있었다. 또한 sort()의 key값을 튜플로 입력하면 입력된 두 개 이상의 인자 순으로 정렬할 수 있다는 점을 알게 되었다.

import sys

sys.stdin = open("1931_회의실 배정.txt", "r")
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
# 회의가 끝나는 시각과 회의가 시작하는 시각 순으로 오름차순 정렬 
arr.sort(key=lambda arr: (arr[1], arr[0]))

cnt = 1
# 첫 회의가 끝나는 시간을 end에 저장
end = arr[0][1]

for i in range(1, N):
    if arr[i][0] >= end:
        cnt += 1
        # 새로운 회의의 끝나는 시각으로 end를 갱신
        end = arr[i][1]

print(cnt)

---

1946. 신입 사원

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

먼저 지원자들의 1, 2차 성적을 포함한 배열을 1차 성적을 기준으로 오름차순 정렬한다. 1차 최고 성적 지원자는 1차 성적만으로 선발 가능 인원에 포함이 된다. 1차 최고 성적 지원자의 2차 성적을 max라는 변수로 설정한다. 2번 지원자부터 2차 성적을 max값과 비교하여 성적이 더 좋은 지원자를 cnt에 추가하고 max값을 i번 지원자의 2차 성적으로 갱신한다.

import sys

sys.stdin = open("1946_신입 사원.txt", "r")
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    arr.sort(key=lambda arr: arr[0])
    
    cnt = 1
    # 1차 최고 성적 지원자의 2차 성적을 max로 설정
    max = arr[0][1]

    for i in range(1, N):
        if max > arr[i][1]:
            # i번 지원자의 2차 성적이 max보다 좋다면 cnt에 1 추가
            cnt += 1
            # i번 지원자의 2차 성적을 max로 설정
            max = arr[i][1]

    print(cnt)

1700. 멀티탭 스케줄링

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

플러그를 뺄 전기용품을 정하는 단계에서 예외 처리 구문을 사용해 볼 수 있었다.

예외 처리 구문은 try-except의 구조로 구성되어 있다.

try:
예외가 발생할 수 있는 코드
except:
예외가 발생할 경우 수행할 코드

정확하게 이해하고 필요한 경우에 사용하면 오류가 발생하는 빈도를 줄일 수 있을 것 같다.

import sys

sys.stdin = open("1700_멀티탭 스케줄링.txt", "r")
input = sys.stdin.readline

N, K = map(int, input().split())
arr = list(map(int, input().split()))
plugged = []

result = 0

# 반복문을 통해 K개의 전기용품의 사용순서를 탐색
for i in range(K):
    # 이미 플러그를 꽂은 전기용품을 사용하는 경우
    if arr[i] in plugged:
        continue
    # 사용 중인 플러그가 N개 보다 작은 경우 plugged에 추가
    if len(plugged) < N:
        plugged.append(arr[i])
        continue
    
    # 사용 중인 플러그를 빼야하는 경우 횟수를 1 추가
    result += 1
    # 플러그를 뺄 전기용품
    unplug = 0
    # 플러그를 뺄 전기용품의 사용되는 순서
    unplug_idx = 0
    
    # 사용 중인 N개의 플러그를 탐색
    for j in range(N):
        try:
            idx = arr[i + 1:].index(plugged[j])
            # j가 더 늦게 사용되는 전기용품인 경우
            if idx > unplug_idx:
                # 플러그를 뺄 전기용품을 j로 변경
                unplug = j
                # 언플러그 인덱스도 j의 인덱스로 변경
                unplug_idx = idx
        except:
            # 이후에 사용되지 않는 플러그가 있는 경우 j로 변경
            unplug = j
            break
    # 사용 중인 unplug 플러그를 i번째 전기용품으로 대체 
    plugged[unplug] = arr[i]

print(result)

아이디어를 떠올려도 그 아이디어를 코드로 구현하는 것이 어렵고 복잡하다. 아직 풀이를 완전히 이해하지 못함.