[6주차_수요일] 앱

[icegosimperson]

• 사이트 : 백준(BOJ)
• 문제: 앱
• 번호: 7579

  🤔 시간복잡도 고려사항
  💡 풀이 아이디어

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : O(N), 메모리를 활성화 or 비활성화 2^100 -> 완전탐색 불가

💡 풀이 아이디어

• 비활성 메모리 추가 비용을 최소화 하는 문제
• 메모리 나눌 수 없음 -> 01 배낭 문제 -> dp
• dp[]: 비용으로 확보할 수 있는 최대 메모리
• dp[j] = Math.max(dp[j], dp[j-cost[i]] + memory[i]);

        int[] dp = new int[sum+1]; // 비용으로 확보할 수 있는 최대 메모리, sum 최대 = (100 * 100) = 10000
        for(int i=0; i<N; i++){
            for(int j=sum; j>=cost[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-cost[i]] + memory[i]);
            }
        }

        for(int i=0; i<=sum; i++){
            if(dp[i]>=M){
                System.out.println(i);
                break;
            }
        }

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 100
• 0 ≤ c1, ..., cN ≤ 100
• 배열의 최대 크기: 100*100 =10,000
• 시간복잡도: 100*10000 =1,000,000 (10^6) → O(N)

💡 풀이 아이디어

• DP이용
  • 해당 앱을 활성화 or 비활성화 : 01배낭문제
    • 01배낭문제는 중복값을 허용하지 않아야하기에 for문 거꾸로 탐색
• 첫번째 아이디어
  • dp[i] = c, i메모리로 얻을 수 있는 최소 비용 c 구하기

    INF로 초기화를 해줘야하고 뭔가 직관적이지 못함.. "비용"을 기준으로 점화식 변경

• 두번째 아이디어
  • dp[i] = j, i비용으로 얻을 수 있는 최대 메모리 j 구하기
  • dp[j] = Math.max(dp[j], dp[j - cost[i]] + memo[i]);
• 생성한 dp값을 바탕으로 최소 비용 i 찾기
  • 처음엔 이분탐색을 이용했으나, dp값이 정렬되어 있다는 보장이 없기때문에 올바른 접근이 아님!
  • dp배열 돌면서 확인하기

dp.. 뭔가 느낌만을 가지고 점화식을 세우는거같아서, 좀 더 초기값이나 세부 내용들을 확실하게 하는 연습을 해야겠다!

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 앱의 개수 <= 100, 1 <= 메모리 바이트 <= 10_000_000
• M바이트를 확보하기 위한 최소 비용 구하기
• 완전 탐색을 통해 앱의 선택할 수 있는 모든 경우의 수를 확인한다면 2^100(시간 초과)
• 앱의 선택과 관련있기 때문에 Knapsack문제로 해결할 수 있음: O(NlogN)

💡 풀이 아이디어

• App[] apps: 앱에 대한 정보 저장
  • int m: 바이트, int c: 비용
• int[][] knapsack: M바이트를 확보하기 위해 필요한 앱 비활성화 최소을 구하기 위한 2차원 배열
  • 행: r번째까지의 앱을 확인했다는 것을 의미
  • 열: c원까지 최소화 비용
  • 행과 열에 대해 r번째 앱까지 고려할 때, c원을 사용했을 때, 몇 바이트까지 활성화할 수 있는지에 대한 정보 저장

[yeongleej]

🤔 시간복잡도 고려사항

• N ≤ 100
• M ≤ 10,000,000
• 0 ≤ c1, ..., cN ≤ 100

=> 활성화 하기 or 비활성화하기 : 완전탐색(2^100)은 불가 X => 최대 비용 : 100 100이므로 N 최대비용 O (DP로 해결해보기)

💡 풀이 아이디어

• M바이트를 확보하기 위한 최소비용을 구하기 위해, 각 활성화앱을 비활성화할 때 비용을 사용해서 비활성화할 수 있는 최대메모리를 구함
• dp[i][j] : i번째까지 탐색했을 때, j비용으로 비활성화할 수 있는 최대 메모리
• 적은 비용부터 탐색하면서 M보다 큰 메모리를 비활성화할 수 있다면 그떄의 비용이 최소비용

문제를 제대로 읽지 않고 dp[i][j]: i번째까지 탐색했을 때, j메모리를 비활성화할 수 있는 최대 비용을 구하려고해서 메모리초과과 났습니다.... 다양한 냅색문제를 더 연습해야곘습니다~

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 100 → N x 최대 비용을 이용한 DP로 풀이
• 0-1 knapsack

💡 풀이 아이디어

• 특정 코스트에 얼마나 많은 메모리를 확보할 수 있느냐가 핵심
• 따라서 중복 선택이 안되는 0-1 knapsack을 활용
• 앱을 순차적으로 탐색하면서 특정 비용에서 비활성화했을 때, 얼마나 많은 메모리를 확보할 수 있는지를 체크
• 최종적으로 금액을 순회하면서 확보해야하는 메모리 이상의 메모리가 나오면 정답

  1차원 배열로 풀려다가 혼났습니다 → 중복을 허용하는 knapsack

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DP > 냅색 알고리즘
• 시간복잡도: 앱 1 ≤ N ≤ 100, 배터리 0 ≤ c1, ..., cN ≤ 100 O(N*C) 는 100*100 = 10^4

💡 풀이 아이디어

• dp[비용] = 메모리 1차원 dp배열을 특정 비용일 때 최대 메모리 값을 구하는 방식으로 접근

• "특정 비용의 최대 메모리" 를 구하는 이유?

  • 만약 dp[M]을 기준으로 최소비용을 구하면 M이 최대 10^7 이기 때문에 10^7만큼 메모리제이션이 필요하여 많은 연산이 필요함
  • M이상의 메모리가 필요하기 때문에 최대라면 항상 메모리를 충족함
  • 따라서 특정 비용에 항상 최대 메모리 값을 넣기 때문에 최소 비용을 구할 수 있음

• 역순으로 순회하는 이유?

  • 단순 배낭문제인 경우 이전 값을 재사용하게 되지만, 최대 메모리를 구하기 위해 항상 최대값으로 갱신해주기 때문에 이전 값을 재사용하게 되면 최적의 해를 구할 수 없음
  • 따라서 갱신된 이전값을 사용하지 않도록 역순으로 순회