2022 02 12

2022-02-12

알고리즘 문제풀이 - 그리디 알고리즘

• 그리디 알고리즘 접근법
  • 정렬을 어떻게 하는지 + 어떤 조건으로 Count를 할건지를 정하자!
    1. 어떤 경우가 최소 경우일지 생각해보기
    2. 해당 경우를 용이하게 Count 할 수 있도록 정렬하기 (O(NlogN))
    3. 한번 쭉 순회하면서 조건에 알맞은 것 Count (O(N))
  • 누가 뽑히는 게 중요한 것인지 vs 그냥 몇 명 수용할 수 있는지가 중요한 건지 구분할 것

• 결혼식 예식장 문제
  • 온시간, 간시간이 주어졌을때 동시 접속자가 가장 많은 시간은 언제인가?
  • 나는...
    • 우선 온시간-간시간 으로 Time 객체 만들고 정렬
    • 간시간으로 부터 온시간이 작은놈들 ++
    • 이중 for문으로 평생걸리게 만들어놓음 (심지어 틀림)
  • 모범답안은...
    • 온시간-'s', 간시간-'e' 으로 TimeInfo 객체 만들고 시간 순 정렬
    • 그냥 for문 돌면서 동시접속자 명수 체크
  • key point) 영수가 언제 왔다가 언제 왔는지는 안중요해
    • 그냥 현재 몇 명이 있는지가 중요해
    • 한 명왔다 -> 한 명왔다 -> 한 명갔다 : 현재 1명 있는거임