Notice
Recent Posts
Recent Comments
Link
05-03 00:47
«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
Tags more
Archives
Today
Total
관리 메뉴

<<개발일지>>

[인프런/Greedy/1.씨름선수] 본문

코딩테스트

[인프런/Greedy/1.씨름선수]

개발하는지호 2024. 3. 20. 00:49

<<풀이>>

 

이 문제는 Greedy 라는 방식을 채택하여 푸는 문제이다. 이를 생각하지 않고 접근 한다면 생각보다 복잡한 형태로 코드가 구성이 되고

 

자칫 시간 복잡도가 N^2가 되므로 시간 초과가가 발생한다.

 

그렇기 때문에 Greedy의 의미인  <<각 선택의 순간에 가능한 최선의 결정을 내려 전체적인 문제 해결 과정을 단순화하고, 결과적으로 문제를 쉽게 풀 수 있는 상태로 만드는 것을 의미합니다.>>

 

여기서는 키를 내림차순으로 만듦으로써 몸무게만 비교하면 되는 형태로 최적화 시켰다.

 

키를 정렬하기 위해서 객체를 정렬해야 하는데, Comparable<>와 compareTo() 를 이용해서 구했다. 

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int solution(Body[] body, int n){
        int max = body[0].w;
        int count = 1;
        for (int i = 1; i < n; i++) {
            if (max < body[i].w) {
                max = body[i].w;
                count++;
            }
        }
        return count;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Body[] body = new Body[n];
        for (int i = 0; i < n; i++) {
            body[i] = new Body(in.nextInt(), in.nextInt());
        }
        Arrays.sort(body);

        System.out.println(T.solution(body, n));
    }
}

class Body implements Comparable<Body> {
    public int h, w;
    Body(int h, int w) {
        this.h = h;
        this.w = w;
    }
    @Override
    public int compareTo(Body o) {
        return o.h - this.h; //내림차순
    }
}

 

-강사님 풀이-

 

강사님은 ArrayList 컬렉션 프레임워크를 사용했으므로 Arrays.sort가 아니라 Collections.sort를 이용했다.

 

나머지는 동일 !!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

class Main {
    private int solution(ArrayList<Body> list, int n){
        int max = Integer.MIN_VALUE;
        int count = 0;
       for (Body body : list) {
           if (body.w > max) {
               max = body.w;
               count++;
           }
       }
        return count;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Body> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add( new Body(in.nextInt(), in.nextInt()));
        }
        Collections.sort(list);

        System.out.println(T.solution(list, n));
    }
}

class Body implements Comparable<Body> {
    public int h, w;
    Body(int h, int w) {
        this.h = h;
        this.w = w;
    }
    @Override
    public int compareTo(Body o) {
        return o.h - this.h; //내림차순
    }
}

 

<<추가 공부>>

 

그리디 알고리즘의 핵심 아이디어는 매 순간 가장 좋은 것만을 선택함으로써, 최종적으로 전체 문제에 대한 해결책이 최적이 되도록 하는 것입니다. 이 접근 방식에서 "최적인 상태를 만든다"는 것은, 각 선택의 순간에 가능한 최선의 결정을 내려 전체적인 문제 해결 과정을 단순화하고, 결과적으로 문제를 쉽게 풀 수 있는 상태로 만드는 것을 의미합니다.

그러나 이 방법이 성공적으로 작동하기 위해서는 두 가지 중요한 조건이 충족되어야 합니다:

  1. 그리디 선택 속성: 알고리즘이 각 단계에서 하나의 최적해를 선택할 때, 이 선택이 최종적으로 전체 문제의 최적해를 보장해야 합니다. 즉, 각 단계에서의 최적의 선택이 전체 문제를 해결하는 데 있어서도 최적임을 의미합니다.
  2. 최적 부분 구조: 문제의 최적해가 해당 문제의 부분 문제들의 최적해로부터 구성될 수 있어야 합니다. 이는 문제를 더 작은 부분 문제로 나누어 해결한 다음, 이러한 부분 문제들의 해결책을 결합하여 전체 문제의 해결책을 도출할 수 있음을 의미합니다.

그리디 알고리즘은 이러한 조건이 충족될 때 효과적이며, 문제에 따라 매우 효율적이고 간단한 해결책을 제공할 수 있습니다. 그러나 모든 문제에 대해 그리디 알고리즘이 최적의 해를 제공하는 것은 아니며, 특정 문제의 특성과 요구 사항에 따라 그리디 알고리즘의 적용 가능성과 효율성이 결정됩니다.

결과적으로, 그리디 알고리즘은 문제를 해결하기 위한 간결하고 직관적인 접근 방법을 제공하지만, 그 적용이 적절한지, 그리고 문제의 요구 조건에 맞는 최적의 해를 실제로 제공하는지는 각각의 문제마다 신중하게 검토해야 합니다.

'코딩테스트' 카테고리의 다른 글

[인프런/Greedy/2. 회의실 배정]  (4) 2024.03.23
[인프런/DP/2.돌다리 건너기]  (5) 2024.03.22
[백준/1010/다리 놓기]  (6) 2024.03.19
[백준/1009/분산처리]  (2) 2024.03.19
[백준/1032/명령 프롬프트]  (5) 2024.03.18
'코딩테스트' Related Articles more