[Coding Test] inflearn(7)

1. 그리디 (Greedy)

그리디 알고리즘은 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.

주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.

근시안적 방법론이란?
단기적인 목표를 중심으로 한 전략적인 접근 방법을 의미합니다. 이 방법론은 주로 현재의 문제를 해결하는 데 초점을 맞추며, 장기적인 전망보다는 단기적인 성과를 중요시합니다.

그리디 알고리즘의 단계

1. 문제의 최적해 구조를 결정합니다.

2. 문제의 구조에 맞게 선택 절차를 정의합니다 : 선택 절차(Selection Procedure)

3. 선택 절차에 따라 선택을 수행합니다.

4. 선택된 해가 문제의 조건을 만족하는지 검사합니다 : 적절성 검사(Feasibility Check)

5. 조건을 만족하지 않으면 해당 해를 제외합니다.

6. 모든 선택이 완료되면 해답을 검사합니다 : 해답 검사(Solution Check)

7. 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

2. 그리디 실전 문제

동전 0 (백준 11047)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class P11047_동전0 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        ArrayList<Integer> al = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            al.add(Integer.parseInt(st.nextToken()));
        }
        int count = 0;
        while (K != 0) {
            for (int i = al.size() - 1; i >= 0; i--) {
                if (K >= al.get(i)) {
                    count += K / al.get(i);
                    K = K % al.get(i);
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

잃어버린 괄호 (백준 1541)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1541_잃어버린괄호 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String example = br.readLine();
        String[] str = example.split("-");
        int answer = 0;
        for (int i = 0; i < str.length; i++) {
            int temp = mySum(str[i]);
            if (i == 0) answer += temp;
            else answer -= temp;
        }
        System.out.println(answer);
    }

    public static int mySum(String a) {
        int sum = 0;
        String[] str = a.split("[+]");
        for (int i = 0; i < str.length; i++) {
            sum += Integer.parseInt(str[i]);
        }
        return sum;
    }
}