인프런 커뮤니티 질문&답변
작성한 질문수
5 - E 풀이까지 가는 생각
해결된 질문
작성
·
29
0
항상 그리디가 어려웠는데 오랜만에 풀어보니 답은 맞는데, 뭔가 이게 맞나라는 생각이 너무 들어서 생각 흐름이 맞는지 질문드립니다!
블로그에 개인적으로 정리한 글이라 반말인점 무시해주시면 감사하겠습니다 ㅠ
무식하게 하기엔 범위가 10만이고 범위가 존재해서 그리디가 생각났다. 우선, 위 사진처럼 생각해봤다. 순서 정렬은 start 시간 기준으로 하는게 맞다. 왜냐하면 회의 시간이 짧은 걸로 sort 하면 100000에 시작하고 100001로 끝나는 게 처음에 배치되기 때문이다. 끝도 의미가 없으니 시작으로 순서 정렬을 잡았다.
그럼 어떤 예외가 있을까 싶었는데
사진의 맨 위에 엄청 긴 선 같은 부분이 문제다. start가 가장 작으니 배열의 처음에 위치하기 때문이다. 따라서
if (prev_s < s && e < prev_e)
위와 같이 이전 값의 사이에 현재 해당 값이 존재하면 (이전 = 긴 선, 현재 = 긴 선 다음으로 start가 빠른 선) 면적은 줄지만 다른 회의가 잡힐 공간 자체는 늘어나게 되니 무조건 이득인 것이다. 따라서 저럴 땐, 이전 친구를 pop해주고 현재 친구를 push 해줬다.
이외에 이전의 끝과 현재의 시작이 겹치거나 더 크면 회의실을 잡을 수 있으니 push 해준다. 반대의 경우는 회의중이기 때문에 회의실을 잡지 못하기 때문에 따로 push 해주지 않는다.
답변 2
0
안녕하세요 자르트님 ㅎㅎ
반례까지 생각하시고 좋은 생각의 흐름입니다.
무식하게 하기엔 범위가 10만이고 범위가 존재해서 그리디가 생각났다.
-> 이거는 무식하게 -> DP -> 그리디 순으로 생각했다가 정답이긴합니다. 그러나 지금 DP를 안배웠기 때문에 맞긴해요 ㅎㅎ
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 자르트님께서 질문해 주신 내용을 확인했습니다. 그리디 알고리즘을 적용할 때, 특히 회의실 배정 문제는 특정 정렬 기준을 설정하고, 그에 따라 회의를 선택하는 방식으로 접근합니다. 회의의 종료 시간을 기준으로 정렬하는 이유는 가능한 많은 회의를 배치하기 위해서입니다.
자르트님께서 고민하신 “회의 시작 시간”을 기준으로 정렬하는 접근법은 때때로 그리디 문제에서 직관적으로 접근하기 어려운 부분이기도 합니다. 일반적으로 시작 시간이 아닌 종료 시간을 기준으로 정렬하는 이유는 첫 번째 회의를 종료하는 시점부터 바로 다음 회의를 시작할 수 있기 때문입니다. 이렇게 하면 최대한 많은 회의 시간을 활용할 수 있습니다.
관련된 참고 자료를 제공해 드릴 수 있습니다:
- 회의실 배정 문제에서 그리디 선택 기준
사진 속의 뛰어난 시각화에도 불구하고, 해결책이 맞는지 확신이 없으신 것 같습니다. 특히 ‘회의 정렬’ 부분에 대한 이해를 강조하고 싶습니다. 자르트님이 제시한 접근 방식에서는 시작 시간을 기준으로 정렬하셨는데, 이것이 효율적인 결과를 보장하지 못할 수 있습니다.
궁금한 점이 있다면 더 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다. 저도 도움이 되기를 바랍니다. 🙏
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.