탐욕 알고리즘 - 회의실 배정문제 해법 -

1. 문제 유형 1-1) 예시 윤대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다. 회의는 시작 시간과 종료 시간이 있고 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다. 가능한 많은 회의가 열리기 위해 회의실은 어떻게 배정해야할까? 1-2) 정형화 시작시간과 종료시간 $(s_{i}, f_{i})$가 있는 n개의 활동들의 집합 $A = \left\{ A_{1}, A_{2},... , A_{n} \right\}$이고 i는 1이상 n이하이다. 여기서 서로 겹치지 않는 최대 개수의 활동들의 집합 S를 구하는 문제 2. 문제 해법 모든 경우의 수를 조사할 수도 있지만 탐욕 알고리즘이 가능한 대표적인 문제..

• format_list_bulleted 그리디 알고리즘
• · 2022. 9. 26.
• textsms

다이나믹프로그래밍 - 어떻게하면 완전탐색도 더 효율적으로 할 수 있을까?

1. 문제 N개의 block이 일렬로 있고 0부터 N-1까지 숫자가 붙어있다. 사이가 안좋은 개구리가 하나의 block위에 함께 있는데 이들이 서로 최대한 멀리 떨어지려고 한다. 만약 J와 K, J= s_h: s_h = h first += 1 else: break 현재 s-1에 첫번째 개구리가 시작할건데 blocks의 s부터 오른쪽으로 순회를 해서 h라고 두는거임 만약 h가 시작높이 s_h보다 크거나 같으면 점프할 수 있고 현재 개구리 높이 s_h를 h로 두고 first에 1을 더해서 개구리 위치를 갱신한다 근데 점프를 못하는 순간 더 이상 오른쪽으로는 못간다는 소리이므로 반복문을 탈출 s_h = blocks[s] #second frog for ind,h in enumerate(blocks[s::-1])..

• format_list_bulleted 다이나믹 프로그래밍
• · 2022. 6. 23.
• textsms