{"id":28184,"date":"2024-10-27T15:32:27","date_gmt":"2024-10-27T15:32:27","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28184"},"modified":"2024-11-26T07:06:59","modified_gmt":"2024-11-26T07:06:59","slug":"%ec%8a%a4%ec%9c%84%ed%94%84%ed%8a%b8-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%eb%b8%94%eb%a3%a8%eb%a0%88%ec%9d%b4-%eb%a7%8c%eb%93%a4%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28184\/","title":{"rendered":"\uc2a4\uc704\ud504\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ube14\ub8e8\ub808\uc774 \ub9cc\ub4e4\uae30"},"content":{"rendered":"

<\/p>\n

\ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc5d0\uc11c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud480\uc5b4\ub0b4\ub294 \uac83\uc740 \ub9e4\uc6b0 \uc911\uc694\ud55c \uacfc\uc815\uc785\ub2c8\ub2e4. \ubcf8 \uac15\uc88c\uc5d0\uc11c\ub294 \uc2a4\uc704\ud504\ud2b8 \ud504\ub85c\uadf8\ub798\ubc0d \uc5b8\uc5b4\ub97c \uc0ac\uc6a9\ud558\uc5ec ‘\ube14\ub8e8\ub808\uc774 \ub9cc\ub4e4\uae30’\ub77c\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \uc2e4\uc81c \ucde8\uc5c5\uc2dc\ud5d8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c\ub85c, \uc790\ub8cc\uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc744 \ub3d9\uc2dc\uc5d0 \uc774\ud574\ud560 \uc218 \uc788\ub294 \uc88b\uc740 \uae30\ud68c\uac00 \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\uc8fc\uc5b4\uc9c4 ‘\ube14\ub8e8\ub808\uc774 \ub9cc\ub4e4\uae30’ \ubb38\uc81c\ub294 N\uac1c\uc758 \uc601\ud654\uac00 \uc788\uc73c\uba70, \uac01 \uc601\ud654\uc758 \uae38\uc774\ub294 \ubc30\uc5f4 filmLengths<\/code>\uc5d0 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \ub2f9\uc2e0\uc740 \uc774 \uc601\ud654\ub4e4\uc744 \ube14\ub8e8\ub808\uc774\uc5d0 \ub2f4\uc544\uc57c \ud558\uba70, \uac01 \ube14\ub8e8\ub808\uc774\uc758 \ucd5c\ub300 \uc6a9\ub7c9\uc740 maxCapacity<\/code>\ub85c \uc81c\ud55c\ub429\ub2c8\ub2e4. \ube14\ub8e8\ub808\uc774\uc758 \uc218\ub97c \ucd5c\uc18c\ud654\ud558\uba70 \ubaa8\ub4e0 \uc601\ud654\ub97c \ub2f4\ub294 \ubc29\ubc95\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n

\ud568\uc218 \uc11c\uba85\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n

func minimumBluRays(filmLengths: [Int], maxCapacity: Int) -> Int<\/code><\/pre>\n
\uc785\ub825 \uc608\uc2dc<\/h2>\n
let films = [90, 85, 75, 60, 120]\nlet maxCap = 180<\/code><\/pre>\n
\ucd9c\ub825 \uc608\uc2dc<\/h2>\n
minimumBluRays(filmLengths: films, maxCapacity: maxCap) \/\/ \uacb0\uacfc: 3<\/code><\/pre>\n
\uc811\uadfc \ubc29\ubc95<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub450 \uac00\uc9c0 \uc811\uadfc \ubc29\ubc95\uc744 \uace0\ub824\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
    \n
  1. \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998(Greedy Algorithm)<\/strong>: \uc601\ud654\uc758 \uae38\uc774\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud55c \ud6c4 \uac00\uc7a5 \uae34 \uc601\ud654\ub97c \ub098\uba38\uc9c0 \uc601\ud654\ub4e4\uacfc \ub3d9\uc2dc\uc5d0 \ube14\ub8e8\ub808\uc774\uc5d0 \ub2f4\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ubc29\ubc95\uc73c\ub85c \ub9e4\ubc88 \ucd5c\ub300\ud55c\uc758 \uc601\ud654\ub97c \ube14\ub8e8\ub808\uc774\uc5d0 \ub2f4\uc544\uac00\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/li>\n
  2. \uc774\uc9c4 \ud0d0\uc0c9(Binary Search)<\/strong>: \ucd5c\ub300\ub85c \ub2f4\uc744 \uc218 \uc788\ub294 \ube14\ub8e8\ub808\uc774 \uc218\ub97c \uc774\uc9c4 \ud0d0\uc0c9\uc73c\ub85c \uacb0\uc815\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uac00\ub2a5\ud55c \ucd5c\ub300 \ube14\ub8e8\ub808\uc774 \uc218\uc758 \ubc94\uc704\ub97c \uc124\uc815\ud558\uace0, mid \uac12\uc744 \uae30\uc900\uc73c\ub85c \ud544\uc694\ud55c \ube14\ub8e8\ub808\uc774 \uc218\ub97c \uce74\uc6b4\ud2b8\ud569\ub2c8\ub2e4. \uc774 \ubc29\uc2dd \uc5ed\uc2dc \ud6a8\uc728\uc801\uc778 \ud574\uacb0\ucc45\uc774 \ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \ud574\uacb0 \uacfc\uc815<\/h2>\n
    \uc5ec\uae30\uc11c\ub294 \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \uc790\uc138\ud788 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
    1\ub2e8\uacc4: \uc601\ud654 \uc815\ub82c<\/h3>\n
    \uba3c\uc800 \uc8fc\uc5b4\uc9c4 \uc601\ud654 \uae38\uc774\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4. \uc774\ub807\uac8c \ud558\uba74 \uac00\uc7a5 \uc9e7\uc740 \uc601\ud654\ubd80\ud130 \ucc28\ub840\ub85c \ube14\ub8e8\ub808\uc774\uc5d0 \ub2f4\uc73c\uba74\uc11c, \uac00\uc7a5 \uae34 \uc601\ud654\uc640 \ub098\uba38\uc9c0 \uc601\ud654\ub97c \uc870\ud654\ub97c \uc774\ub8e8\uac8c \ubc30\uce58\ud558\ub294 \uac83\uc774 \uac00\ub2a5\ud569\ub2c8\ub2e4.<\/p>\n
    let sortedFilms = filmLengths.sorted()<\/code><\/pre>\n
    2\ub2e8\uacc4: \ube14\ub8e8\ub808\uc774 \ubc30\uce58 \ub85c\uc9c1 \uad6c\ud604<\/h3>\n
    \uac01 \ube14\ub8e8\ub808\uc774\uc5d0 \uc601\ud654\ub4e4\uc744 \ub2f4\uc744 \uc218 \uc788\ub294\uc9c0 \ud310\ub2e8\ud558\ub294 \ub85c\uc9c1\uc744 \uad6c\ud604\ud569\ub2c8\ub2e4. \ube14\ub8e8\ub808\uc774\uc758 \ud604\uc7ac \uc6a9\ub7c9\uc744 \uad00\ub9ac\ud558\uba74\uc11c, \ucd94\uac00\ud560 \uc601\ud654\uac00 \uc6a9\ub7c9\uc744 \ucd08\uacfc\ud558\uc9c0 \uc54a\ub294\ub2e4\uba74 \ud574\ub2f9 \ube14\ub8e8\ub808\uc774\uc5d0 \ub2f4\uc2b5\ub2c8\ub2e4. \uc6a9\ub7c9\uc744 \ucd08\uacfc\ud55c\ub2e4\uba74 \uc0c8\ub85c\uc6b4 \ube14\ub8e8\ub808\uc774\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4.<\/p>\n
    \nvar bluRayCount = 1\nvar currentCapacity = 0\n\nfor film in sortedFilms {\n    if currentCapacity + film <= maxCapacity {\n        currentCapacity += film\n    } else {\n        bluRayCount += 1\n        currentCapacity = film\n    }\n}\n<\/code><\/pre>\n
    3\ub2e8\uacc4: \uc804\uccb4 \ucf54\ub4dc<\/h3>\n
    \uc704\uc758 \ub2e8\uacc4\ub4e4\uc744 \uc885\ud569\ud558\uc5ec \ucd5c\uc885 \ucf54\ub4dc\ub97c \uc644\uc131\ud569\ub2c8\ub2e4.<\/p>\n
    \nfunc minimumBluRays(filmLengths: [Int], maxCapacity: Int) -> Int {\n    let sortedFilms = filmLengths.sorted()\n    var bluRayCount = 1\n    var currentCapacity = 0\n\n    for film in sortedFilms {\n        if currentCapacity + film <= maxCapacity {\n            currentCapacity += film\n        } else {\n            bluRayCount += 1\n            currentCapacity = film\n        }\n    }\n    return bluRayCount\n}\n\n\/\/ \uc0ac\uc6a9 \uc608\nlet films = [90, 85, 75, 60, 120]\nlet maxCap = 180\nprint(minimumBluRays(filmLengths: films, maxCapacity: maxCap)) \/\/ \uacb0\uacfc: 3\n<\/code><\/pre>\n
    \uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
    \uc774 \uc194\ub8e8\uc158\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N log N)\uc785\ub2c8\ub2e4. \uc601\ud654 \uae38\uc774\ub97c \uc815\ub82c\ud558\ub294 \ub370 O(N log N)\uc774 \ud544\uc694\ud558\uba70, \uadf8 \uc774\ud6c4\uc758 \ubc18\ubcf5\uc5d0\uc11c\ub294 O(N) \uc2dc\uac04\uc774 \uc18c\uc694\ub429\ub2c8\ub2e4. \ub530\ub77c\uc11c \uc804\uccb4\uc801\uc73c\ub85c \ud6a8\uc728\uc801\uc778 \ud574\uacb0\ucc45\uc785\ub2c8\ub2e4.<\/p>\n
    \uacb0\ub860<\/h2>\n
    \ubcf8 \ubb38\uc81c\ub294 \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \ub9ce\uc774 \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c\uc774\uba70, \uadf8\ub9ac\ub514 \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud6a8\uacfc\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ubb38\uc81c\ub97c \uc774\ud574\ud558\uace0 \uc811\uadfc \ubc29\ubc95\uc744 \uc798 \uc124\uc815\ud558\uc5ec \uc5f0\uc2b5\ud55c\ub2e4\uba74, \ub2e4\uc591\ud55c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc88b\uc740 \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218 \uc788\uc744 \uac83\uc785\ub2c8\ub2e4. \uc2a4\uc704\ud504\ud2b8 \uc5b8\uc5b4\uc758 \ud2b9\uc9d5\uc744 \uc775\ud788\uba70 \uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ub0b4\ub294 \uc5f0\uc2b5\uc744 \uc9c0\uc18d\uc801\uc73c\ub85c \ud574\ubcf4\uc138\uc694.<\/p>\n
    \ucc38\uace0 \ubb38\ud5cc<\/h2>\n