달력

12

« 2018/12 »

  •  
  •  
  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  
  •  
  •  
  •  

'책상 위 컴퓨터/Data Structure & Algorithm'에 해당되는 글 4

  1. 2016.04.18 [Algorithm] 배낭채우기2(1278) - jungol
  2. 2016.04.13 [Algorithm] 배낭채우기(1077) - jungol
  3. 2008.05.22 Selection sort & Heap sort & quick sort 정렬 속도 비교


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

 







Posted by 잡학 저장소 잡학저장소



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 냅색 프라블럼[*])는 조합 최적화의 유명한 문제이다.


간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.


이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.


이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)등으로 의사 다항 시간에 풀 수 있다. 단, 쪼갤 수 없는 경우는 NP-완전이기 때문에 알려진 다항 시간 알고리즘은 없고, FPTAS만 존재한다. 배낭 문제에 대한 FPTAS는 오스카 이바라와 김철언이 1975년에 개발하였다.[1]







개인적 풀이 : 




0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 0 - - - - - - - - - - - - -
2 0 0 40 - - - - - - - - - - - -
3 0 0 40 50 - - - - - - - - - - -
4 0 0 40 50 80 - - - - - - - - - -
5 0 0 40 50 80 110 - - - - - - - - -
6 0 0 40 50 80 110 120 - - - - - - - -
7 0 0 40 50 80 110 120 150 - - - - - - -
8 0 0 40 50 80 110 120 150 160 - - - - - -
9 0 0 40 50 80 110 120 150 160 190 - - - - -
10 0 0 40 50 80 110 120 150 160 190 220 - - - -
11 0 0 40 50 80 110 120 150 160 190 220 230 - - -
12 0 0 40 50 80 110 120 150 160 190 220 230 260 - -
13 0 0 40 50 80 110 120 150 160 190 220 230 260 270 -
14 0 0 40 50 80 110 120 150 160 190 220 230 260 270 300


전략  : DP 에서는 일정한 패턴의 값은 미리 Table 화 하여 값을 가지고 있는다. 

위의 Table 에서 보듯이 1 -> 2 -> 3 -> 4 -> 5 ... 순으로 마지막 14까지 값을 구한다. 

노란색 부분은 값의 최대(노란 색 부분이 꼭 구해진 값이라는 보장은 없다) 값으로 설정된 구간을 말함 

최종 무게가 14 를 가지기 위한 최대 값은 "300" 이다. 



Pseudo Open



Posted by 잡학 저장소 잡학저장소

Selection sort & Heap sort & Quick sort  정렬 속도 비교




사용자 삽입 이미지


학교 과제로 나온 ... 시간 복잡도를 비교하는 과제 ...

음 ... quick 정렬이 나름 제일 빠른 줄 알았지만 ( nlogn 이라고 하지만 ... ) 이런 속도 차이가 ...

selection, insert, bubble 등 이런 정렬들은 ... 일정 자릿수 이상의 값을 입력 하였을 시에 ...

미칠듯한 정렬 시간이 나왔다.

첨부 된 그림은 실제로 적용 해 본 후 나온 결과 화면 ...


※ 정렬 되지 않은 자료일 경우 정렬하는데 얼마 걸리지 않는데, 정렬 된 자료 일 경우 ... 생각보다 시간이 걸렸다. 여러 책에 따르면 Quick sort는 정렬된 자료일 경우 정렬하는데 걸리는 시간이 더 걸린다고 하는데 ... 으흠 ... 쏘스에 따라 달라짐은 이를 어떡하랴 ?

화면을 클릭하면 크게 보일까? 흠흠 ...

( 테스트한 자료는 ... 50,000 에서부터 시작하여 2,000,000 까지의 데이터를 무작위로 생성하여 테스트 하였다. JAVA로 작업 하였음 )


- PS -
 이론상 Quick sort의 경우 정렬된 경우는 위의 결과처럼 나오지 않는다. 즉 복잡도가 증가해서 Selection sort의 경우처럼 느린 경우를 볼 수 있다.
 즉 작성하는 소스에 따라서 결과값은 달리 나온다.

Posted by 잡학 저장소 잡학저장소