Hyun's_Devlog

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

정답에 닿을 듯 말듯해서 더욱 고생했던 문제다. 메모리 초과를 마주해서 고생하고, 이후 오답으로 인해 한번 더 고생했다.

풀이

문제를 보면 알겠지만 bfs를 두번 수행해야 한다. 본인도 거기까지는 생각했으나, 불의 경로와 지훈이의 경로를 어떻게 합칠 수 있을까에 대한 고민으로 시간을 소모했다. 항상 bfs문제를 만날 때면 Bool값을 통해 방문을 체크하는 visited 배열을 사용하는데, 이번 문제의 핵심은 해당 장소를 몇 초 후에 방문하는가를 저장하는 것이다. 불에 대한 경로탐색을 수행하고 나면 각 좌표에 몇 초 후에 불이 도달하는지 기록되어있다. 이후 지훈이의 경로탐색을 수행하여 불보다 먼저 해당 장소에 도착하는지를 확인하여 배열의 모서리까지 도달하면 된다.

메모리 초과가 일어났던 이유

지훈이의 경로탐색이 수행될 때, 해당 좌표의 방문 여부를 확인하지 않아서 방문했던 좌표도 큐에 담아버려 메모리 초과가 일어났다. 이후 지훈이의 경로탐색에 필요한 check:[Bool] 배열을 통해 방문하지 않았던 배열에 대해서만 경로탐색을 수행하도록 수정하였다.

오답 판정에 대한 이유

이후 71%에서 계속 오답이 발생했다. 원인은 또다시 지훈이의 경로탐색 부분에서 발생했는데, 단순히 불이 도달하는 시간보다 지훈이의 시간이 더 낮은 경우에 대해서만 경로탐색을 수행했으나( if visited[x][y] > current_time ), 애초에 해당 좌표에 불이 번지는 장소가 아닌 경우에는 visited[x][y]의 값은 0이다. 따라서 방문이 가능한 부분인데도 해당 부분에 대해서는 경로탐색을 수행하지 않아 올바르지 않은 답을 내놓게 된다. 해당 오류는 zero_woo님의 블로그를 보고 반례를 찾아 해결할 수 있었다. (해당글)

반례

3 4
###F
.J#.
###.

정답은 2가 출력되어야 하나, 고치기 전의 코드로는 "IMPOSSIBLE"이 출력된다. 불이 번지지 않는 위치에 대한 예외처리를 하지 않아서 오답처리를 받았던 것이다.

코드

import Foundation

let rc = readLine()!.split(separator: " ").map{Int($0)!}
let r = rc[0]
let c = rc[1]

var j = [[Int]]()
var f = [[Int]]()
var map = Array(repeating: Array(repeating: "", count: c), count: r)
var visited = Array(repeating: Array(repeating: 0, count: c), count: r)
var ans = Int.max
for i in 0..<r{
    let input = readLine()!.map{String($0)}
    for k in 0..<c{
        map[i][k] = input[k]
        if map[i][k] == "J"{
            j.append([i,k])
        }else if map[i][k] == "F"{
            f.append([i,k])
        }
    }
}

let dx = [-1,1,0,0]
let dy = [0,0,-1,1]

func bfs(j:[[Int]],f:[[Int]]){
    var level = 0
    var q = f
    var dq = [[Int]]()
    var v = Array(repeating: Array(repeating: false, count: c), count: r)

    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            v[x][y] = true
            visited[x][y] = level
            for i in 0..<4{
                let nx = dx[i] + x
                let ny = dy[i] + y
                if nx<0 || nx>=r || ny<0 || ny>=c || map[nx][ny]=="#"{continue}
                if visited[nx][ny]==0 && !v[nx][ny]{
                    v[nx][ny] = true
                    q.append([nx,ny])
                }
            }
        }
        level += 1
    }
    
    level = 0
    q = j
    dq = [[Int]]()
    v = Array(repeating: Array(repeating: false, count: c), count: r)
    
    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            v[x][y] = true
            if x==0||x==r-1||y==0||y==c-1{
                ans = min(ans, level+1)
            }
            for i in 0..<4{
                let nx = curr[0]+dx[i]
                let ny = curr[1]+dy[i]
                if nx<0 || nx>=r || ny<0 || ny>=c || map[nx][ny] == "#"{ continue }
                if visited[nx][ny] > level+1 && !v[nx][ny]{
                    v[nx][ny] = true
                    q.append([nx,ny])
                }
                if visited[nx][ny]==0 && !v[nx][ny]{
                    v[nx][ny] = true
                    q.append([nx,ny])
                }
            }
        }
        level += 1
    }
}
bfs(j: j, f: f)
print(ans == Int.max ? "IMPOSSIBLE":ans)

비록 해답을 찾아보고 풀게 된 문제이지만, 그래프 탐색에 대한 시야가 아주 조금은 넓어지게 된 문제다.

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)