안녕하세요 강사님 정렬에 대해서 설명이 조금 더 듣고 싶습니다.

#include <queue>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N;
vector<vector<int>> n;
vector<int> ch;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    FILE* fp;
    freopen_s(&fp, "input.txt", "rt", stdin);

    cin >> N;
    ch.resize(N, 0);
    for (int i = 1; i <= N; i++) {
        int a, h, w;
        cin >> a >> h >> w;
        n.push_back({ a, h, w });
    }

    //sort(n.begin(), n.end(), [](const vector<int>& a, const vector<int>& b) {
    //    return a[0] > b[0]; });
    int max = 0;
    ch[0] = n[0][1];
    for (int i = 1; i < N; i++) {
        int a1 = n[i][0];
        int h1 = n[i][1];
        int w1 = n[i][2];

        int res = h1;
        for (int j = 0; j < i; j++) {
            int a2 = n[j][0];
            int h2 = ch[j];
            int w2 = n[j][2];

            if (a1 < a2 && w1 < w2) {
                if (h1 + h2 > res) {
                    res = h1 + h2;
                }
            }
        }

        ch[i] = res;
        if (res > max) {
            max = res;
        }
    }

    cout << max;
}

강사님께서도 정렬을 먼저 하고서 알고리즘의 진행을 설명해 주셨는데, 저런식으로 조건을 넣어 줄 경우 정렬을 하지 않아도 상관이 없을 것 같았는데 답이 다르게 나오더군요.
무슨 차이인가요?

안녕하세요, 인프런 AI 인턴입니다.

정렬과 관련된 질문에 대해 알아보겠습니다. 주어진 코드에서는 sort 함수를 사용할 계획이 있는데, 현재 주석 처리되어 있네요. 정렬이 필요한 이유는 특정 조건을 기반으로 적절한 순서로 데이터를 처리하기 위해서입니다.

주어진 코드에서 n 벡터는 가능한 여러 개의 벡터(a, h, w)를 포함합니다. 코드의 목적은 아마도 문제의 요구 사항에 따라 가장 큰 값을 찾는 것이며, 이 과정에서 데이터를 정렬해야 합니다. 주석 처리된 sort는 n 벡터를 첫 번째 요소 a를 기준으로 내림차순 정렬할 것입니다.

왜 정렬이 필요한지:

전처리의 역할: 정렬하지 않고 각 요소를 차례로 비교한다면 불필요한 비교가 많아질 수 있습니다. 정렬은 데이터에 규칙을 주어, 이후 연산에서 논리적 순서가 보장되도록 도와줍니다.
효율성: 예를 들어 정렬된 상태에서는 이전에 처리가 끝난 데이터와의 비교를 통해 중복 계산을 피할 수 있으며, 이로 인해 코드의 효율성이 향상됩니다.
문제의 특성에 맞는 정렬: 이 문제의 경우 a 값에 따라 내림차순으로 수열을 구성하면서 처리 중이며, 이 과정에서 정렬이 필수적입니다. 정렬 후에는 조건(a1 < a2 && w1 < w2)을 만족하는 경우에 대해 필요한 높이(h)를 더해 나가는 것이 알고리즘의 핵심 로직입니다.

따라서, 주석에 있는 정렬을 해제하여 코드를 실행하면 예상한 결과를 얻을 수 있을 것입니다.

추가적으로, 정렬에 대한 이해를 깊이 하도록 하기 위해 다음과 같은 유사한 질문들을 참고하세요:

연산자 오버로딩을 하면 - 정렬에서의 연산자 사용 예시를 볼 수 있습니다.
선생님, 질문이 있습니다. - 정렬을 활용한 다른 방식으로 문제 해결하는 법을 알아볼 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변