본문 바로가기
반응형

SWE/코테137

배낭 문제(Knapsack Problem) - 0-1 Knapsack Review 냅색 문제는 물건 개수에 따라 3가지 종류가 있다.1) Unbounded Knapsack Problem : 물건의 개수가 무제한일 때2) 0-1 Knapsack Problem : 물건의 개수가 1개뿐일 때 ( 각 종류의 물건을 한 번만 사용할 수 있다. )3) Bounded Knapsack Problem : 물건의 개수가 제한적일 때 ( A물건은 3개, B물건은 5개, ... ) 1번 Unbounded Knapsack Problem은 이전 게시물에서 작성했고이번에는 0-1 Knapsack Problem에 대해 공부할 것이다. 예제 문제 Q. 배낭에 담을 수 있는 물건의 종류와 무게, 가격이 다음과 같다고 가정할 때,배낭 최대 수용 무게 4kg에 담을 수 있는 최대 금액은? 0-1 Knapsa.. 2018. 12. 9.
[성실코딩 31일차] 백준 #1699 제곱수의 합 ** / Knapsack 기말고사 시험공부 겸 Unbounded Knapsack문제를 찾아서 풀었다. 잘못된 접근 방식으로 풀어서 시간초과가 나왔고 ( 예제도 맞고 틀린 방법은 아니라고 생각함! 오래걸려서 비효율적일 뿐,,,,,)그래서 맞은 사람 코드를 보고 공부했다. 옳은 풀이법 및 코드참고 코드 링크 : http://wootool.tistory.com/102이 코드에서 핵심 알고리즘 for (int n = 1; n #include // malloc #include // memset #define INF 987654321 int N; // 문제 자연수 N int square[1000] = { 0, }; // 제곱수 저장해 놓는 배열. // 사이즈 1000 _N) { break; }.. 2018. 12. 9.
[성실코딩 30일차] 백준 #1562 계단 수 ** 모르겠다... 규칙성 있을 것 같은데... 예를 들어, N=14일 경우, "9~0"을 순서대로 놓는 10개를 제외하고, 4개를 정렬하는 경우의 수를 따졌다. 1) "9~0" _ _ _ _ 2) _ _ _ _ "9~0" 3) _ _ _ "9~0" _ 4) _ _ "9~0" _ _ 5) _ "9~0" _ _ _ 이렇게 놓는 방법을 생각했고, 각각 6개, 6개, 3개, 3개, 4개가 가능하다. 그리고 4개 자리 수에서 5개 자리 수로 증가할 때마다, 4개에 수에서 각각 2가지 경우가 추가로 가능하다. ( 끝자리 수인 0이나 9를 제외하고) 왜냐하면 예를들어 마지막 자리수가 4로 끝날 경우, 그 뒤에 값을 추가해주려고 하면 ( _ _ _ 4 ), 3혹은 5가 가능하기 때문. ( _ _ _ 4 5, _ _ _ 4.. 2018. 12. 5.
[성실코딩 29일차] 백준 #11727 2xn 타일링 2 *질문 자정 넘기 전에 풀고 싶었는데!! 모르겠다,,, 그리고 나는 규칙성 찾아서 풀었는데 경우의 수 구하는 방법으로 접근하고 싶다 (내가 경우의 수 약함 ㅠㅠ 중복되는 경우의 수를 어떻게 제외 시켜줄지 모르겠음) 쨋든 내일 다시 해보자 예제 입출력은 모두 맞는데 제출하면 틀렸다고 나온다. 사이즈도 unsigned long long 해서 1000까지 나오는데! #include using namespace std; unsigned long long arr[1001] = {0,1,3,5,}; int n; unsigned long long getN(int _n) { if ( arr[_n] !=0 ) { return arr[_n]; } return arr[_n] = getN(_n - 1) + 2.. 2018. 12. 5.
반응형

티스토리툴바