오늘은 주말동안 못한 todolist 만들기와 알고리즘 문제 풀기를 진행하였다.
알고리즘 문제는 내배캠에서 백준 문제를 줬는데 프로그래머스 데브캠프를 준비하고 싶어서 프로그래머스 문제로 옮겨왔다.
푸는 중 두 큐 합 구하기에서 탐욕법으로 답은 구해지는데 자꾸 시간초과가 나서 뭐지 하고 튜터님하고 생각해봤는데 javascript라서 생기는 문제라고 한다.
탐욕법을 쓸 때 split을 사용했는데 배열의 맨 앞읠 빼내며 뒤에 있던 배열의 값들을 한칸씩 땡기는 동작이 있어 배열이 길어지면 길어질 수록 더욱 많은 시간이 소요되는 것이다.
튜터님도 아니 왜 이런식으로 만들었지? 할 정도로 비효율인 것 같다.
다른 방법을 찾아서 한번 해봐야겠다.
탐욕 알고리즘(Greedy Algorithm)
선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.
- 최적해를 구하는 데에 사용되는 근사적인 방법
- 여러 경우중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
- 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장이 없다.
문제 해결 방법
- 선택절차 : 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로돌아가 위의 과정을 반복한다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.
탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용할 수 있다.
ex)
1. 손님의 물건 가격은 4,040원. 손님은 계산을 하기 위해 5,000을 냈고 거스름돈의 동전 개수를 최소한으로 달라고 하였다.
- 거스름 돈 960원을 채우기 위해 먼저 500원 한개
- 100원 4개, 50원과 10원 하나씩
탐욕 알고리즘 적용
- 선택절차
- 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택
- 적절성 검사
- 선택절차를 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사.
- 초과하면 가장 마지막에 선택한 동전을 삭제하고, 돌아가 한단계 작은 동전을 선택
- 해답 검사
- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사
- 액수가 부족하면 다시 반복
- 물건을 훔치러 누군가의 집에 들어갔다. 가방은 35kg까지의 물건만 담을 수 있고 집엔 4개의 물건이 있다.
- 탐욕 알고리즘을 사용한다면
- 가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.
- 그 다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.
- 이 과정을 반복
- 가방은 35kg까지 담을 수 있고, 그림이 가장 비싸니 그림을 먼저 가방에 담을 수 있다.
- 남는 공간이 5kg밖에 남지 않아 더 훔칠 수 있는 물건이 없다. 그리고 이때 훔친 물건의 총 가치는 그림 하나의 가치와 같은 $3,000이다.
- 만약 그림 대신 컴퓨터와 반지를 가방에 담았다면 어떨까?
- 35kg이 넘지 않으면서 총 가치는 $3,500으로 그림 하나만 훔칠 때보다 더 많은 가치의 물건을 훔칠 수 있다. (즉, 탐욕 알로리즘으로 최적해를 구하진 못했다.)
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.
그러나 도둑의 예와 같이 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다.
따라서 두 가지의 조건을 만족하는 “특정한 상황” 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.
오늘 한 일
프로그래머스 알고리즘 문제 풀기
todolist만들기 (html과 css완성)
