그래프2 1/29 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 냅색 알고리즘 (Knapsack Algorithm) 유명한 다이나믹 프로그래밍 문제 혹은 그리디 알고리즘 문제 중 하나이다. 두 가지 유형으로 나뉜다. Fractional Knapsack Algorithm: 주어진 자원을 쪼갤 수 있다는 가정 하에 그리디 알고리즘으로 최적의 조건이 구해진다. 주어진 조건(ex: 가격, 무게) 중 가장 크거나 작은 것부터 대입하여 최적 방식을 구한다.(그리디 알고리즘) 0 - 1 Knapsack Algorithm: 주어진 자원이 0 또는 1, 즉 존재하거나 존재하지 않는, 쪼갤 수 없는 상태면 DP를 사용해야한다. 보통 후자의 문제가 자주 나온다. 그래서 쪼갤 수 없는 보석이 나오면 제로원, 디피.. 2023. 1. 31. 12/04 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 그래프 노드와 간선의 집합 방향이 설정되어 있으면 방향 그래프 방향이 설정되어 있지 않으면 무방향 그래프 간선에 값이 설정되어 있으면 가중치를 뜻한다. 이러한 그래프는 가중치 방향 그래프라 한다. 인접 행렬 프로그래밍에서 그래프를 표현할 때 사용하는 행렬 기본적으로 인접행렬을 입력할 떄 행 -> 열의 방향으로 그래프가 진행 된다고 보면 된다. 노드 a가 b로 갈 때 인접 그래프가 g라고 하면 g[a][b] = 1 이렇게 표현한다. 가중치가 있으면 g[a][b] = (가중치) 라고 표현한다. 무방향 그래프의 경우 g[a][b] = 1 , g[b][a] = 1 이렇게 행과 열을 바꾸어 두 번 지정해주어야 한다. 방문 체크 리스트 d.. 2022. 12. 4. 이전 1 다음
