개발해요

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

안녕하세요, 이륙사입니다.

풀이

위 문제는 DFS를 사용하는 그래프 탐색 문제였습니다. 하지만 골드3에 정답률이 20퍼센트대인 것을 보아, 기본적인 DFS 문제와는 조금 다르다는 것을 짐작할 수 있는데요.

움직일 수 있는 경우의 수

먼저, 특정 위치에서 상하좌우로 한 칸씩 이동하는 것이 아니라 k칸씩 이동이 가능합니다. 즉, 아래 그림의 X표시된 곳으로 한번에 점프해서 이동할 수 있습니다. 따라서 k <= 5이므로, 매 위치마다 4 * 5 = 최대 20가지의 움직임이 가능합니다.

중복 방문

또 특이한 점은 갔던 곳을 다시 갈 수 있다는 것입니다. 중복해서 방문할 수 있기 때문에 현재 조건만 봐선 DFS가 아니라 매 위치마다 방문 가능한 모든 곳을 탐색하는 brute force 문제로 보는게 더 정확할 것 같습니다.

그럼 전부 확인하면서 풀 수 있을지 알아보기 위해 시간 복잡도를 계산해보겠습니다.

• 최대 노드 개수 = N * M = 10,000개,
• 매 위치마다 방문을 고려할 가지수 = 20개
• 단어 길이 <= 80

최대 80번을 움직이는데 한 번 움직일 때마다 20곳을 고려해야 하므로, 10,000 * 20 ^ 80 = 100자리가 넘는 수가 나옵니다. 따라서, 전부 확인하는 방식으로는 시간안에 해결할 수가 없습니다. 그러면 어떻게 시간을 단축시킬 수 있을까요?

📌3차원 그래프

2차원 그래프가 주어졌지만, 사실은 3차원 그래프로 생각할 수 있습니다. 같은 위치를 방문하더라도 영단어의 몇 번째 인덱스에 쓰였느냐에 따라 다른 노드로 볼 수 있기 때문입니다.

예) 단어: "ABAB", K = 2

ABAB를 찾고 있고, (0, 1)에서 탐색을 시작하는 상황을 가정해보겠습니다. 그러면 B인 (0, 0), (0, 2), (1, 1)로 갈 수 있는데, (0, 0)으로 가보겠습니다. K=2이므로, (0, 1), (1, 0), (2, 0)으로 갈 수 있습니다. 그리고 문제의 중복 상황인 (0, 1)로 다시 가보겠습니다. (0, 1) -> (0, 0) -> (0, 1)이 됐습니다. 여기서 3개의 B로 갈 수 있으므로 3개의 ABAB 경로를 찾을 수 있습니다. 즉, (0, 1)을 ABAB의 3번째 순서(인덱스 2)로 방문하면 언제나 3개의 경로를 찾을 수 있다는 뜻입니다. 이것을 기록해놓으면 (1, 2) -> (0, 2) -> (0, 1)의 경로로 탐색을 할 경우 3개의 B에 다시 방문하지 않더라도 3개의 경로가 있다는 것을 바로 알 수 있습니다. => 메모이제이션

경로를 못찾았던 위치도 마찬가지로 0을 기록해서 해당 위치를 특정 순서로 방문하면 더이상 탐색하지 않을 수 있습니다.

쉽게 말하면 같은 (0, 1)의 A를 방문하더라도 이것을 ABAB[0]으로 사용했는지 ABAB[2]로 사용했는지에 따라 다른 노드가 되는 것입니다. 우리가 같은 방안에 있더라도 그 날짜가 오늘이었는지 어제였는지에 따라 다른 상태라고 생각하면 이해하기 편할 것 같네요. 

따라서 이 문제는 [행][열][인덱스]로 구성된 3차원 그래프 DFS + 다이나믹프로그래밍 혹은 DFS + 메모이제이션 문제였습니다. 

※ BFS를 사용하면 큐에 너무 많은 데이터가 들어가서 메모리 초과가 난다고 하네요!

※ 각 위치를 노드로 표현해보면 Node(문자, 행, 열, 인덱스)로 할 수 있습니다.

생각 과정

1. 영단어 경로를 찾기 조건을 만족하는 노드들을 방문하는 그래프 탐색문제라는 것을 확인한다.
2. 특정 위치에서 이동 가능한 경우의 수와 중복 방문이 가능하다는 것을 확인하고, 완전 탐색으로 풀었을 때의 시간 복잡도를 계산해본다.
3. 시간 복잡도가 정말 크다. 복잡도를 줄이기 위한 추가 고려 사항을 생각해본다.
4. 특정 노드를 방문하더라도 단어의 몇 번째 문자를 확인하느냐에 따라 node state가 다르다는 것을 이해한다.
5. 따라서 index까지 고려하는 3차원 그래프 탐색문제이다. 중복 방문 처리가 가능하기 때문에 시간을 단축시킬 수 있다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

var answer = 0
var rowSize = 0
var colSize = 0
lateinit var target: CharArray // 찾으려는 영단어 문자 배열
lateinit var board: Array<CharArray> // 2차원 그래프
val dNext = mutableListOf<Pair<Int, Int>>()
lateinit var visited: Array<Array<IntArray>> // 3차원 그래프 -> [row][col][몇번째에 도착했는지]

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    rowSize = st.nextToken().toInt()
    colSize = st.nextToken().toInt()
    val moveLimit = st.nextToken().toInt()
    board = Array<CharArray>(rowSize) {
        readLine().toCharArray()
    }
    target = readLine().toCharArray()
    
    // -1: 첫 방문, 0: 방문했었지만 경로가 없었다, 1 이상: 발견한 경로 수
    visited = Array(rowSize) {
        Array(colSize) {
            IntArray(target.size) { -1 } 
        }
    }

    // 상하좌우 K칸 이동 경우의 수
    for (i in 1..moveLimit) {
        val up = Pair(-i, 0); val down = Pair(i, 0)
        val left = Pair(0, -i); val right = Pair(0, i)
        dNext.addAll(listOf(up, down, left, right))
    }

    // 모든점을 시작점으로 탐색
    for (i in 0 until rowSize) {
        for (j in 0 until colSize) {
            if (board[i][j] == target[0]) {
                answer += findRouteCount(i, j, 0)
            }
        }
    }

    print(answer)
}

fun findRouteCount(row: Int, col: Int, index: Int): Int {
    if (index == target.size - 1) { // 단어를 찾았다
        return 1
    }

    var count = 0 // 지금 위치에서 찾을 수 있는 경로 수를 저장할 변수

    for (i in dNext.indices) {
        val nextRow = row + dNext[i].first
        val nextCol = col + dNext[i].second

        if (nextRow !in 0 until rowSize || nextCol !in 0 until colSize) continue
        if (board[nextRow][nextCol] != target[index + 1]) continue // 그래프 범위 밖
 
        // 이전에 방문한 곳일 경우
        if (visited[nextRow][nextCol][index + 1] != -1) {
            count += visited[nextRow][nextCol][index + 1]
            continue
        }

        count += findRouteCount(nextRow, nextCol, index + 1)
    }

    // 경로를 찾지 못했으면 0, 찾았으면 0보다 큰 수가 저장된다
    visited[row][col][index] = count
    return count
}

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

풀이

이전 항으로 다음 항의 값을 구할 수 있는 다이나믹 프로그래밍 문제이다.

문제의 상황을 수식으로 나타내보면 다음과 같다.

이렇게 되는 경우의 수를 dp[k][N]이라고 할 떄, 위에 수식은 아래처럼 다시 바꿔서 표현할 수 있다.

L이라는 값을 미리 더해서 (0 ~ n-L)까지 k-1개의 숫자를 더해서 N-L을 만드는 경우의 수를 구하는 상황으로 바꿀 수 있고, k-1개로 묶인 부분이 dp[k-1][N-L]이 된다.

그러면 dp[k][N] = sum( dp[k-1][N-L] ) (0 <= L <= N)이라는 점화식을 만들어낼 수 있는데, 변수가 3개이므로 3중 반복문을 사용해서 구현할 수 있다.

dp[k][N]의 식을 조금 살펴보면,

k = 1일 때 즉, 숫자 하나로 N을 만드는 경우의 수는 N이 무엇이든 항상 N 하나이므로 dp[1][N] = 1이다. 그리고 이게 초기 값이 된다.

n =0일 때는 숫자가 몇 개든지 0만 더해지는 경우밖에 없다. 따라서 dp[k][0] = 1이다. 

ex) dp[4][0] = 1 (0 + 0 + 0 +0)

그리고 이것들이 dp의 초기 값이 된다.

머리로만 하면 이해가 잘 안될 수도 있어서 직접 해보는 게 좋다. 내가 그랬다ㅋ_ㅋ

ex) n = 6, k = 4일 때 반복문 결과

계산하다 보면 dp[k][n] = dp[k][n-1] + dp[k-1][n] 이라는 특이한 구조를 발견할 수 있다. 이 점화식을 사용하면 변수가 두 개라서 이중반복문으로 좀 더 빠르게 구현이 가능하다!

삼중반복문이 처음엔 머리에 잘 안들어왔었는데, 직접 해보는게 이해에 도움이 많이 됐던 문제다.

코드1 (삼중 반복문)

fun main(){
    val input = readLine()!!.trim().split(" ")
    var n = input[0].toInt()
    var k = input[1].toInt()
    val dp = Array(k+1){IntArray(n+1)}

    for (i in 0..n) dp[1][i] = 1

    for (i in 2..k){		// 행: 더하는 숫자 개수
        for (j in 0..n){	// 열: 더해서 나와야 하는 값
            for (m in 0..j){
                dp[i][j] += dp[i-1][j - m] // 직전 행의 처음~현재 열까지 더한다.
                dp[i][j] %= 1_000_000_000
            }
        }
    }
    
    println(dp[k][n])
}

코드2 (재귀)

lateinit var dp: Array<IntArray>

fun main() {
    val input = readLine()!!.trim().split(" ")
    var n = input[0].toInt()
    var k = input[1].toInt()
    dp = Array(k+1){IntArray(n+1)}

    for (i in 0..n){
        dp[1][i] = 1	// 더하는 숫자가 하나일 때
    }

    println(findAnswer(n, k))
}

private fun findAnswer(n: Int, k:Int): Int {
    if (dp[k][n] != 0) return dp[k][n]

    for (i in 0..n){
        dp[k][n] += findAnswer(n-i, k-1)
        dp[k][n] %= 1_000_000_000
    }

    return dp[k][n]
}

코드3 (이중 반복문)

fun main(){
    val input = readLine()!!.trim().split(" ")
    var n = input[0].toInt()
    var k = input[1].toInt()
    val dp = Array(k+1){IntArray(n+1)}

    for (i in 1..k) dp[i][0] = 1 // 합한 값이 0인 경우는 항상 한 가지이다
    for (i in 1..n) dp[0][i] = 0 // dp[1][i] = 1로 세팅하고, 반복문을 2..k으로 시작하는 거랑 같음 

    for (i in 1..k){
        for (j in 1..n){
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
            dp[i][j] %= 1_000_000_000
        }
    }

    println(dp[k][n])
}

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

코드

포도주 시식 문제(https://www.acmicpc.net/problem/2156)와 정말 비슷하다.

포도주 시식 포스팅: (https://best-human-developer.tistory.com/19)

다른 점이 하나 있는데, 포도주 문제에서는 i번째 포도주를 선택하지 않아도 되지만 계단 오르기에서는 i번째 계단을 반드시 밟아야 한다. i번째 계단을 밟지 않는 경우를 포함시키면 3칸 이상을 건너뛰는 상황이 발생해서, 한 번에 한 계단 또는 두 계단씩만 오를 수 있다는 조건1을 만족시키지 못하기 때문이다.

따라서,

함수) dp[i]: i번째 계단까지만 존재할 때, 조건1,2,3을 만족하는 최대 점수

점화식) i번째 계단 + i-1번째 계단을 밟는 경우와 i번째 계단 + i-2번째 계단을 밟는 경우 중 최대 값

-> dp[i] = max( stair[i] + stair[i-1] + dp[i-3] , stair[i] + dp[i-2] ) 

초기값) dp[0] = 1, dp[1] = stair[1], dp[2] = stair[1] + stair[2]

와 같이 반복문을 구성하면, 초기 값부터 조건을 만족하면서 모든 경우의 수를 포함하기 때문에 dp[3] ~ dp[n]까지 답을 구할 수 있다.

정답) dp[n]

풀이

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val stairs = IntArray(n+2)	// n+2: 초기 값 설정할 때 인덱스 에러를 막는다 
    val dp = IntArray(n+2)

    repeat(n) { i ->
        stairs[i+1] = readLine()!!.toInt()
    }

    dp[1] = stairs[1]
    dp[2] = stairs[1] + stairs[2]
    for (i in 3..n){
        // 직전 계단+현재 계단, 두 칸 전 계단+현재 계단 중 최대 값
        // 현재 계단을 밟지 않는 경우도 포함시키면, 세 칸 이상을 뛰어넘는 경우가 발생한다
        dp[i] = max(stairs[i] + stairs[i-1] + dp[i-3], stairs[i] + dp[i-2])
    }

    println(dp[n])
}

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

풀이

어떤 방법을 써야 할까?

1 <= n <= 100,000이므로 모든 경우를 탐색해보면 시간초과가 나고, 정렬을 해서 푸는 문제도 아닌 듯 하다. 따라서, 이분 탐색을 사용하는 문제는 아니고, 그리디한 방법도 떠오르진 않는다.

접근 방법에 대해 생각해봤는데, 사실 이 문제는 다이나믹 프로그래밍을 사용하는 것으로 유명한 문제 중 하나이다.

나는 다이나믹 프로그래밍 문제를 다음과 같은 절차로 풀려고 한다.

1. 반복문에서 사용할 점화식을 찾기 위해 함수를 정의한다. 

-> dp[i]: 배열이 i번째 까지만 있을 때, 시작 위치가 어디든 number[i]로 끝나는 최대 연속합 (number[?] ~ number[i])

ex) 2, 1, -4, 3, 4, -4, 6, 5, -5, 1 -> dp[2] = -1, dp[3] = 3

2. 문제에 따라서 아무것도 없는 상태(ex: 0) or 첫 인덱스의 값을 초기 값으로 설정한다.

-> dp[0] = number[0]

3. (2.)를 고려해서, 모든 경우의 수를 커버할 수 있는 점화식을 찾는다. 

-> dp[i] = {

                if (dp[i-1] < 0) number[i] 

                else) dp[i-1] + number[i]

              }

             < == > max( dp[i - 1] + number[i] , number[i] ) 

(수학적 귀납법과 같다!)

음수가 키포인트이지만, number[i]가 아니라 dp[i-1]이 음수인지의 여부가 중요하다. number[i]가 음수일지라도 dp[i-1]이 양수이면 dp[i] = dp[i-1] + number[i]이어야 한다. 그래야 1, -4, 3, 4, -4, 6, 5, -5, 1에서 3, 4, -4, 6, 5를 찾아낼 수 있다. 반면에 number[i]가 무슨 값이든 dp[i-1]이 음수이면, dp[i] = number[i]이다. 위 예시의 dp[3]에서 확인할 수 있다.

그리고 함수의 정의에 의해, dp 값들 중 최대 값이 답이 된다.

함수랑 점화식을 어떻게 잘 정의할 수 있을까?

경험의 영역인 것 같다. 나는 처음에 정말 모르겠어서 머리 깨져가면서 여러 문제 풀고, 이해하고, 다른 사람들 코드도 보니까 조금 익숙해졌다. dp는 몰아서 푸는 게 도움되는 것 같다.

코드

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val number = readLine()!!.trim().split(" ").map { it.toInt() }
    val dp = IntArray(n) { i -> number[i] }

    var answer = number[0]
    for (i in 1 until n) {
        if (dp[i - 1] < 0) dp[i] = number[i]
        else dp[i] = dp[i - 1] + number[i]
        // dp[i] = max(number[i], dp[i - 1] + number[i])와 같음
        
        answer = max(answer, dp[i])

        /* 틀렸던 코드
        if (0 <= number[i]){
            dp[i] = max(dp[i], dp[i-1] + number[i])
            answer = max(answer, dp[i])
        }
        */
    }

    println(answer)
}