20240130 이것이 코딩 테스트다 챕터3(그리디)

그리디 알고리즘

단순하지만 강력한 문제 해결 방법.
어떤 문제가 있을 때 단순 무식하게 문제를 푸는 알고리즘.
현재 상황에서 지금 당장 좋은것만 고르는 방법. 따라서 매 순간 가장 좋아보이는 것을 선택하여 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형임.

기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해줌. 또한 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됨.

대표적인 그리디 알고리즘 문제 유형은 최소 동전 개수를 구하는 거스름돈 문제인데, ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주면 된다는 아이디어에서 그리디 문제 유형임을 알 수 있다.
한가지 더 생각할 점은 이 아이디어로 문제의 해법을 찾았을 때 그 해법이 정당한지인데, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없어 이 해법이 정당하다고 판단할 수 있다.

%=

파이썬에는 등호를 이용한 다양한 할당연산자가 존재함.
+=. -=만 있는 것이 아니라 %=도 가능임.

할당연산자	의미
=	a = b
+=	a = a+b
-=	a = a-b
*=	a = a*b
/=	a = a/b	-> 왼쪽 변수에 오른쪽 값을 나누고 그 결과를 왼쪽 변수에 할당.
%=	a = a%b	-> 왼쪽 변수에 오른쪽 값을 나눈 후 그 나머지를 왼쪽 변수에 할당.
//=	a = a//b	-> 왼쪽 변수에 오른쪽 값을 나눈 후 그 몫을 왼쪽 변수에 할당.
**=	a = a**b	-> 왼쪽 변수에 오른쪽 값을 제곱하고 그 결과를 왼쪽 변수에 할당.