그리디 알고리즘

보호되어 있는 글입니다.

LIS 란?- N개 원소가 있는 배열에서 일부 원소를 골라내고 골라낸 원소가 이전 원소보다 큰 원소를 만족하는 부분 수열중 가장 긴 수- 예를들어 {5, 3, 2, 6, 1, 7, 8, 9, 0} 이 원소 중에서 일부를 골라내어 전 원소보다 큰 조건을 만족하는 가장 긴 경우는 {2, 6, 7, 8, 9} 이다.  이렇게 LIS를 구할 수 있는 방법은 두가지가 있다.1) DP( Dinymic Programmin)2) Binary Search DP로 푸는 경우//배열을 순회for (int k = 0; k len[i] + 1 //i번째 원소를 k번째 원소 직전 원소로 생각 안하는 경우 //맨 처음에 최소 길이를 부여한 1 ..

보호되어 있는 글입니다.

냅색 뜻? - 쓰지 않을 때에는 접어서 주머니에 넣을 수 있는 간단한 배낭 냅색은 무언가를 담을 수 있는 배낭을 의미한다. 배낭은 크기에 따라 담을 수 있는 양이 제한되어 있다. 즉, 냅색 알고리즘으로 문제를 풀어야 할때는 제한된 양이 정해졌을 때, 그 양에 효율적으로 채워 넣어서 최대의 가치를 구할때 필요하다. 예를들어  6kg을 담을수 있는 가방이 있다. 아래와 같은 물건 리스트가 있다 1) 가치 4 , 무게 3kg 2) 가치 2 , 무게 1kg 3) 가치 5 , 무게 6kg 4) 가치 6 , 무게 5kg 5) 가치 1 , 무게 2kg 6) 가치 3 , 무게 3kg 여기서 넣을 수 있는 최대의 가치는 몇인가? 이 문제는 DP( Dynamic Programming ) 으로 풀어야 한다. DP 란? 큰 ..