[코드트리] Greedy(탐욕 알고리즘) 약점 극복 학습 후기

목차

 

1. 2회차 미션 확인

1-1. 이번 회차 미션: 차근차근 약점 집중 돌파

• 2회차 미션의 핵심은 내 약점 유형을 직접 골라 레슨 1개 이상을 완료하는 것이다.
• 1회차에서 갭체크 진단을 통해 Greedy(탐욕 알고리즘)가 "불안정한 지식" 영역으로 분류되었기 때문에, 이번 회차에서는 Greedy 챕터를 집중 학습하기로 결정했다.
• 진단 결과를 바탕으로 추천된 챕터는 여기에서 확인할 수 있다.

2. 코드트리 커리큘럼 구조 확인

2-1. 레슨 단위 학습 구조: 기본 - 연습 - 테스트

• 코드트리의 가장 큰 특징은 기본 - 연습 - 테스트의 3단계 구조로 문제를 학습할 수 있다는 점이다.
• 기본 문제: 하나의 개념과 하나의 문제가 1:1로 짝을 이루도록 구성되어 있다. 개념 설명을 읽은 직후 바로 문제에 적용할 수 있어서, 이론과 실습 사이의 간격이 거의 없다.
• 연습 문제 / 테스트 문제: 해당 레슨에서 학습한 모든 개념이 함께 제공되며, 여러 개념을 복합적으로 적용하는 연습을 한다.

2-2. 타 서비스와의 비교

항목	코드트리	백준 / 프로그래머스
학습 구조	개념 - 기본 - 연습 - 테스트 단계별 제공	문제만 제공, 개념 설명 없음
약점 진단	갭체크로 유형별 약점 진단 가능	별도 진단 기능 없음
해설 제공	개념 설명 - 모범 코드 - 토론 제공	커뮤니티 풀이에 의존
학습 방향 제시	진단 결과 기반 추천 챕터 안내	스스로 문제 선택

• 백준이나 프로그래머스에서는 "어떤 문제를 풀어야 할지"를 스스로 결정해야 했다. 반면 코드트리는 갭체크 진단 결과를 기반으로 추천 챕터를 제시해 주기 때문에 방향을 잃지 않고 학습을 이어갈 수 있다. (백준은 현재 서비스 종료함)

3. Greedy 레슨 학습 후기

3-1. Greedy 알고리즘

• Greedy(탐욕 알고리즘): 현재 상황에서 가장 최선인 선택을 반복하여 전체 최적해를 구하는 방식이다.
• 코드트리 레슨에서는 Greedy를 처음 소개할 때 동전 거슬러주기 문제를 예시로 사용한다. 1, 4, 5원짜리 동전으로 8원을 거슬러줄 때, 단순히 큰 동전부터 사용하면 5 + 1 + 1 + 1로 4개가 되지만, 실제 최솟값은 4 + 4로 2개다.
• 이 예시를 통해 Greedy가 항상 최적해를 보장하지는 않는다는 점을 먼저 인식하게 된다. Greedy가 유효한 경우는 "현재의 최선이 전체의 최선임을 증명할 수 있을 때"다.

3-2. 레슨에서 배운 문제 패턴

• 회의실 준비 문제: Greedy 레슨에서 가장 인상 깊었던 문제다. 끝 시간 기준 오름차순 정렬이라는 하나의 선택 기준만으로 최적해가 도출된다는 사실이 처음에는 직관적으로 와닿지 않았다.
  • 코드트리는 정답 접근법을 바로 알려주지 않고, 시작 시간 기준 정렬 / 구간 길이 기준 정렬 / 끝 시간 기준 정렬 순으로 각각의 반례를 하나씩 보여줬다.
  • 이 방식 덕분에 "왜 끝 시간 기준으로 정렬해야 하는가"에 대한 근거가 명확하게 잡혔다.
• 연속 부분 합의 최댓값: 합이 음수가 되는 순간 구간을 끊고 다음 원소부터 다시 시작하는 패턴이다. O(N) 시간 복잡도로 해결 가능하다는 점이 인상적이었다.
• 레슨을 통해 어떤 정렬 기준이 유효한지 반례로 직접 검증하는 사고방식을 갖게 되었다.

4. 직접 푼 문제: 자연수 M/2개의 쌍

4-1. 문제 설명

• M개의 자연수를 두 개씩 짝지어 M/2개의 쌍을 만들 때, 두 수의 합이 가장 큰 쌍의 합 C의 최솟값을 구하는 문제다.
• 난이도 80XP / 평균 풀이 시간 65분 / 정답률 41%로, Greedy 레슨 안에서도 난도가 있는 문제에 속한다.

4-2. 아이디어: Greedy + 투 포인터

• C(최댓값)를 최소화하려면, 가장 큰 수와 가장 작은 수를 짝짓는 것이 직관적으로 떠오른다. 이것이 이 문제의 Greedy 핵심 아이디어다.
• 오름차순 정렬 후 왼쪽 포인터(작은 값)와 오른쪽 포인터(큰 값)를 좁혀가며 짝을 만든다. 이 과정에서 매칭 가능한 수(matchCount)만큼 count를 차감하고, count가 0이 되는 순간 해당 포인터를 이동한다.
• 같은 값이 여러 개 있는 경우를 처리하기 위해 (count, value) 쌍으로 입력을 관리하는 것이 이 문제의 포인트다. 값을 그대로 배열에 풀어 넣으면 count가 매우 클 경우 시간 초과가 발생한다.

4-3. 풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    static class NumberInfo implements Comparable<NumberInfo> {
        long count;
        long value;

        public NumberInfo(long count, long value) {
            this.count = count;
            this.value = value;
        }

        @Override
        public int compareTo(NumberInfo o) {
            return Long.compare(this.value, o.value);
        }
    }

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

        NumberInfo[] numbers = new NumberInfo[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long count = Long.parseLong(st.nextToken());
            long value = Long.parseLong(st.nextToken());
            numbers[i] = new NumberInfo(count, value);
        }

        // value 기준 오름차순 정렬
        Arrays.sort(numbers);

        int left = 0;
        int right = n - 1;
        long maxC = 0;

        while (left <= right) {
            // 왼쪽 포인터와 오른쪽 포인터가 만난 경우: 같은 값끼리 짝
            if (left == right) {
                if (numbers[left].count > 0) {
                    maxC = Math.max(maxC, numbers[left].value * 2);
                }
                break;
            }

            long matchCount = Math.min(numbers[left].count, numbers[right].count);
            long currentSum = numbers[left].value + numbers[right].value;

            // 현재 쌍의 합으로 최댓값 갱신
            maxC = Math.max(maxC, currentSum);

            // 매칭된 만큼 개수 차감
            numbers[left].count -= matchCount;
            numbers[right].count -= matchCount;

            // 개수가 0이 된 포인터 이동
            if (numbers[left].count == 0) left++;
            if (numbers[right].count == 0) right--;
        }

        System.out.println(maxC);
    }
}

4-4. 풀이 과정에서 헤맸던 부분

• 처음에는 입력값이 (개수, 값) 형태로 주어진다는 점을 간과하고 값을 배열에 직접 풀어 넣는 방식으로 접근했다. count가 10억 단위일 수 있기 때문에 이 방식은 메모리 초과로 이어졌다.
• left == right인 경우: 같은 값끼리 서로 짝을 지어야 하는 상황이다. 이 케이스를 별도로 처리하지 않으면 오답이 발생한다.

import java.io.*;
import java.util.*;

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().trim());

        List<Long> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long count = Long.parseLong(st.nextToken());
            long value = Long.parseLong(st.nextToken());

            // count만큼 value를 직접 추가
            for (long j = 0; j < count; j++) {
                list.add(value);
            }
        }

        Collections.sort(list);

        int left = 0;
        int right = list.size() - 1;
        long maxC = 0;

        while (left < right) {
            long currentSum = list.get(left) + list.get(right);
            maxC = Math.max(maxC, currentSum);
            left++;
            right--;
        }

        System.out.println(maxC);
    }
}

import java.io.*;
import java.util.*;

public class Main {
    static class NumberInfo implements Comparable<NumberInfo> {
        long count;
        long value;

        public NumberInfo(long count, long value) {
            this.count = count;
            this.value = value;
        }

        @Override
        public int compareTo(NumberInfo o) {
            return Long.compare(this.value, o.value);
        }
    }

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

        NumberInfo[] numbers = new NumberInfo[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long count = Long.parseLong(st.nextToken());
            long value = Long.parseLong(st.nextToken());
            numbers[i] = new NumberInfo(count, value);
        }

        Arrays.sort(numbers);

        int left = 0;
        int right = n - 1;
        long maxC = 0;

        while (left <= right) {

            long matchCount = Math.min(numbers[left].count, numbers[right].count);

            long currentSum = numbers[left].value + numbers[right].value;
            maxC = Math.max(maxC, currentSum);

            numbers[left].count -= matchCount;

            numbers[right].count -= matchCount;

            if (numbers[left].count == 0) left++;

            if (numbers[right].count == 0) right--;
        }

        System.out.println(maxC);
    }
}

5. 마무리

• Greedy는 "가장 좋아 보이는 것을 고르면 되지 않나?"라는 생각에서 출발하지만, 반례를 만나는 순간 무너지는 알고리즘이다. 그 경계를 직접 확인하고 이해하는 과정이 이번 회차 학습의 핵심이었다.
• 코드트리의 개념 설명은 단순히 정답 접근법을 알려주는 것이 아니라, 틀린 접근 - 반례 - 올바른 접근 순으로 구성되어 있어 이해의 깊이가 달랐다. 이 방식 덕분에 문제를 틀리더라도 "왜 틀렸는지"를 스스로 납득할 수 있었다.
• 다음 회차에서는 갭체크에서 "부족한 지식"으로 분류된 Shortest Path(다익스트라) 챕터로 넘어갈 예정이다.

📎 코드 트레일로 이동하기

📎 갭체크 추천 챕터 확인하기