끄적끄적

목차  배낭 문제 (Fractional Knapsack Problem)"배낭 문제"는 한정된 조건에서 최대 가치를 구하는 최적화 문제를 의미하는 용어이며, DP이외에도 백트래킹 등으로 구현할 수 있다.효율성으로 인해 DP를 많이 사용하지만, DP로만 접근할 수 있음을(혹은 DP기법 자체를) 의미하진 않는다. 1. 분할 가능한 배낭 문제 (Fractional Knapsack Problem)그리디한 방법으로 풀 수 있다.아이템들의 "무게당 가치"를 구한 후, 이를 내림차순으로 정렬하여 무게 제한에 도달할 때까지 더해주면 된다. 다만, 무게당 가치 = 가치/무게는 즉 무게 1당 가치를 의미한다.무게 = 0.1 가치 = 0.5 일 때, 가치/무게 = 0.5/0.1 = 5 이 경우, 다음과 같이 가방의 무게가 소..

목차 위상 정렬 (Topological Sorting)유향 비순환 그래프(DAG)의 정점을 변의 방향을 거스르지 않도록 나열하는 정렬 기법이다.탐색 기법도 맞지만 정렬 기법이라는 표현이 본질에 더 가깝다.이벤트/작업 스케쥴링, 의존성 관리 등 순서를 정해야 할 때 사용할 수 있다. 정의만 들어서는 잘 이해가 가지않는다.보통 예시로 선수 과목(혹은 커리큘럼/이수 체계도)를 든다.   세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 순서로 과목을 들어야한다. 각 과목을 그래프의 정점(혹은 노드)로 치환했을 때,자료구조 -> 알고리즘 -> 고급 알고리즘 이라는 이수 순서를 구하는 것이 위상 정렬이다. 위상 정렬의 종류진입 차수(Indegree) 기반, DFS/BFS 기반, DFS를 변..