백준 알고리즘 - 그리디 알고리즘(1931번/1026번/1541번/2217번/13305번/10610번)

그리디 알고리즘이란?

- '현재 상황에서 지금 당장 좋은 것만 고르는 방법'

- 탐욕 알고리즘이라고도 불린다.

 

 

1931번 : 회의실 배정

 

 

문제

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

 

입력

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

 

풀이

num = int(input())

time = [[0]*2 for _ in range(num)]

for i in range(num) :
  first, second = map(int, input().split())
  time[i][0] = first
  time[i][1] = second

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

cnt = 1
end = time[0][1]
for i in range(1, num):
    if time[i][0] >= end:
        cnt += 1
        end = time[i][1]

print(cnt)

 

리뷰

 

가장 중요하게 주목해야 할 부분은 람다를 이용한 정렬 방법과 정렬을 하는 이유일 것 같다.

우선 2차원 배열에서 위와 같이 'key=lambda x : x[0]'과 같은 옵션을 사용하면,

0번째 컬럼 값을 기준으로 오름차순 정렬된다.

 

따라서 

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

이 부분은 0번째 컬럼을 기준으로 한 번,

1번째 컬럼을 기준으로 한 번 더 오름차순 정렬하는 것을 의미한다.

 

이런 식으로 정렬을 하면 시작시간이 빠르고 종료시간이 빠른 순서로 정렬이 된다.

 

여기서 첫 번째 인덱스의 각 값을 첫 시작 시간과 첫 종료 시간으로 볼 수 있고

이후에 종료되는 시간을 기준으로 다음 시작 인덱스를 찾는 로직을 실행해

총 몇 번의 회의가 최대 발생할 수 있는지 계산할 수 있다.

 

 

 

 

 

1026번 : 보물

 

 

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

 

풀이

import sys

a = int(sys.stdin.readline())

array1 = list(map(int, sys.stdin.readline().split()))
array2 = list(map(int, sys.stdin.readline().split()))

result = 0

for i in range(a) :
  result += min(array1)*max(array2)
  array1.pop(array1.index(min(array1)))
  array2.pop(array2.index(max(array2)))

print(result)

 

 

리뷰

이 문제는 다른 사람의 풀이를 보고 풀 수 있었던 문제인데

정답률이 굉장히 높은 편인데 도저히 푸는 방법을 모르겠어서

굉장히 자괴감에 빠졌었다..

 

문제에 접근했던 과정은 답안과 비슷했는데

결과적으로 쓰고 남은 최댓값과 최솟값을 버리는 방법을 몰라서

나름의 방식으로 구현해보려고 했던 것에서 막혔다.

 

알고 보니 쉽게 pop이라는 함수를 쓸 수 있다는 것을 알게 됐다 ㅎㅎ..

pop 함수를 사용할 때 괄호 안에 빼고 싶은 수를 입력하면 될 것 같은데

그게 아닌 list.index(빼려는 값)과 같은 형식으로 써야 한다는 것에 주의해야겠다.

 

 

 

 

 

1541 : 잃어버린 괄호

 

문제

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

 

 

입력

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

 

풀이

답안 1
arr = input().split('-') 

s = 0 

for i in arr[0].split('+'):  
    s += int(i)   

for i in arr[1:]:   
    for j in i.split('+'):
        s -= int(j)

print(s)

답안 2
import sys

a = sys.stdin.readline().strip().split('-')

first_num = 0
first = a[0].split('+')
for i in range(len(first)) :
  first_num += int(first[i])

result = 0

for i in range(1, len(a)) :
  new_array = a[i].split('+')
  for j in range(len(new_array)) :
    result += int(new_array[j])

print(first_num - result)

 

리뷰

여태까지 푼 그리드 알고리즘 중에 가장 오래 고민했던 문제 같다.

대충 어떻게 푸는지는 알겠는데

로직을 짜는 것이 어려웠다.

 

답안 1의 경우 모범 답안이라고 보면 될 것 같고

답안 2는 내가 생각해낸 답안이다.

 

for문에서 배열에서 범위를 길이로 하는 게 익숙해서

습관적으로 그 방식으로 접근했는데

 

모범 답안은 그냥 리스트 배열 요소로 접근하니까

식이 훨씬 깔끔하고 간단해졌다.

 

이런 유연성을 갖추는 것이 중요할 것 같다.

 

 

 

 

 

2217 : 로프

 

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

 

 

풀이

import sys

cnt = int(sys.stdin.readline())

weight_list = []

for i in range(cnt) :
  weight = int(sys.stdin.readline())
  weight_list.append(weight)

weight_list.sort(reverse = True)

for i in range(len(weight_list)) :
  weight_list[i] = weight_list[i]*(i+1)

print(max(weight_list))

 

 

리뷰

아직도 부족하구나를 느끼게 해 준 고마운 문제.. ㅎㅎ

결국 풀이 방식이 맞는 게 중요한데

알고리즘 구현 방식만 고민하다가

제일 중요한 풀이는 계속 틀렸다..

 

접근 방식이 처음부터 잘못됐는데

그게 맞다고 생각하고 구현 방식에만 집중하다 보니

문제는 문제대로 계속 틀리고

시간은 시간대로 잡아먹고

 

알고리즘 문제를 풀 때는

내 접근 법이 어떤 경우에도 맞는 답을 제시하는지

반드시 체크한 후에

구현 방법을 생각해야 할 것 같다.

 

 

 

 

 

13305 : 주유소

 

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.
처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.
예를 들어, 이 나라에 다음 그림(figure 1)처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 
제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.
각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

 

figure 1

 

 

 

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1 이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

 

풀이

from sys import stdin

k = int(stdin.readline())
dist = list(map(int, stdin.readline().split()))
cost = list(map(int, stdin.readline().split()))
res = 0

c = cost[0]
for i in range(k - 1):
    if c > cost[i]:
        c = cost[i]
    res += c * dist[i]

print(res)

 

 

리뷰

풀면서 굉장히 좋은 그리디 알고리즘 문제라는 생각이 들었다.

두 가지 배열을 만들고 기준점으로 활용될 수를 하나 만들어 놓고

하나의 배열의 값만을 이동하는 것이 신박했달까..

 

무슨 말인고하면

처음에는 다른 문제처럼 배열 두 개를 동시에 사용해야 한다고 생각했다.

이중 for문도 사용해보고 하면서 배열 두 개를 동시에 이용했는데

이 문제는 배열 2개를 동시에 사용할 필요가 없었다.

 

지표가 될 값을 처음에 지정해준다.

여기서는 시작 주유소 가격이 지표가 된다.

 

이 가격이 다음 주요소 값보다 작다면 유지하고

거리만큼 곱해서 비용을 더해준다.

 

반대로 이 가격이 다음 주요소 값보다 비싸다면 시작 주요소 가격을 더 작은 값으로 바꿔주면 된다.

이 바뀐 값에 다음 이동해야 할 거리만큼 곱해서 비용을 구한다.

 

이런 접근 방식이 굉장히 좋은 문제라는 생각이 들어서 리뷰

 

 

 

 

 

10610 : 30

 

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어 한다.
미르코를 도와 그가 만들고 싶어 하는 수를 계산하는 프로그램을 작성하라.

 

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

 

풀이

import sys

num = sys.stdin.readline().strip()

array = []
for i in range(len(num)) :
  array.append(int(num[i:i+1]))

array.sort(reverse=True)

if 0 not in array :
  print(-1)
else :
  if int(num) % 3 == 0 :
    for i in array :
      print(i, end='')
  else :
    print(-1)

 

리뷰

처음으로 겪은 시간 초과 🤯🤯

문제를 풀 때 처음 제출한 답은

import sys

num = sys.stdin.readline().strip()

array = []
for i in range(len(num)) :
  array.append(int(num[i:i+1]))

array.sort(reverse=True)

new_num = 0
for i in range(len(array)) :
  check = len(array)-(i+1)
  if check != 0 :
    new_num += array[i]*(10**check)
  else :
    new_num += array[i]

if 0 not in array :
  print(-1)
else :
  if new_num % 30 == 0 :
    print(new_num)
  else :
    print(-1)

 

for문이 많이 쓰이다 보니 시간 초과가 발생한 것 같다.

문자열을 리스트로, 그리고 다시 그 리스트를 숫자로 만들어야 한다는 생각에

로직을 위와 같이 짰는데

 

생각해보니 굳이 숫자로 변환할 필요 없이

입력받은 수가 3으로 나눠지면 확인하면 되는 일이었다.

 

많은 for문의 사용은 시간 초과를 야기한다는 걸 알게 해 준 문제