🏀 개요

알고리즘의 기본을 그리드, 탐색, 다이나믹 프로그래밍 3 가지로 잡고 진행하려 함.

가장 첫 번째로 그리드에 대해서 알아보고자 한다.

참고 :
동빈나 유튜브 채널을 기반으로 정리한 것으로, 유튜브 링크를 첨부 하겠습니다.
동빈나 유튜브 링크

💡 접근 방식

그리드는 말 그대로 가장 좋은 방법을 정하고, 그 방법을 우선 순위를 두고 진행하는 방식 입니다.

단, 여기서 가장 좋은 방법에서 예외 케이스가 있는지 판단하는 것이 매우 중요.

실제, 코딩테스트에서.. 그리디인 줄 알고.. 풀었다가 예외케이스 발견 후 멘붕한 경험이 있음. ㅠ

코드를 짜기 전에, 예외 케이스를 다 찾고 진행하자.

예를 들면 거스름 돈 같은 경우는 단위 큰 거 부터 줄여 나가면, 결국 최소 횟수로 거스러 줄 수 있다.

이런 식으로 확실한 케이스도 있다.

🔧 예제 문제 및 장점

그리드를 통해서 문제를 해결한다면, 결국 K 번 그리드를 반복해서 수행하는 것이기 때문에 O(K)라는 시간 복잡도가 나와 성능적으로도 유리하다.

예제 문제는 해커랭커 문제로 접근하였음.

Luck Balance 문제 바로가기

이기면 행운을 쓰고, 지면 행운을 보관하지만 중요도에 따라 반드시 이겨야할 경우가 있다. 이 경우에 행운을 최대화 하는 케이스를 고르는 문제이다.

가장 좋은 방법은 행운의 값이 가장 큰 케이스는 지는 것은 확실하고, 만약 중요도가 높아 이길 경우는 행운 수치가 낮은 케이스에 지는 것이다.
즉, 베스트 방법이 명확하여 그리드로 접근 가능하다.

def luckBalance(k, contests):
    result = 0
    temp = []
    for content in contests:
        if content[1] == 0:
            result += content[0]
        else:
            temp.append(content[0])
    temp.sort(reverse=True)

    for t in temp:
        if k <= 0:
            result -= t
        else:
            result += t
            k -= 1

    return result

이런식으로 접근 했다. sort를 통해 행운이 큰 경우를 우선순위로 두어 진행했다.
모든 테스트 케이스 통과

Greedy Florist 문제 바로가기

사람 수 k와 꽃 수 n을 가지고 최소 가격을 추정하는 문제이다. 사람이 많이 산 경우 그 값이 늘어나게 되서, 적은 가격의 꽃으로 꽃을 사야한다는 가장 좋은 방법이 있어서 그리드로 접근 가능함.

def getMinimumCost(k, c):
	c.sort()
	cost = 0
	idx = 0
	t = 0

	while idx < len(c):
		t = idx // k
		cost += (t + 1) * c[-1 -idx]
		idx += 1

	return cost

이 문제를 풀면서 잘못 생각한 것은 원래 가격이 항상 변경 되는 줄 알았다. 하지만 알고 보니, 곱하는 수만 변경 되는 것을 다른 분의 블로그를 찾아서 알게 되었다. 참고 블로그
cost는 sort한다면, 역순으로 접근시, 가장 큰 값에 접근한다. 즉 처음에는 사는 것을 가장 큰 값으로 정해서 곱하지 않고, 이후에는 곱하는 케이스가 발생하므로, 점차 작은 값을 리스트에서 받아와 더 해준다.

핵심 아이디어는 t= idx//k 라는 방식으로 그리드를 구현했다는 점이다. 결국, 이 아이디어를 발견 해야 이 문제를 풀 수 있다.