이번에 저희 스터디는 그리디(Greedy) 알고리즘에 대해서 공부했습니다.
일단, 그리디 알고리즘이라는 것은 탐욕 알고리즘이라고도 불립니다.
왜 탐욕 알고리즘이냐면, 입력 데이터 간의 관계를 고려하지 않고 수행하는 과정에서 탐욕적이게 최댓값 또는 최솟값을 가진 데이터를 먼저 선택합니다.
즉, 자기로부터 가까운 것밖에 볼 줄 모르는 근시안적인 선택을 해서 부분적인 최적해를 찾고, 이들을 모아서 주어진 문제의 최종적인 최적해를 찾습니다.
이 그리디 알고리즘과 친해지기 위해 알고리즘 문제들을 풀었는데, 그 중에서 릿코드 문제가 저한테는 쉬운 듯하면서 어려웠습니다.
이 릿코드 문제를 대략적으로 설명하자면, 정수들이 저장되어 있는 nums 배열이 주어집니다. 이 정수들은 최대로 점프할 수 있는 것을 의미합니다. 첫 번째 인덱스에서 부터 시작하는데, 첫 번째 인덱스에 저장된 값을 이용하여 다음 인덱스로 점프할 수 있습니다. 예를 들어, 3이 적혀 있으면 최대 3칸까지 다음 인덱스로 이동할 수 있습니다. 이렇게 점프하여 마지막 인덱스에 도착하면 True를 반환하고 도착하지 못하면 False를 반환하도록 합니다.
여러 가지 방법들이 떠올랐지만, 시간 초과나 메모리 초과가 걸릴 것이 분명했어서 다른 방식으로 풀어야 겠다고 생각했습니다.
이걸 어떻게 그리디하게 풀어야 될까 한참 고민하다가 해결 방법이 손에 잡힐듯 안잡혀서 답답하여 다른 분 것을 참고하였습니다.
참고해보니, 정말 쉽게 생각해서 푸셨구나라는 느낌을 받았습니다.
참고한 코드는 다음과 같고, python으로 구현했습니다.
# Leetcode - 55.Jump Game
class Solution(object):
def canJump(self, nums):
jump = 0
for i in range(len(nums)-1):
jump = max(jump, nums[i])
if jump==0 :
return False
jump -= 1
return True일단, 배열의 마지막 인덱스는 목적지이기 때문에 신경 쓸 필요 없으며, 또한 배열에서 값들이 1 이상이 있으면 어차피 마지막 인덱스에 도착하게 될 것입니다.
하지만, 우리가 고려해야 될 것은 배열에 0이 있을 경우입니다.
먼저, 초기에 0이 저장된 jump라는 변수와 배열에 저장된 값을 비교하여 그 최댓값으로 갱신합니다.
만약, 여기서 최댓값이 0이면 더 이상 점프할 수 없기 때문에 False를 반환하고 종료합니다.
그게 아니면, jump 변수의 값을 1 감소시키는데, 이는 바로 다음 인덱스로 이동하기 위함이고, 똑같이 다음 인덱스의 값이랑 현재 최댓값이랑 비교하여 갱신합니다.
즉, 한 번씩 다음 지역에 이동할 때마다 그 지역에 존재하는 점프할 수 있는 최대 연료를 확인하고 계속 교환해주는 방식이라고 생각할 수 있습니다.
최대 연료가 0이면, 목적지에 도착하기 전에 결국 점프할 수 있는 연료가 다 떨어졌다는 의미이고 더 이상 이동할 수 없으니 False를 반환하는 것입니다.
이 문제를 되게 복잡하게 풀 생각을 했는데, 다른 분들이 푸신 것을 보고 어떻게 이런 식으로 짧고 간결하게 코드를 구현하셨을까 감탄했습니다.
