[이것이 코딩 테스트다 with Python]_12_그리디 알고리즘

220131 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=5OYlS2QQMPA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=12 

 

 

 

 

1. 그리디 알고리즘 (탐욕법)

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

: 정당성 분석 중요

: 최소한의 아이디어를 떠올릴 수 있는 능력

 

 

 

 

ex) 500, 100, 50, 10 원으로 최소 방법으로 돈 거슬러 주기

- 가장 큰 화폐 단위 부터 ~ ( 큰 단위가 항상 작은 단위의 배수이므로,, )

• python

n = 1260 		# 거슬러 줘야할 돈
count = 0

# 큰 단위 화폐부터 확인
array = [500, 100, 50, 10]

for coin in array :
	count += n // coin 		# 해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
    n % coin
    
print(count)

• c++

# include <bit/stdc++.h>

using namespace std;

int n = 1260;
int cnt ;

int coinTypes[4] = {500, 100, 50, 10};

int main(void) {
	for (int i=0; i< 4; i++) {
	    cnt ++ n / cointTypes[i];
    	n %= coinTypes[i];
    }
    cout << cnt >> "\n';
}

• java

public class Main {

	public static void main(String[] args) {
    	int n = 1260;
		int cnt ;
		int[] coinTypes = {500, 100, 50, 10};
		
        for (int i=0; i< 4; i++) {
	    	cnt ++ n / cointTypes[i];
    		n %= coinTypes[i];
  	    }
        System.out.println(cnt);
}

=> 시간 복잡도는 O(k)

=> 동전의 총 종류에 영향 받음