Major/문제 해결 기법(Application of algorithm) (5) 썸네일형 리스트형 네트워크 플로우 시작점 s부터 도착점 t까지 몇개(정수기준이라)나 보낼 수 있나 들어보니 일종의 쿠팡루틴 비슷하다 쿠팡 창고에서 어떤 도착지까지 다 보내야하는데 어떤 경로를 통해서 보내야 하는지,, 플로우란??? 그냥 시작점에서 몇개 보내는 지 갯수 컷이란??? 중간에 관문임 경우에 따라 다양한 관문을 잡을 수 있겄지 근데 그 각각의 컷은 보낼 수 있는 플로우 값 더한거 그럼 그 각각의 컷(플로우값의 합)들 을 모아둔 집합이 있다고 할 때 그 집합 중에서 가장 작은 값이 보낼 수 있는 최대 플로우지. 근데 엣지 최대 전송 가능한 거 찾을 때, 너비우선탐색 BFS가 있고 깊이우선탐색 DFS가 있음. 세그먼트 트리 - (Segment Tree) Segment Tree (입력) -> 배열 A[n], 두 정수 a, b ( 0 Update(i,x) : A[i] = x (Brute-force method) -> No preprocessing. - 전처리없이 하면 -> O(n) in the worst case - 시간복잡도가 O(n)일 것이다. 배열의 부분합을 쳐 여어놓으라고 이거 나중에 문제푸는데 쓴데 배열에서 구간 합 근데 트리에서 이미 구한 값을 이용해서 구하면 쉬웅게 이렇게, long long sum(vector &tree, int node, int start, int end, int left, int right) { if(left>end || right < start) { return 0; } if (left 욕심쟁이 기법(Greedy Algorithm) 문제를 풀 때 가장 먼저 시도해볼 수 있는 방법. => 잘 될 거 같은 방법버텀 한다. 눈에 보이는거 순서대로 처리한다. 매 단계마다, 각 단계에서 최선이라고 볼 수 있는 선택을 한다. 전체적인 입장을 보지 않고 현재 순간 최선을 취한다. 알고리즘이 매우 간단한 대신, 구한 답이 정답이라는 보장이 없다.(정답 확인 과정 必) " 숲을 안보고 앞의 나무 부터 벤다...! " 기본 형태 (틀) set Greedy(set C)// C : 후보들의 집합 { S (4주차) - 문제해결기법 #부분합 문제 & 입력 : 배열 A[n], 두 정수 a, b( 0 (3주차) - 자료구조 RMQ(Range Minimun Query) 구간최소트리 아.. 이거 그냥 자료 배열에서 구간 정해놓고 최솟값 찾는거라고 생각해서 아 이거 x밥인데 뭘 거창하게 강의를 하지..? 했는데 생각보다 이해 안되서 공부를 해야것다.. 애립네... 사실 찾고자 하는것은 굉장히 간단해 보인다. 배열이 주어지면, 주어진 a부터 b까지의 정해진 구간 내에서 최솟값을 찾는 것이다. a가 더 작은 값이니 a는 0번 배열, 즉 첫번째 배열일 경우가 가장 작은 값, b는 배열 n-1번째까지(n개의 배열이 있다고 할 때)가 가장 마지막 배열이다. 하지만 알다시피, 멍청하게 하면 시간만 주어지면 누구나 할 수 있는 문제이다. 하지만 이런 문제를 해결함에 있어서 복잡도O(ଲ)안에 해결해야하는 부분이기에 노가다(Brute-force) 방법은 지양한다. 가장 시간이 긴 경우, 전부 읽게된다.. 이전 1 다음
