앱등개발자IOS

백준 12865: 평범한 배낭 (Knapsack문제 / with Swift )

Dynamic Programming문제의 일종으로 매우 유명한 Knapsack 문제 (배낭문제) 이다. 2차원배열의 열은 해당 1~ k(배낭의 최대 수용 무게) 까지 나타내게 되고, 행은 가지고있는 물건의 수만큼 크기를 가진다. (1 ~ n) n은 가지고있는 물건의 갯수 우리는 물건 n개를 차례로 순회하며,dp배열을 업데이트한다. dp[i][j]가 의미하는 것은, i 번째 물건까지 순회했을 때, j만큼의 무게를 채울 때의 가치의 최댓값이 된다. 따라서 현재 순회중인 물건의 무게보다 적은 크기의 무게를 가리키는 열들에 대해서는, 업데이트가 필요 없으므로 이전 행의 값을 그대로 아래로 가지고 내려오면 된다. 현재 순회중인 물건의 무게보다 크거나 같은 무게를 가리키는 열에서는, 1.바로 위의 줄에 있는 값과,..

Swift알고리즘 2023. 9. 22. 15:02

백준 11866: 요세푸스 문제 0 (구현 / with Swift)

Point1: arr.remove(at: idx) 함수로 배열 중간에 있는 원소를 빼내는 것 Point2: arr에 있는 원소들을 지우고, idx값을 늘려가다보면, idx가 arr.count를 넘어가는 경우가 발생한다. 이럴 때는 idx를 arr.count로 나눈 나머지를 idx에 할당해주면 된다.

Swift알고리즘 2023. 9. 20. 20:13

백준 9251: LCS ( 최장 공통 부분수열 {DP} / Swift )

두 개의 부분수열이 주어졌을 때, 가장 긴 공통 부분 수열을 구해야하는 문제이다. ACAYKP와 CAPCAK가 주어진다면 ACAYKP CAPCAK ACAK라는 부분 수열이 있기에 답은 4가 된다. Point 1: arr[i][j]가 나타내는 것은, a문자열의 i번째 요소를 b문자열의 j번째 요소까지 비교하였을 때 최장 공통 부분수열의 길이이다. Point 2: arr[i][j] = arr[i - 1][j - 1] + 1이다. 예를 들면, ACCC와 같이 b문자열이 진행되고, 현재 a문자열에서 C문자를 체크하고 있을 때, C가 나올 때마다 1씩 증가시키는 것은 말이 되지 않는다. 1 222와 같이 진행되는 것이 맞다. Point 3: arr[i - 1]과 b[j - 1]이 일치하지 않는 경우, arr[i]..

Swift알고리즘 2023. 9. 20. 19:39