1. Before Class
트리 장식 문제부터 그냥 다 막히는 것 같아서 우선 강의를 반복하여 들은 후 문제를 풀어보기로 결정.
2. During Class
(1) 탐욕법 (Greedy Algorithm)
- "지금 좋은 것이 나중에도 좋다"
- 각 단계에서 그 순간에 최적해로 여겨지는 것을 선택한다.
(2) 적용 가능성 검토
- 정해진 순서를 살핀다.
- 방향을 정한다.
3. After Class
예제: 체육복 빌려주기
- 체육복이 있는 학생은 뒷 번호의 학생에게만 빌려줄 수 있음.
- 한명을 사이에 두고 뒤에 있는 사람에게 빌려줄 수 없음.
- 반대방향으로 줄 수 있는 가능성을 염두에 두고 풀어야 함.
방법 1: 순서대로 scan
- 학생 수는 기껏해야 30명
- 학생 수만큼 배열을 확보하고, 체육복 수 기록.
- 번호대로 스캔하며 빌려줄 관계 지정.
(체육복 있는 학생 = 2, 체육복 없는 학생 = 0, 1의 갯수 = 수업 가능 학생) - 알고리즘 복잡도: Linear Type - O(n)
방법 2: 없는 사람 확인
- 전체 학생수가 매우 큰데, 여벌 체육복을 가져온 학생이 매우 적을 경우.
- 문제 성질 상 더 낮은 알고리즘은 어려우며, 용량 차지가 클 것으로 예상.
- 체육복 가진 학생 번호(reserve)를 정렬하고, 빌려줄 다른 학생을 찾아 처리. = Hash
- 여벌도 있고 도난도 당한 경우는 고려하지 않으므로 제외해주면 됨.
- 알고리즘 복잡도
- O(klogk): reserve(여벌O)를 정렬
- O(k) X O(1) = O(k): lost 중 0값 찾아 처리
- 전체 알고리즘의 시간 복잡도: O(klogk)
유저가 왜 그랬을까