TIL 135일차 : 그리디 알고리즘 쉽게 이해하기

 

✏️도전한 점

---

1. 알쿼리즘 : 11399번: ATM (acmicpc.net)

2. 이력서 수정

 

01 그리디 알고리즘이란?

---

💡 그리디 알고리즘은 쉽게 <가장 큰 쿠키 먼저 고르기>라는 예시에서 살펴볼 수 있다.

 

- 내 앞에 다양한 크기의 쿠키🍪들이 한 접시에 담겨있다고 상상해보자. 나는 배가 많이 고픈 상태이고, 가능한 한 많은 쿠키를 빨리 먹고 싶다. 하지만, 한 번에 하나의 쿠키만 고를 수 있다. 어떤 쿠키를 먼저 고를 것인가?

 

- 그리디 알고리즘은 <매 순간 최선의 선택을 한다>는 아이디어에서 비롯됐다. 위의 경우에는 가장 큰 쿠키를 먼저 고르는 것이 답일테다. 왜냐하면, 이 방법이 나의 배를 가장 빨리 채울 수 있는 방법이기 때문이다. 그래서 나는 가장 큰 쿠키를 먼저 골라 먹고, 그 다음으로 큰 쿠키를 골라 먹고, 이런 식으로 계속 쿠키를 고르게 된다.

 

- 그리디 알고리즘이란 바로 이렇게, 각 단계에서 가장 좋아 보이는 선택을 하는 것을 말한다. 이 방법이 항상 가장 좋은 결과를 주는 것은 아니지만, 많은 경우에서 충분히 좋은 해결책을 제공해 준다.

 

- 요약하자면, 배가 고플 때 가장 큰 쿠키부터 먹는 것처럼, 문제를 해결할 때도 매 순간 가장 좋아 보이는 선택을 하는 것이 그리디 알고리즘의 방식이다.

 

02 문제 풀이

---

🔎문제 발생 : 예시의 숫자를 하나씩 총 6회 input을 주는 방법으로 착각해서  분명 답이 잘 나오는데도 불구하고 런타임 에러가 발생했다. 여태 시간초과는 발생해봤어도 런타임 에러는 처음이라 풀이 자체가 문제가 있음으로 추측했다.

 

이때 작성한 코드이다.

answer = [int(input()) for i in range(int(input()))]
answer.sort()
result = []
added = 0
for i in answer:
    if len(result) == 0:
        result.append(i)
    else:
        result.append(added+i)
    added += i
print(sum(result))

🔎문제 해결 : input()은 총 2회 입력으로 '5'와 '3 1 4 3 2'를 입력하면 해결됐다.

 

people = int(input())
answer = sorted(map(int, input().split()))
result = 0
added = 0

for i in answer:
    result+= i+added
    added += i

print(result)

🔎최적화 : 결국 sum하는 문제라 result를 빈리스트에서 0으로 바꾸고 그때그때 연산하는 코드로 바꿨다. if조건문을 없애서 속도가 더욱 빨라졌다.

 

✨ 후기 및 인사이트 : 매순간 최선의 선택을 하기 위해 정렬을 해서 같은 조건을 맞췄다.

1. sorted 함수는 정렬된 새로운 리스트를 반환한다.
2. map(함수, 시퀀스)가 기본 코드형식이고 시퀀드는 리스트나 튜플을 말함.
3. 주어진 함수를 시퀀스의 모든 항목에 적용하고, 그 결과를 map 객체로 반환하는 멋진 함수!
4. map객체를 list로 변환해야 하는데 sorted써서 생략했다.

 

result = answer.sort()
result # 결과 None

💡 주의 : answer.sort()는 직접 변환하는 메소드라 result에 아무것도 담기지 않는다.