코딩 테스트/그리디3 그리디(greedy) - 주유소 1. 문제 해결의 아이디어 ① 최소 비용 계산 -> 가장 싼 값의 기름을 최대한 많이 사야함 ② 계산 방식 - 문제 상황 그대로 접근 : 주어진 기름값 목록에서 최솟값을 찾고, 그 도시에서 목적지까지 가는 데 필요한 기름을 그 가격으로 몽땅 구입하는 식으로 계산. - 그리디 알고리즘 : 도시를 하나씩 지나가며 그 도시의 가격과 이전 도시의 가격을 비교해서 당장 싼 가격으로 다음 도시로 가는데 필요한 기름만 사는 식으로 계산. 2. 소스 코드 - 문제 상황 그대로 접근 - 그리디 알고리즘 3. 평가 - 처음에 문제 상황 그대로 구현을 했더니 시간 초과가 났다. 최대로 주어질 수 있는 도시 개수가 10억 개라서 최솟값 계산에 인덱스 계산 등을 반복하니 시간복잡도가 치솟은 듯. - 뒤늦게 반복문으로 그냥 도시.. 2021. 7. 29. 그리디(greedy) - 볼링공 고르기 1. 문제 해결을 위한 아이디어 ① 공 두 개를 고르는 모든 경우에서, 무게가 같은 공 두 개를 고르는 경우를 뺀다. ② 공 무게 리스트의 맨 처음 공부터 기준으로 해서 무게가 다른 조합을 전부 비교해서 구한다. ③ 무게가 가장 작은 공부터 기준으로 해서 그와 다른 무게의 공을 고르는 경우의 수를 구한다. 2. 소스 코드 아이디어 ① 아이디어 ② 아이디어 ③ 3. 메모 - 아이디어 ①, ②를 구현한 코드는 공의 개수가 늘어날수록 소요 시간이 늘어남. → 주어지는 데이터의 수에 따라 시간 복잡도가 어떻게 변하는지 따져보는 것이 중요함. 2021. 7. 26. 그리디(greedy) - 만들 수 없는 금액의 최솟값 1. 문제 해결의 아이디어 만들 수 없는 최솟값을 찾으려면 가장 작은 값부터 만들 수 있는지 없는지를 확인하면 된다. 따라서 입력 받은 동전을 작은 단위 순으로 정렬하고 하나씩 꺼내면서 목표 금액(target)을 만들 수 있는지 확인하는 작업을 반복한다. 동전의 단위가 자연수이므로, 확인해야 할 금액은 1부터 시작한다. 따라서 target을 1로 정하고 동전을 꺼내기 시작한다. 만약 꺼낸 동전의 단위가 1보다 크면 1을 만들 수 없으므로 1이 답이된다. 만약 꺼낸 동전의 단위가 1이면 1을 만들 수 있으므로 target을 2로 변경한다. 다음에도 마찬가지로 꺼낸 동전의 단위가 2보다 크면 2를 만들 수 없으므로 2가 답이된다. 만약 꺼낸 동전의 단위가 2 이하, 즉 1 또는 2이면 target을 만들 수.. 2021. 7. 25. 이전 1 다음
