Hyun's_Devlog

https://www.acmicpc.net/problem/2294

직전에 풀었던 15988번 문제와 비슷하면서도 고민을 해봐야 하는 문제였다. 결국 다른 분의 풀이를 보고서 정답을 얻을 수 있었다.

풀이

배열 dp는 k개의 요소로 구성된 배열이며 dp[k]는 k원을 만들 수 있는 동전의 개수를 담고 있다.

dp[0]은 0원을 만들 수 있는 동전의 개수. 즉 0개부터 시작한다. 이후 동전을 담아놓은 배열을 순회하면서 dp를 갱신한다.

예제를 예시로 들겠다. 1원 5원 12원 동전이 있고, 목표 액수는 15원이다. 

우선 1원만 사용하여 dp배열을 갱신하면 아래와 같다.

다음으로 5원을 사용하여 dp배열을 갱신하면 다음과 같다.

사용할 동전의 가치가 coin원이고, 목표금액이 k원이라면 dp 배열의 요소 dp[k]는 dp[k-coin]+1로 갱신이 가능하며, 이를 통해 더 작은 값으로 갱신해주면 된다. 

즉 coin번째 배열부터 시작하여 갱신을 시작하면 되며, dp[0] = 0 인 상태에서 점화식은 다음과 같이 세울 수 있다.

점화식

dp[k] = min( dp[k], dp[k-coin]+1 )

코드

import Foundation

let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
var k = nk[1]

var dp = Array(repeating:10001, count:10001)
dp[0] = 0
var coins = [Int]()
for _ in 0..<n{
    let coin = Int(readLine()!)!
    if coin <= 10000{ coins.append(coin) }
}
//coins = coins.sorted(by: <)

for coin in coins{
    for i in coin...10000{
        dp[i] = min(dp[i], dp[i-coin]+1)
    }
}
if dp[k] == 10001{
    print(-1)
}else{
    print(dp[k])
}

문제를 풀 당시 coins배열을 오름차순 정렬했는데, 풀이를 적다 보니 coin의 오름차순 정렬은 할 필요가 없다는 것을 깨달았다.

https://www.acmicpc.net/problem/15988

대표적인 동적 계획법 문제이다. 동적 계획법은 항상 마주할 때마다 느끼듯이 점화식을 고민하는 데에 너무 오랜 시간이 걸린다. 더 많은 문제들을 풀어봐야 하나 보다.

풀이

정답을 표현할 배열 dp는 n+1개의 요소를 가지는 배열이며, dp[n]은 "1,2,3을 사용하여 n을 만들 수 있는 식의 개수"라고 정의한다.

점화식을 사용하기 위해서 배열에 최소 3개의 요소가 담겨있어야 한다. 1부터 3까지의 경우의 수를 적어보면 다음과 같다.

이후 1,2,3을 이용해 4를 만드는 식을 만든다고 가정할 경우, 다음과 같은 생각을 해볼 수 있다.

1. 1을 만들 수 있는 모든 식에 "+3"을 추가한다면 4를 만들 수 있다.
2. 2를 만들 수 있는 모든 식에 "+2"를 추가한다면 4를 만들 수 있다.
3. 3을 만들 수 있는 모든 식에 "+1"을 추가한다면 4를 만들 수 있다.

따라서 다음과 같은 점화식을 세울수있게된다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

다만 문제를 보면 알 수 있듯이 n의 크기가 1,000,000이므로 정답을 출력할 때 1,000,000,009로 나눈 나머지를 출력하라고 적혀있다.

모듈러 산술 연산법칙은 분배 법칙이 성립하므로 코드를 적을 때는 다음과 같이 적는다.

dp[n] = ((dp[n-1]%1,000,000,009) + (dp[n-2]%1,000,000,009) + (dp[n-3]%1,000,000,009))%1,000,000,009

정답 코드

import Foundation

var dp = Array(repeating: 0, count: 1000001)
dp[1] = 1
dp[2] = 2
dp[3] = 4
let mod = 1000000009

for i in 4...1000000{
    dp[i] = ((dp[i-1]%mod) + (dp[i-2]%mod) + (dp[i-3]%mod))%mod
}

for _ in 0..<Int(readLine()!)!{
    let n = Int(readLine()!)!
    print(dp[n])
}

https://www.acmicpc.net/problem/1890

풀이

동적 계획법 문제이다. 처음에는 깊이 우선 탐색으로 시도했으나 시간 초과가 발생. 동적 계획법 문제로 분류되어있는 걸 확인하고 난 후 고민했으나, 결국 다른 사람의 풀이과정을 이해하고 코드를 다시 작성하였다.

시간 초과 코드

import Foundation

let n = Int(readLine()!)!

var map = Array(repeating: [Int](), count: n)
for i in 0..<n{
    map[i] = readLine()!.split(separator: " ").map{Int($0)!}
}
var ans = 0

func dfs(x:Int, y:Int){
    if map[x][y]==0{
        if x==n-1 && y==n-1{
            ans += 1
        }
        return
    }
    let length = map[x][y]
    if x+length<n{
        dfs(x: x+length, y: y)
    }
    if y+length<n{
        dfs(x: x, y: y+length)
    }
}
dfs(x: 0, y: 0)
print(ans)

해결 코드

import Foundation

let n = Int(readLine()!)!

var map = Array(repeating: [Int](), count: n)
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in 0..<n{
    map[i] = readLine()!.split(separator: " ").map{Int($0)!}
}

dp[0][0]=1
for x in 0..<n{
    for y in 0..<n{
        if map[x][y]==0 || dp[x][y]==0{continue}
        let nx = x + map[x][y]
        let ny = y + map[x][y]
        if nx<n{ dp[nx][y] += dp[x][y]}
        if ny<n{ dp[x][ny] += dp[x][y]}
    }
}
print(dp[n-1][n-1])

https://www.acmicpc.net/problem/6588

풀이

소수 판별 문제이다. 문제를 보고서 소수 배열과 투 포인터를 사용하여 풀이를 제출했으나 시간 초과가 나왔다.

문제를 해결하기 위해서는 소수 배열의 작은 숫자부터 n의 차를 구한 수를 소수인지 판별하는 방법으로 해결해야 한다는 게시글을 보고서 다시 제출하였더니 통과했다.

시간 초과 코드

import Foundation

var numbers = Array(repeating: true, count: 1000001)
var primes = [Int]()
for i in 0..<1000001{
    if i <= 1{
        numbers[i] = false
        continue
    }
    if numbers[i]{
        if i != 2{
            primes.append(i)
        }
        for k in stride(from: i+i, to: 1000001, by: +i){
            numbers[k] = false
        }
    }
}

while let input = readLine(){
    let n = Int(input)!
    if n == 0{ break }
    
    var flag = false
    var start = 0
    var end = primes.count-1
    while start < end{
        let sum = primes[start] + primes[end]
        if sum > n{
            end -= 1
            continue
        }else if sum == n{
            flag = true
            break
        }else{
            start += 1
        }
    }
    if flag{
        print(n,"=",primes[start],"+",primes[end])
    }else{
        print("Goldbach's conjecture is wrong.")
    }
}

해결 코드

import Foundation

var primes = Array(repeating: true, count: 1000001)

for i in 0..<1000001{
    if i <= 1{
        primes[i] = false
        continue
    }
    if primes[i]{
        for k in stride(from: i+i, to: 1000001, by: +i){
            primes[k] = false
        }
    }
}

while let input = readLine(){
    let n = Int(input)!
    if n == 0{ break }
    
    var flag = false
    for i in 3..<1000001{
        if primes[i]{
            let chk = n-i
            if primes[chk]{
                flag = true
                print(n,"=",i,"+",chk)
                break
            }
        }
    }
    if !flag{
        print("Goldbach's conjecture is wrong.")
    }
}

심지어 문제를 풀고나서 알아낸 점은 같은 소수의 구성으로도 n을 만들 수 있다면 정답이 될 수 있다는 것이다. 투 포인터를 사용한 코드를 적을 때에 당연히 서로 다른 소수라는 가정을 한 채로 작성했었다. 대표적인 예시가 6을 입력할 경우 투 포인터를 사용한 코드는 불가능한 조합이라는 결과를 출력하지만, 통과했던 코드는 3 + 3 조합을 출력하게 된다.

이번문제도 C++로 작성했던 문제를 swift로 다시 풀어보았다.

https://www.acmicpc.net/problem/1158

풀이

문제에 적힌 방법대로 풀면 된다. 대신 기존의 배열에서 제거하는 방법이 아닌 요소를 0으로 변환하면서 배열을 순회했다. 애초에 요소는 1부터 시작하기 때문이다. 배열의 요소가 0이 아니라면 카운트를 증가하지 않고 인덱스만 증가. 카운트가 k값이 되면 그때의 요소를 요세푸스 배열에 담는 방식으로 문제를 풀어보았다.

풀고나서 다른 사람들의 풀이를 보니 간결하고 빠른코드가 많았다.

http://boj.kr/ef42c280ec1c4098b04deca633c2b1dc

//
//  main.swift
//  1158_swift
//
//  Created by Hyun on 2022/01/20.
//

import Foundation

let NK = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = NK[0]
let K = NK[1]

var arr = Array(1...N)
var josephus = [Int]()

var cnt = 0
var idx = -1

while josephus.count < arr.count{
    cnt += 1
    idx += 1
    if idx >= arr.count{
        idx = 0
    }
    if arr[idx] == 0{
        while arr[idx] == 0{
            idx += 1
            if idx >= arr.count{
                idx = 0
            }
        }
    }
    if cnt == K{
        josephus.append(arr[idx])
        arr[idx]=0
        cnt = 0
        continue
    }
}

var text = "<"
for j in josephus{
    if j == josephus.last{
        text+=String(j)
    }else{
        text+=String(j)+", "
    }
}
text += ">"
print(text)

알고리즘 공부를 위해 풀었던 첫 백준문제이다. c++로 풀었는데, 이틀동안 문제만 들여다 보다가 결국 답을 검색하고나서 풀게되었다.

처음에 문제를 읽고나서도 이해가 안되서 지문을 수차례 읽었던 기억이 떠오른다. 이번에 스위프트로 재작성하여 공유해본다.

https://www.acmicpc.net/problem/1021

풀이

큐의 변화는 크게 3가지이다.

1. 큐의 가장 첫번째 원소를 제거한다. 

2. 큐의 원소를 좌측으로 회전

3. 큐의 원소를 우측으로 회전

당시 고민했던 부분은 회전수를 최소화하는 것인데, 좌측의 회전수가 나오면 우측의 회전수는 자연스럽게 [큐의 크기 - 좌측회전수]를 통해 알수있게 되어 둘의 크기를 비교한 뒤 값이 적은 방향으로 이동하면 된다.

http://boj.kr/138f9df0ef054fbd8dc48e1fe2274c3d

//
//  main.swift
//  1021_swift
//
//  Created by Hyun on 2022/01/19.
//

import Foundation

let NM = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = NM[0]
let M = NM[1]
var q = Array(1...N)
var ans = 0

let targets = readLine()!.split(separator: " ").map{Int(String($0))!}
for target in targets{
    var left = 0
    var right = 0
    for idx in q.indices{
        if q[idx] == target{
            //회전수 계산하기
            left = idx
            right = q.count-idx
            break
        }
    }
    //회전수를 비교하여 적은 방향으로 회전하기
    if left < right{
        for _ in 0..<left{
            q.append(q.removeFirst())
            ans+=1
        }
    }else{
        for _ in 0..<right{
            q.insert(q.removeLast(), at: 0)
            ans+=1
        }
    }
    //원소 제거
    q.removeFirst()
}
print(ans)