5/1 그리디 알고리즘(Greedy Algorithm)

어제는 그리디 알고리즘에 대해 이론적인 공부와 기초 문제를 풀어봤습니다
오늘은 그리디 알고리즘을 활용한 문제들을 풀어보는 시간을 가졌습니다

문제 링크

잃어버린 괄호 성공

문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력
첫째 줄에 정답을 출력한다.

예제 입력 1
55-50+40

예제 출력 1
-35

예제 입력 2
10+20+30+40

예제 출력 2
100

예제 입력 3
00009-00009

예제 출력 3
0

이 문제는 어떤 식으로 접근해야 최솟값이 나올지 고민했습니다
예제 출력을 보다 보니 빼기보다 더하기를 먼저 하여 큰 값을 만들고 빼면 최솟값이 나오지 않겠냐는 생각을 하게 되었고, 그 방식으로 문제에 접근해봤습니다

import sys
input = sys.stdin.readline

n = input().split('-')  # 입력값을 -기준으로 나눠 저장
num = []

for i in n:  # 분리된 문자열에 대해 반복문 수행
    count = 0  # 각 문자열에서 숫자들의 합을 계산하기 위한 변수 초기화
    m = i.split('+')  # '+'를 기준으로 숫자를 분리하여 리스트로 저장
    for j in m:  # 분리된 숫자들에 대해 반복문 수행
        count += int(j)  # 각 숫자들을 정수형으로 변환하여 더함
    num.append(count)  # 각 문자열의 숫자들의 합을 결과값 리스트에 저장

k = num[0]  # 첫 번째 숫자를 변수 k에 저장
for i in range(1, len(num)):  # 첫 번째 숫자 이후의 숫자들에 대해 반복문 수행
    k -= num[i]  # 첫 번째 숫자에서 다른 숫자들의 합을 뺌

print(k)  # 결과값 출력

예제 1번으로 받은 55-50+40을 예로 들면 -를 기준으로 값을 나눠 55, 50+40으로 나눠줍니다
그 후 다시 50+40을 +를 기준으로 나눈 후 분리된 숫자들로 반복문을 수행합니다
각 숫자를 count라는 변수에 더해주고, 더한 숫자를 num이라는 빈 리스트에 넣어줍니다
첫 번째 수 55를 k에 넣어주고 반복문을 이용해 num 리스트에 있는 값들을 빼주면 최솟값이 나옵니다

문제 링크

신입 사원 성공

문제
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력
각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입력 1
2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

예제 출력 1
4
3

이 문제는 리스트를 어떤 식으로 이용할까를 고민했습니다
서류심사 성적, 면접 성적의 순위를 주면 A의 성적이 다른 B의 성적에 비해 둘 다 부족하다면 무조건 탈락
이 조건에서 선발할 수 있는 신입사원의 최대 인원수를 구해야 하는 문제여서 일단 서류심사, 면접 성적 둘 중 하나를 기준으로 잡고 오름차순으로 리스트를 정렬하고 문제 풀이를 시작했습니다.

# 첫째 줄에 테스트 케이스의 개수 T가 주어진다
# 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N이 주어진다
# 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 주어진다.
# 회사가 선발할 수 있는 신입사원의 최대 인원수를 출력

import sys
input = sys.stdin.readline

T = int(input())  # 테스트 케이스의 개수를 입력 받습니다.

for _ in range(T):
    N = int(input())
    count = 1  # 처음 비교하는 본인
    rank = []
    for _ in range(N):
        grade = list(map(int, input().split()))
        rank.append(grade)
    rank.sort(key = lambda x:x[0])  # 첫 번째 성적 순으로 오름차순 정렬합니다.
    temp = rank[0]  # 가장 높은 등수를 가진 지원자의 등수 정보를 temp에 저장합니다.
    for i in range(1, N):
        if temp[1] > rank[i][1]:  # 만약 temp의 두 번째 성적이 i번째 지원자의 두 번째 성적보다 크면
            count += 1  # count를 1 증가시키고
            temp = rank[i]  # temp를 i번째 지원자로 업데이트합니다.

    print(count)

처음에는 정렬된 리스트에서 서류심사 성적이 1등인 사람보다 면접 성적이 높은 사람을 모두 카운트하면 되겠다 생각해서 코드로 작성했다가 틀렸습니다
반례를 찾아보니 틀린 곳을 찾을 수 있는 반례를 발견하고 temp라는 변수를 이용해 서류심사 성적 1등의 성적을 넣고 반복문을 통해 비교하며 서류심사 성적 1등인 사람보다 면접 성적이 좋은 사람을 찾으면 count를 1 더해주고 찾은 사람의 시험 성적을 temp에 넣어주어 바뀐 성적으로 비교하니 문제가 해결되었습니다

문제 링크

회의실 배정 성공

문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1
4

힌트
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

이 문제는 시작시간과 끝나는 시간이 주어질 때 회의실을 이용할 수 있는 최대 횟수를 찾는 문제입니다
리스트를 어떤 식으로 정렬할까 고민을 많이하고 구글에 검색해보다가 시작시간의 오름차순으로 정렬을 한 뒤, 정렬된 리스트를 다시 끝나는 시간으로 오름차순 정렬해주는 방법을 찾아내서 문제를 풀어보았습니다

# 둘째 줄부터 N + 1 줄까지 각 회의의 정보가 주어지는데
# 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다
# 하루에 할수 있는 회의의 최대 개수를 출력한다
import sys
input = sys.stdin.readline

n = int(input())

meeting = []
for i in range(n):
    time = list(map(int, input().split()))
    meeting.append(time)

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

end_time = 0
count = 0
# 끝나는 시간이 빠른 순으로 정렬한 후 시작시간과 끝나는 시간을 각각 start와 end 변수에 할당
for start, end in meeting:
    # start가 end_time보다 크거나 같으면 회의실을 사용할 수 있으므로 count 변수에 1을 더해줍니다
    if start >= end_time:
        count += 1
        # 회의의 끝나는 시간 end를 end_time 변수에 저장
        end_time = end

print(count)

리스트를 정렬하는 방법만 찾으면 쉬운 문제였습니다
회의가 끝나는 시간과 시작하는 시간을 비교해서 시작하는 시간이 크거나 같으면 count를 +1 해주고 끝나는 시간을 변경해서 다시 다음 회의의 시작 시각과 비교하며 진행하니 문제가 해결되었습니다

동적 프로그래밍을 공부할 때는 점화식을 생각해 접근하는 방식 자체가 어려웠는데, 그리디 알고리즘은 최소한의 아이디어를 떠올리면 해결할 수 있는 문제들이 많아서 조금 편하게 느껴진 거 같습니다
내일도 그리디 알고리즘에 관한 문제를 조금 더 풀어보고 과제로 있는 컴퓨터 시스템에 관한 서적을 읽으며 공부하는 시간을 가질 거 같습니다