인프런 커뮤니티 질문&답변
작성한 질문수
5-A 그림 질문
작성
·
172
답변 1
0
안녕하세요 효민님 ㅎㅎ
일정이 짧은 순서대로 정렬되고 비용 또한 오름차순 정리되면 아래 그림처럼 그리는것이 맞을까요? 수업 듣다가 헷갈려서 여쭤봅니다 ㅎㅎ
>>
음..
저보다 그림 잘 그리시네요 ㅎㅎ
효민님의 그림도 어느정도는 맞는 설명입니다.
다만,
제가 이렇게 그린 이유는 다음과 같은데요.
PQ에다 들어가는 부분을 묘사한 것인데요.
sort를 해서 쭉쭉 들어갑니다. d, p순이기 때문에
d는 day, d는 오름차순으로 정렬되는 것이 자명하죠. 해당 부분은 1일, 2일... 이렇게 설명드리고 있습니다.
근데 여기서
p는 오름차순 정렬이 될까요?
됩니다.
그러나.
이렇게 됩니다.
d, p 를 기준으로.
{1, 3}
{2, 1} 이렇게 되어있으면
3 1 이런식으로 정렬이 되겠죠? d가 1차적, p가 2차적으로 정렬이 되니까요.
그러한 p 중에서 최댓값이 p의 가장 앞의부분에 있게 됩니다.
즉, pq에서는 자동으로 p가 내림차순으로 정렬되는 것이죠.
이를 알려주기 위해 저렇게 그려봤습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
그리고 요즘 질문 많이 드리는데 너무 잘 가르쳐주셔서 감사합니다. 강사님 정말 최고십니다. 강사님의 열정에 보답하기 위해서라도 열심히 준비해서 한번에 코딩테스트 합격해보도록 하겠습니다!
으으.. 효민님 ㅠㅠ 제가 원래 실수를 잘 안하는데.. 잘못 알려드린것 같습니다. 요새 제가 서비스 배포를 앞두다보니 정신이 없네요 ㅠㅠ
priority_queue<int, vector<int>, greater<int>> pq; 이렇게 설정했기 때문에
내림차순이 아닌 오름차순 정렬되는 것 아닌가요? 따라서 pq.pop( )으로 가장 적은 비용부터 제거해서 아래 그림처럼 가장 큰 비용만 남게 되는 것으로 이해했습니다!
>> 네 맞습니다. 오름차순 정렬이고.. 저 히스토그램 그림은 수정되는게 맞습니다... 죄송합니다 ㅠㅠ
해당 부분은 강의내에서 수정 글 달도록 하겠습니다.
효민님이 말씀하신 것처럼
오름차순으로 정렬된 히스토그램이 맞는 표현입니다.
강의내에서 제가 말씀드린 것 처럼 최소치를 빼서 최댓값을 만드는 것.
입니다.
헷갈리게 해서 죄송합니다 ㅠ
강사님 정말 최고십니다. 강사님의 열정에 보답하기 위해서라도 열심히 준비해서 한번에 코딩테스트 합격해보도록 하겠습니다!
>>
그리고... 칭찬감사합니다 ㅎㅎ 마음이 따스해지네요 ㅎㅎ 저도 효민님이 꼭 코테 합격하시길 기원할게요 ㅎㅎ 이 강의내의 히든퀘스트까지 꾹꾹 다 풀어주세요!(그걸 풀어야 속도 + 잔실수가 줄어들어요!!)
감사합니다.
자세한 답변 감사합니다! 그러면 처음 sort후에는 아래 그림처럼 v가 정렬되는 것이 맞고,
sort 후 pq에 v[i].second 값이 들어가도
priority_queue<int, vector<int>, greater<int>> pq; 이렇게 설정했기 때문에
내림차순이 아닌 오름차순 정렬되는 것 아닌가요? 따라서 pq.pop( )으로 가장 적은 비용부터 제거해서 아래 그림처럼 가장 큰 비용만 남게 되는 것으로 이해했습니다!