교안 p131 질문 있습니다

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

해결된 질문

작성

148

수정됨

안녕하세요 큰돌님 😀

교안 p131의 'x를 1순위로 오름차순으로 정렬하고 y가 2순위로 내림차순 z가 3순위로 오름차순 정렬이라는 문제'의 예제 코드에서

struct Point
{
    int x, y, z;

    Point(int y, int x, int z) : y(y), x(x), z(z) {}

    Point()
    {
        y = -1;
        x = -1;
        z = -1;
    }

    bool operator<(const Point &a) const
    {
        if (x == a.x)
        {
            if (y == a.y)
                return z < a.z; // 3순위 : z가 오름차순
            return y > a.y; // 2순위 : y가 내림차순
        }
        return x < a.x; // 1순위 : x가 오름차순
    }
};

operator< 오버로딩 부분에서 오름차순, 내림차순이 어떻게 정해지는 것인지 정렬 로직이 궁금합니다.

검색해보았더니 operator< 가 Point 내부에서 자체적으로 정렬을 시킨다고 했는데,

그럼 operator< 매개변수로 들어오는 a가 어떻게 들어오게 되고 정렬을 어떻게 시키는 건지 이해가 안갑니다..ㅜㅜ

예를 들어서 Point의 지역변수 x, y, z와 a의 x, y, z를 비교했을 때, x < a.x가 false이면 자리를 바꾸는 것인가요..?ㅠㅠ 로직 자체가 이해가 안 갑니다.

그리고 Point 구조체를 만드실 때 변수를 y, x 순으로 받으시는 것도, 이렇게 하면 더 편리한 이유가 있는건지 질문드리고 싶습니다!

감사합니다.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

그럼 operator< 매개변수로 들어오는 a가 어떻게 들어오게 되고 정렬을 어떻게 시키는 건지 이해가 안갑니다..ㅜㅜ

>> 이부분은 sort의 원리인데요. 참고로 최신 교안을 다운 받으시면 다음 부분을 볼 수 있습니다.

sort()의 원리

sort()는 각각의 요소들을 cmp함수가 true 가 뜨는 “요소들의 순서”로 바꿔줍니다.

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
return a < b;
}
vector<int> v = {3, 10, 4, 11};
int main(){
sort(v.begin(), v.end(), cmp);
for(int i : v) cout << i << " ";
}

예를 들어 {3, 10, 4, 11}이 있다고 했을 때

10과 4는 a < b가 false이기 때문에 이를 바꿔서 4, 10으로 만들고 다른 요소들도 그런지를 확인합니다.

이런 과정들을 반복해서 {3, 4, 10, 11}이라는 집합을 만듭니다. 즉, 모든 요소들이 a < b라는 조건식을 충족시키는 집합으로 만드는 것이죠.

예를 들어서 Point의 지역변수 x, y, z와 a의 x, y, z를 비교했을 때, x < a.x가 false이면 자리를 바꾸는 것인가요..?ㅠㅠ 로직 자체가 이해가 안 갑니다.

>> 네 맞습ㄴ디ㅏ. false면 바꾸고 모든 요소들이 true값을 가지도록 바꾸는 것입니다.

그리고 Point 구조체를 만드실 때 변수를 y, x 순으로 받으시는 것도, 이렇게 하면 더 편리한 이유가 있는건지 질문드리고 싶습니다!

>> 구조체 - y, x는 취향입니다. clain님 원하시는대로 만드시면 됩니다. 다만 x, y보다는 y, x가 더 좋은 이유는 교안내의 for문을 y부터 걸고 그다음에 x를 거는게 효율성이 더 좋아서 그런데 교안내의 해당 부분 참고부탁드립니다.

2차원배열과 탐색을 빠르게 하는 팁

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

Clain

질문자

설명해주셔서 감사합니다. 설명해주신 내용은 전부 이해되었습니다!!

그런데 혹시

#include <bits/stdc++.h>
using namespace std;
struct Point
{
    int y, x;
    Point(int y, int x) : y(y), x(x) {}
    Point()
    {
        y = -1;
        x = -1;
    }
    bool operator<(const Point &a) const
    {
        return x < a.x;
    }
};
priority_queue<Point> pq;
int main()
{
    pq.push({1, 1});
    pq.push({2, 2});
    pq.push({3, 3});
    pq.push({4, 4});
    pq.push({5, 5});
    pq.push({6, 6});
    cout << pq.top().x << "\n";
    return 0;
}

위의 예제코드에서 pq에 push 하면서 Point가 들어가는데 어떻게 Point 안에 있는 operator< 함수가 동작하는 건지 궁금합니다..

그러니까 Point 내부의 operator< 메서드가 어떻게 매개변수로 Point &a를 받는 건지 이해가 안됩니다.

예를 들어서, {1, 1}과 {2, 2}는 Point 구조체이지만 서로 다른 내부?를 갖고 있고 연결되는 게 없는데 어떻게 operator< 가 매개변수로 받아서 비교하고 자리를 바꾸는 건지 이해가 안됩니다..ㅜㅜ

설명해주시면 감사하겠습니다!

큰돌

지식공유자

이렇게 생각하시면 됩니다.

우리가 a < b라는 걸 기준으로 3 2 1 4를 1 2 3 4로 정렬을 하죠?

근데 이게 만약에 복잡한 구조체들.

{3, 1}, {2, 3} ... 이런 것들로 이루어졌는데 < 라는 걸 한다고 칩시다.

어떻게 해야할까? 라는 것이죠.

이 때 그걸 정의를 하는게 필요하고 < 라는 오퍼레이터 를 설정해야 합니다.

    bool operator<(const Point &a) const
    {
        return x < a.x;
    }

앞의 코드를 보시면 {}.x를 기준으로 < 를 정의한 것을 볼 수 있습니다. 이를 기반으로 정렬을 하는 것입니다.

Point 내부의 operator< 메서드가 어떻게 매개변수로 Point &a를 받는 건지 이해가 안됩니다.

>> 비교대상자인 point 타입의 매개변수를 계속해서 받아 operator < 라는 함수가 계속해서 호출되면서 -> sort가 이뤄진다고 보시면 됩니다. (내부적으로)

좀 더 자세히 설명하자면 아래의 과정이 계속해서 일어납니다.

현재 객체(*this)의 x 좌표와 매개변수로 받은 객체 a의 x 좌표를 비교합니다.
만약 현재 객체의 x 좌표가 a 객체의 x 좌표보다 작다면, true를 반환합니다. 그렇지 않다면 false를 반환합니다.

인프런 AI 인턴

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

질문자님께서는 C++에서 operator<를 오버로딩하여 구조체 또는 클래스의 객체를 특정 기준에 따라 정렬하고자 하는 방법에 대한 이해를 요청하셨습니다. 구체적인 코드 예시를 통해 오름차순과 내림차순의 정의와 정렬 로직, 그리고 sort 함수에서 사용하는 방법에 대해 궁금해 하셨습니다.

큰돌님의 강의 중 다음 질문 & 답변 게시판 글이 유사한 문제에 대한 답변을 포함하고 있습니다. 해당 글에서는 operator<가 정의된 방식과 정렬 방법이 언급되어 있으며, sort 함수의 사용 예시와 정렬 로직에 대한 설명이 포함되어 있습니다.

가령, sort 함수는 기본적으로 < 연산자를 사용하여 요소들을 오름차순으로 정렬합니다. 특정 기준으로 정렬 로직을 변경하고 싶다면 operator<를 오버로딩하여 원하는 정렬 순서를 정의할 수 있습니다. 예를 들어서, 만약 a < b가 참이라면, a가 b보다 먼저 오게 됩니다.

클래스 또는 구조체 내의 operator< 오버로딩은 sort 함수가 내부적으로 두 객체를 비교할 때 사용되며, 따라서 별도의 비교 함수(cmp)를 정의할 필요가 없습니다. 이 오버로딩은 객체 두 개를 비교하도록 설계되어 있으며 sort 함수 호출 시, 내부적으로 객체의 operator<가 사용됩니다.

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

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

교안 p131 질문 있습니다

sort()의 원리