그리디 & 구현

💬 해당 포스팅은 나동빈님의 (이코테 2021 강의 몰아보기) 2. 그리디 & 구현 강의를 듣고 요약한 글입니다.

 

 

 

✔ 그리디 알고리즘(Greedy) 이란?

현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

그리디 알고리즘으로 풀 때는 중요한 점이 있는데, 해당 방법의 정당성을 분석하는 것이다. 단순히 가장 좋아 보이는 것만을 반복적으로 선택해도 최적의 해를 구할 수 있는 지 검토해야 한다는 것이다. 

 

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많지만, 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

 

▼ 예) 거스름 돈 문제

동전으로 거스름 돈을 주려고 하는데 500원, 100원, 50원, 10원이 무한으로 있다고 가정한다. 거스름 돈이 N 이라고 할 때, 줄 수 있는 동전의 최소 개수를 구하시오.

예를 들어 위 거스름돈 문제에서 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 만약 800원을 거슬러 줘야 하는데 화폐 단위가 500원, 400원, 100이라면 위 방식은 최적의 해가 아니게 된다. (500원 1개, 100원 3개/400원 2개)

따라서 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 지 검토할 수 있어야 한다.

 

 

✔ 구현(Implementation) 이란?

머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현은 시뮬레이션, 또는 완전 탐색이라고 불리기도 한다.

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 구체적으로는 다음과 같다.

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

 

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용된다. Java에서의 2차원 배열과 비슷한 개념이다. 

 

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

이 때, 동서남북을 다음과 같이 벡터를 정의할 수 있다. dx = {0, 0. 1, -1}, dy = {1, -1, 0, 0} . 이와 같이 다른 방향들도 배열을 사용해서 저장하고 활용할 수 있다.

 

---

위 알고리즘에 대한 문제풀이는 차차 추가할 예정이다!