그리디(탐욕) 알고리즘

그리디 알고리즘

• 현재 시점에서 가장 최선의 선택을 반복해서 전체 문제를 해결하는 방식
• 알고리즘의 핵심 아이디어는 매 순간 가장 좋은 선택을 하면 결국 전체 문제에 대해서도 최적의 해결책을 찾을 수 있다는 점
• 다만 이 접근이 항상 최적해를 보장하는 것은 아니다.
• 탐욕적 선택

즉, 문제를 해결할 때 매 단계에서 최적의 선택을 하여 최종적으로 전체 문제에 대한 최적해를 찾으려는 접근 방식이다.

그리디 알고리즘을 적용할 수 있는 조건

1. 탐욕 선택 속성 - 각 단계에서의 최적 선택이 전체 문제의 최적해를 보장할 수 있어야 한다. 즉, 매순간의 최선이 전체적으로도 최선이어야 한다.
2. 최적부분 구조 - 문제를 작은 하위 문제로 쪼갤 수 있고, 각 하위 문제의 최적해가 합쳐져서 전체 문제의 최적해가 되어야 한다.

그리디 알고리즘 예시

• 거스름돈 문제
  • 손님에게 500원, 100원, 50원, 10원짜리 동전으로 거스름돈을 줄 때, 가장 적은 동전 개수를 구하는 문제
  • 가장 큰 단위의 동전부터 최대한 많이 주는 방식으로 거스름돈을 거슬러 주면 가장 적은 동전으로 거스름돈을 줄 수 있음
• 최대 이익을 얻는 배낭 문제
  • 무게와 가치가 다른 물건들을 배낭에 넣을 때, 배낭 최대 용량을 넘지 않으면서 물건들의 가치를 최대화 하는 방법
  • 각 물건의 단위 무게당 가치를 기준으로 정렬 - 가치가 높은 물건부터 최대한 배낭에 넣는 방식으로 문제 해결

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42746

1. 문제 분석

예를 들어, 주어진 정수가 [6, 10, 2]라면 
[6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 
이중 가장 큰 수는 6210입니다.

• 주어진 숫자들을 이어 붙여 가장 큰 수를 만드는 문제
• 숫자들을 순서대로 재배열하고 결과값이 가장 큰 수가 되어야 하며 문자열로 반환해야한다.
• 두 숫자 x와 y를 비교할 때, (x + y)와 (y + x)를 이어붙여 비교

2. 알고리즘 선택

• 더 큰 숫자를 만드는 선택이 항상 전체적으로 최적의 선택이 될 수 있음 → 전체 최적해 보장
• 한번 정렬된 숫자 순서를 바꿀 필요가 없음 → 선택한 숫자가 전체적으로 최적의 해 → 최적 부분 구조
• 이전의 선택을 저장해야하는가?(계산의 중복이 발생하는가?) → no (dp pass)

👉 그리디 알고리즘을 사용하는 것이 적합하다고 볼 수 있다.

3. 구현

function solution(numbers: number[]) {
	const answer = numbers
		.map((num) => String(num))
		.sort((a, b) => (b + a).localeCompare(a + b))
		.join("");

	return answer[0] === "0" ? "0" : answer;
}

1. 숫자열을 문자로 변환
2. 문자열 정렬 (sort) - O(n log n)
3. string array join