[99클럽 코테 스터디] 19일차 TIL - 과일 장수

오늘의 학습 키워드

</> 탐욕법(Greedy)

공부한 내용 본인의 언어로 정리하기

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;

        Arrays.sort(score);
        
        int row = score.length / m ;
        int[][]box = new int[row][m];      
       
        int index = score.length - 1;
        for(int i =0; i < row; i++){
            for(int j =0; j < m; j++){
                box[i][j] = score[index--];
            }
        }
              
        for(int i = 0; i < row; i++){
            answer += (box[i][m-1] * m);
        }

        return answer;
    }
}

오늘의 회고

오늘의 주제는 탐욕법(Greedy)입니다.
영어 단어 Greedy의 의미처럼 그리디 알고리즘 이란 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 '각 단계에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 입니다.

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

그래서 오늘 문제는 탐욕법의 정의와 같이 최적해를 찾아야 했기 때문에 배열에 제한을 둔 상태로 큰 수부터 차례로 배열에 값을 추가해 (최저사과 점수 * 사과 개수)를 만들 수 있는 가장 큰 값으로 뽑아내야 했습니다.

처음에는 그리디 알고리즘을 검색하면서 이진 탐색 트리가 계속 보이기도 하고 최근 문제가 이진 탐색 트리로 많이 나왔던 것을 보아하니 이진 탐색 트리를 사용해야 하나 싶었지만 당장에 최대한 빨리 풀 수 있을 것 같은 방식으로 풀고 나중에 다른 방법을 추가로 알아봐야겠다는 생각에 배열로 진행을 하게 되었고 그나마 코드의 양을 줄일 수 있는 방법이 무엇일까 생각하다 이차원 배열이 생각나 실행을 하게 되었습니다.

오늘도 코드를 작성하기 전에 어떤 방식으로 진행을 해야 할지 생각하며 주석으로 적어 나갔습니다.
1. 이미 최종 출력값인 answer가 초기화가 되어있고 마지막에 반환받을 준비도 되어있다.
2. 가격의 최대 효율이 되려면 상품가치가 가장 낮은 사과는 우선순위가 뒤로 가야한다.
3. 박스의 갯수는 score.length / m 이 되어야한다.
4. 높은 가치의 사과부터 순서대로 box 배열에 추가해서 각 배열의 가장 마지막 값에다 m(상자당 사과 개수)를 곱해서 모두 더하면 최종 반환해야하는 결과값이 나온다.

이 과정으로 시작을 하였습니다.

class Solution {
    public int solution(int k, int m, int[] score) {
        //최종 출력값 int answer 초기화
        int answer = 0;
        
        //사과 점수 오름차순 정렬
        //box를 2차원 배열로 생성 (행은 사과의 갯수 / m == 박스개수);
        //제일 큰 값부터 뽑아서 박스를 만들면 최대의 효율이 가능
        //마지막으로 반복해서 모두 더한 값을 출력
        //큰값부터 생성했기 때문에 배열 제일 마지막에 있는 사과가 가장 점수가 낮은 사과
        //행의 갯수만큼 반복해 (최저 점수 * 사과 개수)를 answer에 더함

    	//마지막으로 반복해서 모두 더한 값을 출력
        return answer;
    }
}

사과 점수를 내림차순 정렬을 해서 앞에서부터 값을 가져오는것보다 오름차순 정렬을 한 상태에서 배열의 마지막 값부터 가져오는게 더 간단하다고 생각해 오름차순 정렬을 하였습니다

Arrays.sort(score);

그리고 box의 배열을 여러개로 따로 만드는 것보다 2차원 배열로 생성하면 한번에 관리하기가 쉬워 만들었습니다.
최대 행은 ( 사과 갯수 / 상자의 사과 갯수)가 되어야 했고 열은 한 상자당 들어갈 수 있는 사과의 갯수가 되어야 했습니다.

int row = score.length / m //나중에 행의 갯수만큼 반복을 해야하므로 미리 행 자체를 만들어 놓음
int[][]box = new int[row][m]box;

아까 말한대로 가장 큰 값인 배열의 마지막 값부터 추가해주면 최대 효율을 낼 수 있습니다.

int index = score.length-1;

for(int i = 0; i < row; i++){
	for(int j = 0; j < m; j++){
    	box[i][j] = score[index--];
    }
}

이렇게 박스가 완성이 되었으니 행 만큼 반복해 모든 값을 (최저 점수 * 사과 개수)로 구해 더해야 했습니다.

for(int i = 0; i < row; i++){
	answer += (box[i][m-1] * m)
}

그리고 모두 더했으니 마지막으로 반환만 해주면 완성입니다.

return answer

추가 회고:

AI가 2번째로 개선 해준 코드를 봤을 때 정렬을 한 리스트에서 상자의 길이 만큼의 인덱스 자체를 가져와서 곱해주는 것은 생각을 못했던 것 같다. 이와 같은 경우로 한다면 불필요한 리스트 생성과 추가적인 데이터 구조를 사용하지 않고 정렬되어 있는 배열에서 직접 계산하여 메모리 효율성도 높다. 문제를 풀 때 조금 더 간단하고 직관적으로 생각을 해서 구성하는 과정을 추가 해보아야겠다.

AI 코드리뷰

현재 코드의 장점

1. 정렬 후 처리: 입력된 점수 배열을 정렬한 후 상자를 채우는 방식은 직관적입니다. 배열을 정렬하여 높은 점수부터 상자를 채우고, 마지막으로 상자 내 가장 낮은 점수를 기준으로 총합을 계산하는 방식은 문제의 요구사항을 정확히 반영하고 있습니다.

2. 간결한 구현: 코드가 비교적 간결하고, 문제를 명확하게 해결하는 방식으로 작성되었습니다. 특히, 점수를 계산하는 부분에서 상자의 최하위 점수만을 사용하여 빠르게 계산할 수 있습니다.

현재 코드의 단점

1. 불필요한 2차원 배열 사용: box라는 2차원 배열을 사용하여 점수를 재배열한 후, 다시 그 배열을 순회하는 것은 비효율적입니다. 2차원 배열 대신 단순히 정렬된 점수를 역순으로 순회하면서 계산하면 메모리와 시간을 절약할 수 있습니다.

2. 유연성 부족: 이 코드에서는 상자에 반드시 m개의 점수를 넣어야 합니다. score.length % m이 0이 아닌 경우, 남은 점수를 처리하지 못할 수 있습니다. 이런 경우를 대비해 코드가 좀 더 유연하게 작성될 필요가 있습니다.

   • 개인적인 생각: 이 부분에 대해서는 팔지 못하는 사과는 계산할 필요가 없으므로 상관없다고 생각합니다.

시간 복잡도

• 정렬: Arrays.sort(score)는 평균적으로 O(n log n)의 시간 복잡도를 가집니다.
• 상자 채우기 및 계산: 이 부분은 O(n)의 시간 복잡도를 가집니다. 왜냐하면 배열을 순회하면서 점수를 상자에 채우고, 합계를 계산하는데, 두 과정 모두 O(n) 시간이 걸리기 때문입니다.

개선된 코드 제안 (재귀적 풀이)

이 문제를 이진 탐색 트리(Binary Search Tree, BST)를 사용해 재귀적으로 풀 수 있는 방법을 생각해 볼 수 있습니다. 하지만 이 문제의 요구사항을 충족하기 위해 굳이 BST를 사용할 필요는 없습니다. 이유는 다음과 같습니다:

• BST의 장점: BST는 삽입, 탐색, 삭제 연산이 평균적으로 O(log n)의 시간 복잡도를 가지므로, 동적 데이터 관리에 유리합니다. 또한 특정 범위 내의 데이터를 빠르게 찾는 데 유리합니다.

• BST의 단점: 이 문제에서는 정렬된 배열에서 상자 내의 최소값을 찾고, 그 값을 곱한 결과를 계산하는 것이기 때문에, BST의 범위 탐색 기능이나 삽입 기능이 크게 유리하지 않습니다. 오히려 BST를 사용하게 되면, 추가적인 메모리 사용과 구현 복잡도만 증가할 수 있습니다.

재귀적 접근:
재귀적 접근으로 문제를 풀려면, 현재 문제에서 구하려는 값을 작은 문제로 쪼개고, 작은 문제를 해결하는 방식으로 접근할 수 있습니다. 하지만 이 문제에서 재귀적으로 접근하는 것은 불필요하게 복잡도를 증가시킬 수 있습니다. 예를 들어 다음과 같은 코드가 가능합니다:

import java.util.Arrays;

class Solution {
    public int solution(int k, int m, int[] score) {
        Arrays.sort(score);
        return calculate(score, score.length - m, m);
    }

    private int calculate(int[] score, int index, int m) {
        if (index < 0) {
            return 0;
        }
        return score[index] * m + calculate(score, index - m, m);
    }
}

개선된 버전의 장점:

1. 재귀적 사고: 문제를 작은 문제로 쪼개서 해결하는 재귀적 사고를 훈련할 수 있습니다.
2. 간결성: 재귀적 접근은 코드의 간결성을 가져올 수 있습니다.

개선된 버전의 단점:

1. 비효율성: 재귀는 함수 호출마다 스택 메모리를 사용하므로, 호출이 깊어지면 메모리 사용이 증가합니다.
2. 오버헤드: 반복적인 함수 호출로 인해 오버헤드가 발생할 수 있습니다.

시간 복잡도:

재귀적 풀이의 시간 복잡도는 비재귀적 풀이와 동일하게 O(n log n)입니다. 이는 정렬에 의해 결정됩니다.

개선된 코드 제안 2

import java.util.Arrays;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;

        // 1. 점수를 오름차순으로 정렬합니다.
        Arrays.sort(score);

        // 2. 뒤에서부터 m개씩 그룹화하여 상자 만들기
        int length = score.length;
        for(int i = length - m; i >= 0; i -= m){
            // 3. 각 상자의 최소 점수 * 상자 당 사과 개수 = 상자의 이익
            answer += score[i] * m;
        }

        return answer;
    }
}

장점

1. 효율적인 구현:
   사과 점수 배열을 정렬한 후, 뒤에서부터 상자를 만드는 방식은 이익을 최대화하는 효과적인 방법입니다. 이는 문제에서 요구하는 최대 이익을 정확히 계산할 수 있습니다.
   O(n log n)의 정렬 후 O(n)의 루프를 통해 최대 이익을 계산하므로, 성능 면에서도 매우 효율적입니다.

2. 간결한 코드:
   코드가 간단하고 직관적입니다. 정렬 후 순회하면서 상자 단위로 계산을 진행하므로 로직을 이해하기 쉽습니다. 추가적인 메모리 사용 없이 주어진 배열만으로 문제를 해결합니다.

3. 최적화된 메모리 사용:
   2차원 배열 등 추가적인 데이터 구조를 사용하지 않고, 정렬된 배열에서 직접 계산하므로 메모리 효율성이 높습니다.

단점

1. 정렬 과정의 시간 소모:
   정렬을 필수적으로 사용하기 때문에, 정렬 과정에서 O(n log n)의 시간이 소모됩니다. 이로 인해 입력이 매우 큰 경우, 정렬이 성능의 주요 병목이 될 수 있습니다. 그러나, 문제의 입력 범위 내에서는 효율적입니다.

2. 이해를 위한 가정 필요:
   문제의 특성상 사과의 점수가 낮은 사과를 무시하는 것이 최적의 결과를 가져오며, 이는 코드에서 가정하고 있지만, 이런 부분을 명시적으로 이해하고 넘어가야 합니다.

시간 복잡도

• 정렬: Arrays.sort(score)에서 사용하는 정렬 알고리즘의 시간 복잡도는 평균적으로 O(n log n)입니다. 이 알고리즘은 Java의 Dual-Pivot Quicksort를 사용하는데, 최악의 경우에도 O(n log n)의 성능을 보장합니다.

• 이익 계산: 정렬된 배열을 뒤에서부터 순회하면서 상자를 만드는 과정의 시간 복잡도는 O(n)입니다. 이는 상자에 필요한 m개의 사과를 반복해서 선택하는 작업입니다.

• 종합 시간 복잡도: 전체 알고리즘의 시간 복잡도는 정렬에 의한 O(n log n)이 가장 큰 부분을 차지하며, 이 후의 연산은 O(n)으로, 최종적으로 O(n log n) 입니다.

---

내일 공부할 것 :

1. 자료구조와 알고리즘 복습: 특히 정렬 알고리즘(퀵 정렬, 병합 정렬 등)과 이진 탐색 트리의 기본 개념을 복습.
   BST에서의 삽입, 삭제, 탐색의 시간 복잡도에 대해 명확히 이해하고, 어떻게 동적 데이터 구조로 활용할 수 있는지 생각하기

2. 메모리 관리 및 최적화: 메모리 관리에 대한 이론과, 자바에서 메모리 최적화를 어떻게 할 수 있는지에 대해 공부
   특히 불필요한 객체 생성의 비용과, 재귀 호출의 메모리 사용 공부하기

3. 재귀와 반복: 재귀적 접근과 반복적 접근의 장단점을 비교해보고, 각 방법을 적용할 때의 기준을 공부
   Tail recursion (꼬리 재귀) 최적화에 대해 알아보기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135808