그리디, 라인스위핑 질문있습니다 :)

작성한 질문수 79

0

안녕하세요 유태님 ㅎㅎ

문제마다 앞에서부터 정렬할지, 뒤에서부터 정렬할지 정확하게 판단이 서지를 않고 있습니다.

-> 이거는 오름차순 또는 내림차순을 말씀하시는거죠? 이건 문제마다 다른데요.

이번 선긋기문제를 볼까요?

    sort(L, L + n); 
    l = L[0].first; r = L[0].second; 

앞의 코드처럼 오름차순 정렬을 하고 있는데요.

이렇게 보통의 라인스위핑 문제는 오름차순 정렬이 많습니다. 그래서 처음에는 오름차순으로 정렬을 시도하고 -> 내림차순이나 정렬 조건을 다르게 해서 하는것을 추천드립니다.

감사합니다.

0

안녕하세요, 인프런 AI 인턴입니다. 한유태님 🙂

그리디 알고리즘이나 라인 스위핑 문제에서 정렬의 방향을 결정하는 것은 문제의 조건과 목표에 따라 다를 수 있습니다.

1. 그리디 알고리즘:

   • 문제 목표에 집중: 먼저 문제의 목표를 명확히 이해하는 것이 중요합니다. 최대나 최소를 찾는 문제인지, 특정 조건을 만족해야 하는지를 명확히 해야 합니다.
     
   • 정렬 기준 설정: 주로 ‘이득이 큰’ 혹은 ‘비용이 작은’ 요소들을 먼저 선택하는 방식으로 진행됩니다. 따라서 어떤 기준으로 정렬해야 이득을 극대화할 수 있을지 판단하세요.
     

2. 라인 스위핑:

   • 좌표나 범위 기반: 주로 좌표 축을 따라가면서 이벤트를 처리하는데, 시작점과 끝점을 기준으로 정렬합니다. 시작 이벤트를 먼저 처리하는 것이 일반적입니다.
     
   • 이벤트 처리 순서: 시작과 끝 이벤트가 동시에 존재할 때 어떤 것을 먼저 처리해야 하는지 문제가 명시하고 있는지를 확인합니다.
     

정렬 방향이나 기준은 이러한 문제들에 따라 다양할 수 있기 때문에, 문제를 반복적으로 풀어보면서 패턴을 익히는 것이 중요합니다. 또한, 관련된 문제 토론이나 해설을 참고하는 것도 패턴을 익히는 데 큰 도움이 됩니다.

이와 관련해서 더 구체적인 예시가 필요하시다면, 아래의 URL에서 유사한 질문과 답변을 참고하실 수 있습니다:
- 6-F 그리디 질문입니다.

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