728x90 공부/알고리즘28 Knapsack Problem(배낭 문제) 오늘은 배낭 문제(Knapsack Problem, 냅색 프라블럼) 에 대해 배워보겠습니다. 배낭 문제는 조합 최적화의 유명한 문제 입니다. :도둑이 다른 가치와 다른 무게가 있는 보석을 훔치는데 넣을 수 있는 무게가 정해진 가방에 최대한 많이 넣는 문제입니다. 이 배낭문제는 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem) 과 짐을 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem) 라 부릅니다. 저희 분할 가능 배낭문제를 그리디 관점에서 살펴보도록 하겠습니다. (다항시간에 풀 수 있습니다. 0-1 배낭문제는 DP로 풀 수 있습니다.) 훔친 물건 중에 가치가 가장 높은 거 부터 넣습니다. 그리디는 쉽게 생각할 수 있지만 항상.. 2020. 6. 21. 네트워크 플로우(Network Flow) ※이 글은 나동빈님 포스팅을 보고 복습용으로 제작이 되었습니다. https://blog.naver.com/ndb796/221237111220 27. 네트워크 플로우(Network Flow) 네트워크 플로우(Network Flow)는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를... blog.naver.com 안녕하세요. 옆집 컴공생입니다. 오늘은 네트워크 플로우(Network Flow) 에 대해 배워 볼거에요. 그전에 구현에서 BFS 를 써서 구현을 하기 때문에 개념을 복습하는 게 좋을 거 같습니다 . https://com24everyday.tistory.com/109?category=1123820 너비 우선 탐색(BFS) ※이 포스팅은 나동빈님 강의를 듣고 정리한 것 입니다.※ .. 2020. 6. 15. 강한 결합 요소(Strongly Connected Component) ※다음 포스팅은 나동빈님 블로그를 보고 포스팅한 것입니다. https://blog.naver.com/ndb796/221236952158 26. 강한 결합 요소(Strongly Connected Component) 강한 결합 요소란 그래프 안에서 '강하게 결합된 정점 집합'을 의미합니다. 서로 긴밀하게 연결되어 있다고... blog.naver.com 강한 결합 요소란 그래프 안에서 '강하게 결합된 노드의 정점 집합' 라는 의미 입니다. 서로 강하게 연결되어 있다고 하여 강한 결합 요소입니다. 이는 SCC 알고리즘이라고 불리는 데요. SCC 는 '같은 SCC 에서 선택한 두 정점은 서로에게 도달이 가능하다' 는 특징이 있습니다. 다음 그래프에서 SCC 를 구하면 다음과 같습니다. 집합에 속하는 정점끼리 서로.. 2020. 6. 13. 위상정렬(Topology Sort) 위상 정렬(Topology Sort) 는 순서가 정해져있는 작업을 차례로 수행할 때 순서를 결정해주기 위해 사용되는 알고리즘입니다. 예시를 바로 볼까요. 다음과 같이 할 일 루틴이 있다고 합시다. 청소나 블로그 작성은 어느것을 먼저 수행하든지 상관이 없지만 점심은 강의를 복습하고 나서야 할 수 있습니다. 이처럼 한 단계를 수행하기 전에 해야하는, 즉 화살표의 개수(조건)를 '진입 차수' 라고 합니다. 이러한 조건들에 부합하는 일직선이 순서를 찾는것이 위상정렬입니다. 출근 -> 청소 -> 블로그 작성 -> 강의듣기 -> 강의 복습 -> 점심먹기 위와 같이 정렬을 수행할 수 있습니다. 그리고 다양한 답이 존재합니다. 그렇기 때문에 더욱 매력적인 알고리즘이라고 할 수 있습니다. 또 위상정렬을 DAG(Direc.. 2020. 6. 12. 이전 1 2 3 4 5 ··· 7 다음 728x90
