sh1mj1_log

https://sh1mj1-log.tistory.com/130 글에서 이어지는 포스팅입니다. 백준 1931 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 문제 분석 1개의 회의실에 회의가 겹치지 않도록 최대한 많은 회의를 배정해야 합니다. 이 때는 그리디 알고리즘을 적용해야 합니다. 현재 회의의 종료 시간이 빠를 수록 다음 회의와 겹치지 않게 시작하는 데 유리합니다. 종료 시간이 빠른 순서대로 정렬하면 겹치지 않는 회의실을 적절하게 선택하면 됩니다. 2. 손으로 풀기 1. 회의와 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬. 종..

그리디(Greedy) 그리디(Greedy) 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘입니다. 그래서 동적 계획법(Dynamic Programming) 보다 구현하기 쉽고 시간 복잡도가 우수합니다. 하지만 항상 최적의 해를 보장하지는 못한다는 단점도 있습니다. 그래서 항상 그리디 알고리즘을 사용하기 전 논리에 대해 자세히 살펴보아야 합니다. 그리디 알고리즘의 수행 과정 1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택 2. 적절성 검사: 현재 선택한 해가 전체 문제의 조건에서 벗어나지 않는지 검사 3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 만약 해결할 수 없다면 1의 과정을 반복. 바로 ..