그리디 알고리즘

조별 토론했던 내용 정리

그리디 알고리즘 vs 브루트포스 알고리즘

• 그리디(모든 경우 탐색x)
• 브루트포스(모든 경우 탐색o)

시간 복잡도 차이

• 그리디: O(n), O(n log n)
• 브루트포스: O(2^n), O(n!)
  -> 브루트포스가 시간 복잡도가 높음

그리디 알고리즘 사용하는 경우?

• 어떤 조건으로 계산을 줄일 수 있을 때

Arrays.sort(arr)에서 arr가 커지면 정렬 시간이 커진다
-> 어차피 first와 second만 구하면 되는 문제라면?

• 큰 값이 first보다 크면 first에 초기화, first와 second 사이면 second에 초기화
  -> O(n)
• 최대 힙 방법
  -> 배열이 클 때 자료구조가 부담스럽더라도 사용하면 좋음 -> k번째로 큰 수, 상위 k개 수 구하는 경우 적합(변수를 미리 선언할 수 없어서?)
  -> O(n log n)

정리

모든 경우의 수를 다 따지는 브루트포스 vs 꼭 필요한(최선의) 선택을 통해 답을 구하는 그리디

그리디의 전제 조건 - 지극히 당연한 논리, 수학적으로 증명된 것을 사용(막연한 추측x)

문제가 그리디로 보이더라도 의심해야 됨
브루트포스로 풀 경우 시간초과날 때 그리디 사용
(테스트 케이스 건수가 엄청 크다, 시간 초과가 예상된다? -> 고려 가능)
잘 모르겠으면 브루트포스로 풀면 됨
(시간초과면 그리디, dp 고려 가능)

그리디 문제는 특정 중요한 코테에 잘 나오지 않는다.
제너럴한 지식을 갖고 있는지를 보려고 하기 때문에 합격을 가르는 코테에서 많이 나오지는 않음.

그래프 알고리즘 = 그리디 알고리즘 (수학적으로 증명됨)

그리디로 해결 못하는 문제

• 시간 복잡도 측면에서 특정 알고리즘을 쓰지 않으면 못푸는 문제들

추가로

이클립스에서 Expressions 쓰면 식에 대한 답 나옴
Variables

---

우리 팀은 조별 시간에 그 날 배운 내용에 관한 알고리즘 문제를 풀기로 했다.

백준 도서관

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String str = bufferedReader.readLine();
        int N = Integer.parseInt(str.split(" ")[0]); // 책의 개수
        int M = Integer.parseInt(str.split(" ")[1]); // 한번에 들 수 있는 책의 개수

        ArrayList<Integer> positiveBooks = new ArrayList<>();
        ArrayList<Integer> negativeBooks = new ArrayList<>();

        str = bufferedReader.readLine();
        String[] positions = str.split(" ");
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(positions[i]);
            if (num > 0) {
                positiveBooks.add(num);
            } else {
                negativeBooks.add(Math.abs(num));
            }
        }

        Collections.sort(positiveBooks, Collections.reverseOrder()); // 양수는 내림차순 정렬
        Collections.sort(negativeBooks, Collections.reverseOrder()); // 음수는 내림차순 정렬

        int totalSteps = 0;

        // 양수 처리
        for (int i = 0; i < positiveBooks.size(); i += M) {
            totalSteps += positiveBooks.get(i) * 2;
        }

        // 음수 처리
        for (int i = 0; i < negativeBooks.size(); i += M) {
            totalSteps += negativeBooks.get(i) * 2;
        }

        // 가장 먼 거리를 한 번 빼줌
        int maxDistance = 0;
        if (!positiveBooks.isEmpty() && !negativeBooks.isEmpty()) {
            maxDistance = Math.max(positiveBooks.get(0), negativeBooks.get(0));
        } else if (!positiveBooks.isEmpty()) {
            maxDistance = positiveBooks.get(0);
        } else if (!negativeBooks.isEmpty()) {
            maxDistance = negativeBooks.get(0);
        }

        totalSteps -= maxDistance;

        System.out.println(totalSteps);
    }
}