0 + 알고리즘(Algorithm)

[알고리즘] 그리디 알고리즘(백준 11047, 1541, 11399, 1931, 1026 -Java)

힘들면힘을내는쿼카 2023. 3. 24. 15:16
728x90
반응형

[알고리즘] 그리디 알고리즘(백준 11047, 1541, 11399, 1931, 1026 -Java)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

 

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

IT기업 코딩테스트 대비를 위한 [자료구조 및 알고리즘 핵심이론 & 관련 실전 문제 풀이 강의] 입니다. - JAVA 편 -, - 강의 소개 | 인프런

www.inflearn.com

 

그리디 알고리즘

 

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 입니다.

현재 상태에서 최선을 선택하다 보면 결국에는 최선의 결과가 나올것이다 라고 가정을 합니다.

 

그리디 알고리즘 핵심 이론

1) 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2) 적정설 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사
3) 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사(해결 못하면 1번으로 돌아간다.)

백준 11047

11047번: 동전 0
대표적인 그리디 알고리즘 문제 입니다.

 

풀이

public class Quiz11047_2 {
    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());
        // 동전 배열
        Integer[] coin = new Integer[n];
        for(int i = 0; i < coin.length; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        int count = 0;
        int mock = 0;
        // 가장 단위가 큰 동전부터 탐색
        for(int i = n-1; i >= 0; i--) {
            // 목표 금액에서 동전으로 나눈다.
            mock = k / coin[i];
            // 몫이 0 이면 동전(coin[i])을 사용할 수 없다.
            if(mock != 0) {
                // 몫 만큼 해당 동전을 사용한다.
                count += mock;
                // 목표 금액(k)에서 동전(coin[i])으로 나눈 나머지로 목표금액(k)을 변경한다.
                k = k % coin[i];
            }
        }
        System.out.print(count);
        br.close();
    }
}

백준 1541

1541번: 잃어버린 괄호
-를 만나면 그 이후에 등장하는 문자열은 다 빼면 최소 숫자가 됩니다.^^

 

풀이

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        // -를 만나기 전에는 다 더하고, -를 만나면 이후에는 다 빼면 된다.

        // -앞 문자열, -뒤 문자열로 나눔
        // 55+10-50+40-30 -> [50+10, 55+40, 30]
        String[] strArr = str.split("-");
        int result = 0;
        // -를 만나면 크기가 2이상인 배열이 된다.
        for(int i = 0; i < strArr.length; i++) {
            int temp = mySum(strArr[i]);
            // 첫 문자열은 더함(-를 만나기 전 문자열)
            if(i == 0) result += temp;
            // 이후 문자열은 뺀다(이후 문자열은 -를 만났기 때문에 빼야한다.)
            else result -= temp;
        }

        System.out.print(result);
    }

    private static int mySum(String s) {
        int sum = 0;
        // +를 기준으로 문자열을 나눈다.
        // 50+40 -> [50, 40] -> 90
        String[] temp = s.split("[+]");
        for(String str : temp) {
            sum += Integer.parseInt(str);
        }
        return sum;
    }
}

백준 11399

11399번: ATM
오름차순으로 정렬한 뒤 배열의 합을 구하고 그 배열의 합을 계속 더하면 해결할 수 있는 문제 입니다.

for(int i = 0; i < time.length; i++) {
    sum += time[i]; // 배열의 합을 구함
    result += sum; // 배열의 합의 합을 구함
}

 

풀이

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] time = new int[n];
        for(int i = 0; i < n; i++) {
            time[i] = Integer.parseInt(st.nextToken());
        }

        // 오름차순 정렬
        Arrays.sort(time);

        int result = 0;
        int sum = 0;
        for(int i = 0; i < time.length; i++) {
            sum += time[i]; // 배열의 합을 구함
            result += sum; // 배열의 합의 합을 구함
        }

        System.out.print(result);
        br.close();
    }
}

백준 1931

1931번: 회의실 배정

처음에는 loop 2개를 사용해서 문제를 해결했으나, 시간초과가 발생했습니다.. ㅠ

백준 1931번 : 회의실배정 - JAVA 자바
회의 종료 시간 기준으로 오름차순 정렬을 해야 해결할 수 있습니다.
최대한 많은 회의를 하기위해서는 종료시간이 빨라야 하기 때문 입니다.
서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 선택을 할 수 있습니다.

 

✅ 이때 주의해야할 점이 있습니다.
바로 종료시간이 같을때 입니다.
예를들어 아래와 같은 입력이 있다고 합시다.

7 7
3 7
1 2

종료시간으로만 오름차순 정렬하면 다음과 같습니다.

1 2
7 7
3 7

정답은 (1, 2) -> (3, 7) -> (7, 7) 이렇게 3이어야 합니다.

하지만 종료시간만으로 오름차순 정렬 한다면
(1, 2) -> (7, 7) 이렇게 2가 됩니다…. (3, 7)이 선택이 안되는 것 이죠..

따라서 종료시간이 같을 때는 시작시간으로 기준으로 오름차순 정렬해야 합니다.

 

풀이

public class Quiz1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 회의 수
        int n = Integer.parseInt(br.readLine());

        /**
         * 각 회의 시간이 겹치면 안됨
         * 회의실 사용할 수 있는 최대 갯수
         */
        List<List<Integer>> table = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            table.add(new ArrayList<>());
        }
        // 회의 시간표 저장
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            table.get(i).add(start);
            table.get(i).add(end);
        }

        // 회의 종료 시간 기준으로 오름차순 정렬
        Collections.sort(table, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                // 종료시간이 같을 경우에는 회의 시작시간 기준으로 오름차순 정렬
                if(o1.get(1) == o2.get(1)) {
                    return Integer.compare(o1.get(0), o2.get(0));
                } else {
                    return Integer.compare(o1.get(1), o2.get(1));
                }
            }
        });

        // 첫 회의를 배정한다.
        // 첫 회의의 끝나는 시간과 다음 회의 시작 시간 비교
        int count = 1;
        // 선두 회의의 끝나는 시간
        int endTime = table.get(0).get(1);
        for(int i = 1; i < n; i++) {
            // 후발 회의의 시작 시간
            int startTime = table.get(i).get(0);
            if(endTime <= startTime) {
                count++;
                // 선두 회의의 끝나는 시간
                endTime = table.get(i).get(1);
            }
        }
        System.out.print(count);
        br.close();
    }
}

백준 1026

1026번: 보물

B배열은 재정렬 하면 안된다고해서 우선순위 큐를 사용해서 문제를 풀었습니다.

 

풀이

public class Quiz1026 {
    public static void main(String[] args) throws IOException {
        // S = A[0] × B[0] + ... + A[N-1] × B[N-1]
        // S 값이 최소가 되게 A를 정렬
        // S가 최소가 되기 위해서는 B의 최댓값과 A의 최솟값을 곱하면 된다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 배열의 크기
        int n = Integer.parseInt(br.readLine());

        // 배열 A
        Integer[] A = new Integer[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        // 배열 A 오름차순 정렬
        Arrays.sort(A);

        // 배열 B
        // B 배열은 재정렬하면 안됨.
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            queue.add(Integer.parseInt(st.nextToken()));
        }

        int result = 0;
        int i = 0;
        while (!queue.isEmpty()) {
            result += A[i] * queue.poll();
            i++;
        }

        System.out.print(result);
        br.close();
    }
}

백준 13305

13305번: 주유소
다음 주유소의 거리만큼 주유를 하다가 가격이 싼 주유소를 찾으면 남은 거리만큼 주유를 하면 됩니다.

 

풀이

public class Quiz13305 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 도시 갯수
        int city = Integer.parseInt(br.readLine());

        // 도로 길이
        // 편의를 위해 도로 마지막은 0을 넣음 따라서 배열의 크기를 city와 동일하게 한다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] roadLen = new long[city - 1];
        for(int i = 0; i < roadLen.length; i++) {
            roadLen[i] = Long.parseLong(st.nextToken());
        }

        // 기름 가격
        st = new StringTokenizer(br.readLine());
        long[] price = new long[city];
        for(int i = 0; i < price.length; i++) {
            price[i] = Long.parseLong(st.nextToken());
        }

        // 처음에는 무조건 기름을 넣어야 한다.
        // 기름이 비싼 곳에서 적게 넣고
        // 기름이 싼곳에 많이 넣으면 된다.
        // 1. 기름이 싼곳을 찾을 때 까지 다음 주유소까지 거리만큼 기름을 넣는다.
        // 2. 기름이 싼곳을 찾으면 남은 목표 거리만큼 기름을 넣는다.

        long result = 0;
        long min = price[0];
        for(int i = 0; i < roadLen.length; i++) {
            // 현재 주유소 기름값이 이전 주유소 기름값 보다 저렴하면
            if(min > price[i]) {
                // 제일 저렴한 기름값 변경
                min = price[i];
            }
              // 저렴한 가격으로 주유하고 다음 주유소로 간다.
            result += (min * roadLen[i]);
        }

        System.out.print(result);
        br.close();
    }
}
728x90
반응형