Life Of D22

Click 문제 바로 가기 : JUNGOL 문제 : 배낭채우기2 (1278) 제한시간 1Sec 메모리제한 64mb 입력 형식 : 입력의 첫 줄은 보석의 개수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다.둘째 줄부터 N+1줄에는 각 보석의 무게 Wi(1≤Wi≤W)와 값어치 Pi가 주어진다. (단, 보석은 각 종류별로 1개씩이다.) 출력 형식 : 출력은 보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서 보석의 총 값어치가 최대가 되는 최대값을 출력한다. 입력 예 출력 예 4 16 90 2 40 5 30 10 50 5 10

Clink 문제 바로 가기 : JUNGOL 문제 : 배낭채우기 (1077) 제한시간 1 Sec 메모리제한 64 mb 입력 형식 : 첫 줄은 보석의 가지 수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다. 둘째 줄부터 N+1줄에는 각 보석의 무게 Wi(1≤Wi≤W)와 값어치 Pi가 주어진다. (단, 각각의 보석의 개수는 무제한으로 가정한다.) 출력 형식 : 보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서, 보석의 총 값어치가 최대가 되는 최대값을 출력한다. 입력 예 출력 예 4 14 300 2 40 5 110 3 50 참고 이론 : 배낭문제 (출처 : 위키피디아) 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다. 간단..

Selection sort & Heap sort & Quick sort 정렬 속도 비교 학교 과제로 나온 ... 시간 복잡도를 비교하는 과제 ... 음 ... quick 정렬이 나름 제일 빠른 줄 알았지만 ( nlogn 이라고 하지만 ... ) 이런 속도 차이가 ... selection, insert, bubble 등 이런 정렬들은 ... 일정 자릿수 이상의 값을 입력 하였을 시에 ... 미칠듯한 정렬 시간이 나왔다. 첨부 된 그림은 실제로 적용 해 본 후 나온 결과 화면 ... ※ 정렬 되지 않은 자료일 경우 정렬하는데 얼마 걸리지 않는데, 정렬 된 자료 일 경우 ... 생각보다 시간이 걸렸다. 여러 책에 따르면 Quick sort는 정렬된 자료일 경우 정렬하는데 걸리는 시간이 더 걸린다고 하는데 ....

/* SelectionSort : sort contiguous list by the selection sort method. Pre : The contiguous list list has been created. Each entry of list contains a key. Post : The entries of list have been rearranged so that the keys in all the entries are sorted into nondecreasing order. Uses : MaxKey, Swap */ void SelectionSort( List * list ){ Position current; /* position of place being correctly filled */ ..