[이것이 코딩 테스트다 with Python]_13_그리디 알고리즘 유형 문제

220131 작성

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

https://www.youtube.com/watch?v=_TG0hVYJ6D8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=13 

 

 

 

 

 

 

 

< 문제1 > 1일 될 때까지

: 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행

: 두번 째 연산은 N이 K로 나누어 떨어질 때만 선택

    1) N에서 1 빼기

    2) N을 K로 나누기

 

: N, K 주어질 때 N이 1이 될 때까지 1 or 2 번의 과정을 수행해야하는 최소 횟수

- 주어진 N에 대해 최대한 많이 나누기

- 1 번보다 2번이 작업 수 많이 줄임

• python

n, k = map(int, input().split())
cnt = 0

while True :
    target = ( n // k ) * k		# k로 나누어진당
    cnt += (n-target)			
    n = target

    if n < k :
        break

    cnt += 1
    n //= k

cnt += (n-1)
print(cnt)

• c++

#include <bits/stdc++.h>

using namespace std;

int n, k;
int cnt = 0;

int main(void) {
	cin >> n >> k;
    while (true) {
    	int target = ( n // k ) * k		# k로 나누어진당
    	cnt += (n-target)			
    	n = target

    	if n < k ;
        	break
            
		cnt ++;
	    n /= k;
    }
	cnt += (n-1);
    cout << cnt << '\n';
}

• java

import javna.util.*;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int cnt = 0;
        
        while(true) {
        	int target = (n/k) * k;
            cnt += (n - target);
            n = target;
            
            if ( n < k )
            	break;
            
            cnt += 1;
            n /= k;
        }
       	cnt += (n-1);
        System.out.println(cnt);
    }
}

 

 

 

 

 

 

 

 

< 문제2 > 곱하기 or 더하기

: 각 숫자가 0~9 로 된 문자열 S 가 주어질 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 X or + 연산자를 넣어

결과적으로 만들어질 수 있는 가장 큰 수 구하기

- + 보다는 X 가 더 크게

- 1 이하면 더하기, 2 이상이면 곱하기

• python

data = input()

result = int(data[0])

for i in range(1, len(data)) :
    num = int(data[i])

    if num <= 1 or result <= 1 :
        result += num
    
    else :
        result *= num

print(result)

• c++

# include <bits/stdc++.h>
using namespace std;

string str;

int main(void) {
	cin >> str;
    long long result = str[0] - '0';
    
    for (int i = 1; i<str.size(); i++); {
    	int num = str[i] - '0';
        if (num <= 1 || result <= 1)
        	result += num;
        else :
        	result *= num;
	}
	cout << result << '\n';
}

• java

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in)l
        String str = sc.next();
        
        long result = str.charAt(0) - '0';
        for (int i = 1; i < str.length(); i++) {
        	int num = str.charAt(i) - '0';
            
            if (num <= 1 || result <= 1)  {
            	result += num;
            
            else :
            	result *= num;
            }
        }
        System.out.println(result);
    }
}

 

 

 

 

 

 

< 문제3 > 모험가 길드

: 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여

: N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 최대값

- 오름차순 정렬 이후 공포도가 가장 낮은 모험가부터 확인

- 현재 그룹 수가 현재 확인하고 있는 공포도보다 크거나 같으면 설정

• python

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0    # 총 그룹수
count = 0     # 현재 그룹 모험가 수

for i in data :
    count += 1
    if count >= i :    # 현재 그룹 모험가 수가 현재 공포도 이상이면 그룹 ㄱ
        result += 1
        count = 0     # 초기화
print(result)

• c++

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> arr;

int main(void) {
	cin >> n;
    
    for (int i = 0; i < n; i++ ) {
    	int x;
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin(), arr.end());
    
    int result = 0;
    int cnt = 0
    for (int i = 0; i < n; i++ ) {
    	cnt += 1;
        if (cnt >= arr[i] ) {
        	result += 1;
            cnt = 0;
        }
    }
    cout << result << '\n';
}

• java

import java.util.*;

public class Main {
	public static int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        for (int i =0; i< n; i++) {
        	arryList.add(sc.nextInt());
        }
        Collections.sort(arrayList);
        
        int result = 0;
        int count = 0;
        for (int i = 0; i<n; i++) {
        	count += 1;
            if (count >= arrayList.get(i)) {
            	resut += 1;
                count = 0;
            }
        }
        System.out.printIn(result);
    }
}