그리디: 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.

이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그래도 번역하여 '탐욕 법'으로 소개된다. 이름에서 알 수 있듯이

어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은

'현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다.

 

코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 

'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다.

정렬, 최단 경로 등의 알고리즘 유형은 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다.

 

그리디 알고리즘 유형의 문제는 아주 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다.

사전 지식 없이도 풀 수 있는 문제도 있겠지만, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다. 

 

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고,

문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.

 

실전문제:

1. 큰 수의 법칙 (책 92페이지)

 

내가 푼 답

책의 답 

책의 답에서는 반복되는 수열의 규칙에 대해서 파악하고, 이를 식으로 나타내어 해결을 했다. 

다음에는 이러한 수열 문제를 위와 같이 식으로 나타내어 해결해 보아야겠다.

 

2. 숫자 카드 게임 (책 96페이지)

 

내가 푼 답

min과 max 함수를 이용해서 풀었다. result라는 배열에 각 행에서 가장 작은 수를 넣고 모두 넣은 후, 그 수들 중 가장 큰 수를 출력했다.

책의 답

책에서는 내가 사용하는 방법과는 조금 다르게 min()과 max()함수를 사용했다. 위와 같은 방법도 알아두어야 겠다.

 

3. 1이 될 때까지 (책 99페이지):

내가 푼 답

정말 간단하게 풀었다. 문제에 주어진 조건처럼 나누어 떨어지면 나누고 아니라면 1을 빼는 방법으로 풀었다.

이렇게 간단하게 풀면 시간제한에 걸리지 않을까 싶은 생각이 들었다.

그래서 책에 나와있는 시간 측정 방법으로 측정을 해보았는데, 큰 수를 넣어도 1초를 넘어가지는 않았다.

측정 방법이 잘 못 됐을 수 있지만, 여기에 대해서는 온라인 저지에서 문제를 풀 때 좀 더 정확하게

채점될 수 있기 때문에 일단 넘어가기로 했다. 

 

책의 답: 

책에서는 반복문을 통해 N을 나누고, 더 이상 나눌 수 없을 때 한번에 빼버렸다.

내가 푼 방법보다 이 방법이 확실히 빠를 것이다. 가장 큰 이유는 18번째 줄 때문이라고 생각하는데,

나는 하나하나 빼서 카운트를 하지만 위의 방법에서는 일일이 빼지 않고 카운트를 해버린다.

숫자를 뺄 때, 위와 같은 방법이 더 효율적인 것을 기억해야겠다.