개발해요

https://programmers.co.kr/learn/courses/30/lessons/49191

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

오늘 프로그래머스에서 순위라는 문제를 풀어봤는데 어렵다는 생각이 들었습니다. 그래서 제 힘으로 풀진 못하고 다른 분들 풀이를 찾아봤는데, 대부분 플로이드 와샬을 사용해서 푸셨더라구요. 그런데 왜 꼭 그래야 하는지가 명쾌하게 나와있지 않아서 좀 답답했습니다. 그러던 중 DFS만을 사용해서 푸신 분이 계셔서 해당 풀이를 공부하고 공유해보려고 합니다. 

정리

1. 문제를 그래프로 표현할 수 있다: 선수(노드), 경기(엣지) 승패(엣지 방향)
2. 이길 수 있는 선수 + 지는 선수의 합이 n-1인 선수는 순위가 확정된 것이다.
3. 각 선수마다 누구에게 이기고 지는지를 모두 확인한다. 즉, (a > b), (b > c) -> (a > c) 처럼 건너 관계까지 모두 확인한다. --> DFS를 사용한다
4. a > b를 확인할 때, 반대로 b < a 라는 정보도 확인할 수 있다. 즉, 각 선수마다 이기는 정보에 대한 DFS 탐색을 진행하면 지는 관계까지 모두 확인할 수 있다. --> 그러므로 각 선수를 시작노드로 각각 DFS를 진행한다

풀이

두 선수가 이기고 지는 관계를 그래프의 노드, 엣지, 엣지방향으로 나타낼 수 있습니다.

엣지 방향을 어떻게 하든 상관 없지만 저는 노드에서 나가는 방향이 이기는 것, 들어오는 방향이 지는 것으로 표현했습니다. 대회에서 이기면 경기를 더 치룰 수 있지만 지면 짐싸서 집으로 돌아와야 하기 때문이죠. 물론 문제에선 그렇지 않지만요!ㅋㅋ

그래프

근데 왜 그래프로 생각해야 할까요? '그냥 그렇게 하는게 자연스러우니까, 당연하니까, 문제 분류가 그래프니까' 라고 생각할 수도 있지만, 나름의 이유를 부여할 수도 있습니다.

이를 단순 리스트로 표현하면 [1, 3], [3, 2]가 됩니다. 그리고 이 정보만으론 순위를 판별할 수 없습니다. 그냥 '1 > 3, 3 > 2 이니까 당연히 1  > 2고, 1 > 3 > 2가 되지'라고 생각할 수 있지만, 사실 이것이 그래프적으로 사고한 겁니다. (1 -> 3), (3 -> 2)의 과정을 거친것이죠. 단순 배열처럼 생각한다면 그 너머에 있는 관계까지 파악하는 것이 힘듭니다.

키 포인트

그리고 이것이 문제의 핵심 키포인트입니다. 건너건너 연결된 관계까지 모두 확인해야만 경기 결과 속에 숨어있는 모든 순위 관계를 파악할 수 있습니다. 그리고 이 과정에서 DFS가 사용됩니다.내가 이기는 상대가 이기는 상대가 이기는... 을 모두 파악해야 하기 때문입니다.

순위 확정 판별 조건

순위가 확정됐음은 어떻게 판별할 수 있을까요? 우선 모든 관계를 파악합니다. 그리고 n명의 선수들이 있을 때, 특정 선수가 이기는 선수 + 지는 선수 = (n-1)명이라면, 그 선수는 순위가 확정됐다고 판단할 수 있습니다. 그래프에서는, 한 node에서 들어오거나 나가는 edge의 수가 n-1인 node를 의미합니다 (건너건너 포함).

// 순위를 알 수 있는 선수의 수를 센다
for (i in 1..n){
    if (edgeCount[i] == n-1) answer++
}

예를 들어, 1번이 3번을 이기고, 3번이 2번에게 이기면 3번의 입장만 고려했을 때, 3명 중 2명과의 관계를 알고 있으므로 순위가 확정된 것입니다.

DFS

DFS를 사용하여 각 선수마다 내가 이길 수 있는 모든 선수와 내가 지는 모든 선수를 알아냅니다. 그리고 몇 명인지만 알면 되기 때문에 문제는 더 간단해집니다.

각 노드를 시작 노드로 해서 이길 수 있는 모든 선수를 확인합니다. 그리고 그 과정에서 반대로 지는 선수는 그 시작 노드에게 진다는 체크를 해줍니다. 즉, 이기는 노드들에 대한 방문만을 통해 지는 정보까지 모두 알 수 있게 됩니다.

/*
    * src: 이기는 선수 current: 지는 선수, loser: current에게 지는 선수
    * src가 이길 수 있는 모든 선수를 DFS로 확인한다.
    * 이 과정에서 반대로 current들은 src에게 진다는 정보도 알 수 있다.
    */
    private fun countEdgesOf(src: Int, current: Int) {
        for (loser in winList[current]) {
            if (visited[src][loser]) continue
            
            visited[src][loser] = true
            
            // 관계가 n-1개인지만 확인하면 되기 때문에
            // 이기고 지는 경우 상관없이 관계 개수를 카운팅한다.
            count[src]++   // src가 loser를 이긴다
            count[loser]++ // loser는 src에게 진다
            countEdgesOf(src, loser) // 건너 관계를 확인한다.
        }
    }

위의 예를 다시 가져와 보겠습니다. [1, 3], [3, 2]가 입력으로 들어오고, 1에 대해 DFS를 시작합니다.

depth1) 1 -> 3

- 1이 3을 이긴다. (edgeCount[1]++;)

- 3이 1한테 진다. (edgeCount[3]++;)

1에서 3을 방문할 때 1에 대한 정보만이 아닌 3에 대한 정보도 확인할 수 있습니다. 또한, 엣지의 개수만 센다는 것에 주목해주세요. 실제로 필요한건 관계의 개수이기 때문입니다.

depth2) (1 ->) 3 -> 2

앞에 (1 ->)가 있습니다. 1에서부터 시작했다는 의미입니다.

1이 2를 이긴다. (edgeCount[1]++;)

2가 1한테 진다. (edgeCount[2]++;)

정답

이것을 모든 노드에 대해 실행한 후, edgeCount[i] == n-1인 개수를 세면 그것이 답이 됩니다.

코드

class Solution {
    private lateinit var edgeCount: IntArray // 들어오거나 나가는 edge 개수
    private lateinit var visited: Array<BooleanArray> // visited[src][dst]
    private lateinit var winList: Array<MutableList<Int>> // [node]가 이긴 선수들
    
    fun solution(n: Int, results: Array<IntArray>): Int {
        var answer = 0
        edgeCount = IntArray(n+1)
        visited = Array(n+1){
            BooleanArray(n+1)
        }
        winList = Array(n+1) {
            mutableListOf<Int>()
        }
        
        results.forEach {
            val winner = it[0]
            val loser = it[1]
            
            winList[winner].add(loser)
        }
        
        // 모든 관계를 확인한다
        for (i in 1..n) {
            countEdgesOf(i, i)
        }
        
        // 순위를 알 수 있는 선수를 센다
        for (i in 1..n){
        	if (edgeCount[i] == n-1) answer++
        }
        
        return answer
    }
    
    /*
    * src: 이기는 선수 current: 지는 선수, loser: current에게 지는 선수
    * src가 이길 수 있는 모든 선수를 DFS로 확인한다.
    * 이 과정에서 반대로 current들은 src에게 진다는 정보도 알 수 있다.
    */
    private fun countEdgesOf(src: Int, current: Int) {
        for (loser in winList[current]) {
            if (visited[src][loser]) continue
            
            visited[src][loser] = true
            
            // 관계가 n-1개인지만 확인하면 되기 때문에
            // 이기고 지는 경우 상관없이 관계 개수를 카운팅한다.
            edgeCount[src]++   // src가 loser를 이긴다
            edgeCount[loser]++ // loser는 src에게 진다
            countEdgesOf(src, loser) // 건너 관계를 확인한다.
        }
    }
}

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

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

어제 백준에서 구간 나누기2 문제를 풀어봤습니다. 이전에 풀어본 유형이어서 알고리즘은 떠올랐지만 구체적인 풀이법이 떠오르지 않더라구요. 왜 그렇게 풀어야했는지 제대로 이해하지 못하고 넘어갔던 것 같아서 이번 기회에 정리해보려고 합니다.

선 정리

1. 구간을 어떻게 나눌까 -> 반대로 접근해서 구간 점수의 최대값을 기준으로 구간을 나눌 수 있는지 확인한다. -> 이분 탐색
2. 점수 최대값의 범위: 0 ~ (배열 최대값 - 최소값)
3. 구간을 나눌 때, 구간마다 최대한 길게 만든다 -> M개 이하가 될 확률을 높일 수 있음
   1. M개 이하로 나누는데 성공 -> 더 점수를 낮춰도 나눌 수 있는지 확인 -> upper = mid - 1
   2. M개 이하로 나누는데 실패 -> 점수를 더 높여서 확인 -> lower = mid + 1  
   3. 왜? 우리의 목표는 점수 최대 값의 최소값을 구하는 것이며, 구간 당 가능한 점수가 클수록 구간의 길이가 길어질 확률이 높아지기 때문이다. 

후 풀이

언뜻 읽어보면 점수의 최댓값의 최솟값, 말이 좀 복잡해 보입니다. 저는 구간을 나누면 점수가 계산되고 그 중 최댓값이 존재할텐데, 그 최댓값을 최소로 만들고 싶다. 즉, '구간을 어떻게 나눠야 가장 작은 (점수 최댓값: maxScore)을 구할 수 있을까'라고 이해했습니다. 

어떻게 구간을 나눠야 최소값을 얻을 수 있을까에 대한 문제구나 생각하고, 완전 탐색을 먼저 떠올렸습니다. 하지만 M개 이하로 나누기 때문에 시간 복잡도가 팩토리얼 수준으로 나와서 불가능하다고 판단했습니다.

반대로 접근한다

어떻게 해결할 수 있을까,,, 결론적으로 반대로 접근해서 해결할 수 있는 문제였습니다. 즉, 점수 최댓값을 먼저 설정하고, 그걸 기준으로 M개 이하의 구간을 나눌 수 있는지 확인하는 겁니다. 그 과정에서 이분 탐색을 사용합니다.

1. 점수 최대값의 범위는 배열이 하나일 때의 최소값 0에서 배열 내 최대값과 최소값의 차이 즉, 0 ~ (max(array) - min(array))입니다.
2. 이제 점수 (최대값)을 기준으로 구간을 나눠봅니다. 구간마다 최대한 많은 길이를 차지하도록 만듭니다. 왜냐면,
   1. M개 이하로 구간을 나눠야하기 때문에 구간을 최대한 길게 만들수록 성공 확률이 높아집니다.
   2. 앞의 구간에서 최대한 많은 숫자를 가져갈수록, 뒤에 남은 숫자들의 범위가 작아집니다. 그러면 그만큼 뒤에 구간의 점수도 작아질 확률이 높아집니다.
3. M개 이하로 구간을 만들지 못했다면, 점수를 더 크게 해서 구간을 나눌 수 있는지 다시 확인합니다. 반대로 성공했다면, 점수를 더 작게 해도 구간을 나눌 수 있는지 확인합니다. 이렇게 기준을 잡을 수 있는건, 점수가 클수록 구간이 길어질 확률이 높아지기 때문입니다. 즉, 평균적으로 구간마다 더 많은 숫자를 가질 수 있게 됩니다. 그리고, 우리의 목표는 점수 최대값의 최소값을 구하는 것이니까요!

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 입력
    val (n, divideLimit) = readLine().split(" ").map(String::toInt)
    val array = with(StringTokenizer(readLine())){
        IntArray(n){
            this.nextToken().toInt()
        }
    }
    
    var lower = 0
    var upper = array.maxOrNull()!! - array.minOrNull()!!

    if (n == 1) { // 배열 크기가 하나일 때
        print(0)
        return
    } else if (divideLimit == 1) { // 구간 1개 -> 배열을 나눌 수 없을 때
        print(upper - lower)
        return
    }

    // 점수의 최대값을 기준으로 이분 탐색
    // 점수의 최댓값이 mid가 되도록 구간을 가장 길게 나눠본다
    // 나눌 수 있으면 최소값을 찾기 위해 더 작은 최대값을 찾아본다
    // 나눌 수 없으면 더 큰 최대값을 찾는다
    // 구간의 점수가 커질수록 구간이 길어지고 구간 개수가 작아질 확률이 높아진다 
    while (lower <= upper) {
        val mid = (lower + upper) / 2

        if(isValid(array, mid, divideLimit)) {
            upper = mid - 1
        } else {
            lower = mid + 1
        }
    }

    print(lower)
}

fun isValid(array: IntArray, standard: Int, divideLimit: Int): Boolean {
    var count = 0
    var max = 0
    var min = 10_001

    for (i in array.indices) {
        max = max(max, array[i])
        min = min(min, array[i])

        // 최대값 or 최소값이 더 크/작아져서 더 길게 나눌 수 없을 때
        if (max - min > standard) {
            count++
            max = array[i]
            min = array[i]
        }
    }
    count++ // 마지막 구간

    return count <= divideLimit
}

후기

어떻게 생각하면 풀 수 있다는 건 확실히 알게됐지만, 왜 이렇게 접근해야만 하는지는 사실 아직도 와닿지가 않습니다. 이렇게 접근할 수도 있다는 걸 숙지하고, 사고의 폭을 넓혀가야 하는 걸까요? 조금은 답답하기도 한데, 이와 관련해서 댓글로 남겨주신다면 정말 감사하겠습니다.

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

풀이

1. 투포인터 방법(left, right)을 사용한다.
2. 짝수, 홀수 카운팅(evenCount, oddCount)를 위한 변수와 최소 길이를 저장할 정답(answer) 변수를 선언한다. right 포인터는 0부터 시작한다.
3. right 포인터로 홀수를 k+1개 찾을 때까지 숫자를 차례대로 확인하면서 홀, 짝의 개수를 카운팅한다.
4. 홀수가 k+1개가 됐을 때,
   1. 지금의 짝수 개수가 k+1번째 홀수의 왼쪽에 있는 홀수 k개를 지웠을 때의 연속 짝수 길이가 된다. 따라서 이것을 지금까지 구한 정답과 비교한다
   2. left를 현재 구간의 첫번째 홀수 인덱스 + 1이 될 때까지 증가시킨다. 그 과정에서 짝,홀수의 개수를 감소시킨다.
5. 3, 4번 로직을 right가 전체 수의 길이보다 크거나 같아질 때까지 반복한다.
6. 홀수가 k개 이하일 경우를 대비하기 위해, 3,4,5번 반복문 종료 후 eventCount + oodCount == 전체 수의 길이인지 확인한다. true이면 eventCount가 정답이 된다. 

생각 과정과 후기

실버1이었는데 개인적으로 정말 정말 어려웠다.

우선 홀수를 어떻게 지워야 가장 긴 짝수를 만들 수 있을지 고민했다. 그리고 인접한 홀수들을 지울 때 가장 긴 짝수를 구할 수 있을 거라고 생각했다. 왜냐면, 만약 아래처럼 띄엄띄엄 지운 케이스가 정답이라고 가정해보면, 왼쪽에 있는 더 긴 범위가 정답일 것이다. 하지만 오른쪽 범위에서 지운 홀수 대신 가운데에 있는 홀수를 지우면 구간을 만들 수 있기 때문에 가정에 모순이 된다. 그래서 띄엄띄엄 지웠을 때는 정답을 구할 수 없다고 논리적으로도 확신할 수 있었다.

이제 구현만 하면 되는데, 그게 쉽지 않았다.

처음에는 홀수들의 인덱스를 리스트에 따로 저장해서 차례대로 k개를 지울 때마다 연속 짝수의 길이를 구하려고 했다. 하지만 지울 때마다 양 끝에 있는 홀수들의 바깥쪽에 짝수가 있는지, 있다면 몇개나 있는지를 알아내는 것이 쉽지 않았다. 그래도 나름대로 코드를 짜서 돌려봤는데 잘 안됐고, 결국 다른 분들 풀이를 참고했다.

풀이법을 어떻게 떠올릴 수 있었을까?

1. 인접한 홀수들을 왼쪽에서 오른쪽 순서대로 탐색한다 --> 구간을 옮긴다는 개념을 떠올릴 수 있다.

2. 홀수 범위를 알더라도 양 옆에 짝수가 어떻게, 몇 개나 있는지도 알아야 한다 -> 짝, 홀을 모두 고려해야 한다.

==> 순서대로 모든 수를 탐색하면서 + 짝 홀 두 가지를 다 신경써야 한다 + 구간을 옮긴다 -> 투포인터

이런 과정으로 떠올릴 수 있지 않았을까?

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val st = StringTokenizer(readLine())
    val numberSize = st.nextToken().toInt()
    val removeSize = st.nextToken().toInt()
    val numbers = with(StringTokenizer(readLine())) {
        IntArray(numberSize) {
            this.nextToken().toInt()
        }
    }

    var answer = 0
    var left = 0
    var right = 0
    var evenCount = 0
    var oddCount = 0

    while (right < numberSize) {
        if (numbers[right++] % 2 == 0) evenCount++
        else oddCount++

        // k+1번째까지 찾아야 k번째 홀수 오른쪽에 있는 짝수들을 계산할 수 있다.
        if (oddCount > removeSize) {
            answer = max(answer, evenCount)

            // 가장 왼쪽에 있는 홀수를 찾을 때까지 증가시킨다
            while (numbers[left] % 2 == 0){
                left++
                evenCount--
            }
            left++ // 투포인터 범위를 가장 왼쪽에 있던 홀수 오른쪽부터 시작하도록 옮긴다
            oddCount--
        }
    }

    if (evenCount + oddCount == numberSize) {
        answer = evenCount
    }
    print(answer)
}

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

풀이

DP로 풀 수 있을 것 같았는데 방법이 떠오르지 않아서 우선 BFS를 사용했다. 매초마다 이전 위치들에서 도착할 수 있는 모든 위치로 움직이기 때문에 가장 처음 목표지점에 도착했을 때가 최단 시간이 된다.

또한, 곱하기2로 범위를 절반씩 줄일 수 있으므로 O(log^N) 시간으로 문제를 해결할 수 있다

BFS 과정에서 당연하지만 이전에 방문했던 점은 다시 방문하지 않아야 하는데, 이전보다 시간이 더 흐른 상태에서 같은 연산을 반복하기 때문이다. 따라서 방문표시를 할 배열이 필요한데, 크기를 어느 정도로 잡아야할지 고민이 됐다. 예를 들어 50,001 (x2) -> 100,002 (-1) (-1) -> 100,000 와 같이 최대 범위를 초과했다가 마이너스로 가는 경우도 있을 것 같았기 때문이다. 

결과적으로, 50,001 (-1) -> 50,000 (x2) -> 100,000처럼 최대 범위를 넘어서는 경우보단 숫자를 먼저 몇 번 빼고 x2를 하는게 항상 더 빨리 갈 수 있다. 그리고 절반인 50,000을 기준으로 숫자가 커질수록 그 차이는 훨씬 커진다.

ex)

1. 50,004 (x2) -> 100,008 (-8) -> 100,000 ==> 9번

2. 50,004 (-4) ->  50,000 (x2) -> 100,000 ==> 6번

따라서, 방문 가능 범위를 0 ~ 100,000으로 제한해도 문제를 해결할 수 있다.

개인적으로 처음엔 여기까지 생각하지 못해서 안전하게 최대 200,000까지 방문 가능하도록 했는데, 정답을 받을 수 있었다.

이후에 궁금해서 찾아봤는데, 최대 범위를 넘어서는 경우가 없는건 k의 최대 값이 짝수이기 때문이었다.

9 -> 15  ==>  9 -> 8 ->16 -> 15 의 케이스처럼, 최대 값이 홀수라면 최대 값을 넘어서고 마이너스로 가는 케이스가 존재할 수 있기 때문이다.

하지만 처음 문제를 풀 땐 생각하기 어려울 수 있기 때문에, 그럴 땐 범위를 충분히 안전하게 설정해서 푸는 게 좋을 것 같다.     

코드

import java.io.*
import java.util.*

// 250_000을 이상인 모든 수 n은
// (n * 2) 이후 -1씩 계산해주는 것보다
// -1을 먼저 몇 번 빼고 n * 2를 하는 게 항상 더 빠르다
// ex) 250_001 * 2 = 500_002 -> 500_000 ==> 3번 계산
// ex) 250_001 -> 250_000 -> 500_000 ==> 2번 계산
// 250_001에서 수가 커질 수록 차이는 더 커진다.
const val MAX_POSITION = 100_000

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val myPosition = input[0].toInt()
    val goal = input[1].toInt()

    val visited = BooleanArray(MAX_POSITION + 1)    // 방문 처리 배열
    val queue: Queue<Pair<Int, Int>> = LinkedList() // 위치, 지난 시간
    queue.offer(Pair(myPosition, 0))
    visited[myPosition] = true

    while (queue.isNotEmpty()) {
        val pair = queue.poll()
        val position = pair.first
        val time = pair.second

        if (position == goal) { // 동생을 찾았으면 종료
            print(time)
            return
        }

        // -1을 거쳐가는 최단경로는 존재할 수 없다
        val nextPosition1 = position - 1
        if (nextPosition1 >= 0 && visited[nextPosition1].not()) {
            visited[nextPosition1] = true
            queue.offer(Pair(nextPosition1, time + 1))
        }

        // 현재 위치가 동생의 위치보다 크면 증가 연산을 할 필요가 없다.
        if (position < goal) {
            val nextPosition2 = position + 1
            // 최대 범위를 넘었다가 왼쪽으로 가는 경로보다 더 빠른 경로가 항상 존재한다.
            if (nextPosition2 <= MAX_POSITION && visited[nextPosition2].not()) {
                visited[nextPosition2] = true
                queue.offer(Pair(nextPosition2, time + 1))
            }

            val nextPosition3 = position * 2
            if (nextPosition3 <= MAX_POSITION && visited[nextPosition3].not()) {
                visited[nextPosition3] = true
                queue.offer(Pair(nextPosition3, time + 1))
            }
        }
    }
}