SW 전공
시험 직전 요약장
판단 기준과 헷갈리는 개념, 대표 예제를 짧게 확인하세요.
그리디와 동적 계획법
원래 이론 →헷갈리는 개념
표를 좌우로 밀어 나머지 열을 확인하세요. 키보드: ←·→, Home·End
| 항목 | 그리디 | 동적 계획법 |
|---|---|---|
| 선택 | 현재 최선 선택을 확정 | 여러 선택 결과를 비교 |
| 이전 선택 수정 | 보통 하지 않음 | 저장된 상태를 통해 비교 |
| 필요 성질 | 그리디 선택 속성 | 중복 부분문제·최적 부분구조 |
| 장점 | 빠르고 단순 | 더 넓은 최적화 문제 해결 |
| 주의 | 반례 확인 필요 | 상태 수와 메모리 증가 |
대표 계산·예제
종료시간이 빠른 활동부터 정렬한 뒤 마지막 선택 활동과 겹치지 않는 활동을 고른다.
도식좌우로 이동해 전체 내용을 확인하세요. 키보드: ←·→, Home·End
활동: A(1,4), B(3,5), C(0,6), D(5,7), E(8,9)
선택: A → D → E
시작시간이 빠른 활동, 길이가 짧은 활동을 먼저 고르는 규칙은 일반적으로 최적을 보장하지 않는다.
내 최근 연습 오답
현재 브라우저의 연습 채점 기록에서 공개된 단원과 연결된 오답을 확인합니다.
오답 기록을 확인하고 있습니다.