개발해요

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

유형

누적 합, 완전 탐색

풀이

부분 행렬의 최대 값을 구하는 문제이다. 부분 행렬 or 배열에서 연속된 부분 합을 빠르게 구하는 방법으로는 누적 합이 있다. 일단 그것을 배제하고 단순하게 완전 탐색으로 모든 부분 행렬의 합을 구하려고 한다면, 아래와 같이 6중 for문을 사용하게 된다.

// 부분 행렬의 왼쪽 위 끝 점
for (startRow in 0 until rowSize) {
    for (startCol in 0 until colSize) {
        // 오른쪽 아래 끝 점
        for (endRow in startRow until rowSize) {
            for (endCol in startCol until colSize) {
                var partSum = 0
                // 부분 행렬 안에서 포인터 이동
                for (row in startRow..endRow) {
                    for (col in startCol..endCol) {
                        partSum += matrix[row][col]
                    }
                }
            }
        }
    }
}

시간 복잡도까지 안가도 이건 안되겠다는 게 느껴지지만ㅋㅋ, 대충 따져봐도 O(N^6)에 가깝기 때문에 이 방법으론 안된다.

위에서 얘기한대로 누적 합 방법을 사용하면 완전 탐색으로도 시간 안에 풀 수 있다. 누적 합이 위의 코드에서 맨 안쪽에 있는 실제 부분 합을 구하는 이중 for문을 수식 하나로 바꿔주기 때문이다. 즉, 부분 행렬의 시작 점과 끝 점만 알면 누적 합을 구하는 수식을 통해 O(1)로 합을 구할 수 있다.

ex) 부분 행렬 (2,3) ~ (5,7)의 합

= prefixSum[5][7] - prefixSum[2-1][7] - prefixSum[5][3-1] + prefixSum[2-1][3-1]

for (startRow in 0 until rowSize) {
    for (startCol in 0 until colSize) {
        for (endRow in startRow until rowSize) {
            for (endCol in startCol until colSize) {
                var currentPrefixSum = prefixSum[endRow][endCol]
                // 시작 점이 0행이면 뺄 구간이 없다.
                if (startRow > 0) currentPrefixSum -= prefixSum[startRow-1][endCol] 
                if (startCol > 0) currentPrefixSum -= prefixSum[endRow][startCol-1] // 열도 마찬가지
                if (startRow > 0 && startCol > 0)  currentPrefixSum += prefixSum[startRow-1][startCol-1]
                maxPartSum = currentPrefixSum.coerceAtLeast(maxPartSum)
            }
        }
    }
}

따라서 시간 복잡도는 시작점이 (0,0)일 때 끝 점이 (0,0)에서 (n-1, n-1)인 경우, 시작 점이 (0,1)일 때 끝 점이 (0,1)에서 (n-1, n-1)인 경우의 수와 같이 모든 부분 행렬의 경우의 수를 따져보면 알 수 있다.

시작 점이 (0,0)일 경우 n^2, (0,1)이면 n*(n-1), ... , (0, n-1)이면 n,

1행에서는 (1,0)이면 (n-1)*n, (1,1)이면 (n-1)*(n-1), ..., (1, n-1)이면 n-1이 된다.

이런 식으로 전부 구한다면 연산 횟수 = n*(1+...+n) + (n-1)*(1+...+n) + ... + (1+...+n) = (1+...+n)*(1+...+n)이며, n에 199를 넣어보면 대략 4억이다.

풀이 순서

1. (0,0)에서 각 점까지의 누적 합을 구한다.

2. 가능한 모든 시작 점과 끝 점을 확인하면서 모든 부분 행렬의 합을 구한다.

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (rowSize, colSize) = readLine().split(" ").map(String::toInt)
    val matrix = Array(rowSize) {
        val st = StringTokenizer(readLine())
        IntArray(colSize) { st.nextToken().toInt() }
    }
    val prefixSum: Array<IntArray> = calculatePrefixSum(matrix) // 0행0열에서부터의 누적합 기록
    var maxPartSum = matrix[0][0]
    
    // 부분행렬 [startRow][startCol] ~ [endRow][endCol]의 합
    for (startRow in 0 until rowSize) {
        for (startCol in 0 until colSize) {
            for (endRow in startRow until rowSize) {
                for (endCol in startCol until colSize) {
                    var currentPrefixSum = prefixSum[endRow][endCol]
                    if (startRow > 0) currentPrefixSum -= prefixSum[startRow-1][endCol]
                    if (startCol > 0) currentPrefixSum -= prefixSum[endRow][startCol-1]
                    if (startRow > 0 && startCol > 0)  currentPrefixSum += prefixSum[startRow-1][startCol-1]
                    maxPartSum = currentPrefixSum.coerceAtLeast(maxPartSum)
                }
            }
        }
    }

    print(maxPartSum)
}

// 누적합 배열 반환
fun calculatePrefixSum(matrix: Array<IntArray>): Array<IntArray> {
    val prefixSum = Array(matrix.size) { IntArray(matrix[0].size) }
    
    prefixSum[0][0] = matrix[0][0]
    // 0행 누적합
    for (i in 1 until prefixSum[0].size) {
        prefixSum[0][i] = prefixSum[0][i-1] + matrix[0][i]
    }
    // 0열 누적합
    for (i in 1 until prefixSum.size) {
        prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0]
    }

    // 1행1열에서 row행col열까지의 누적합
    for (row in 1 until prefixSum.size) {
        for (col in 1 until prefixSum[0].size) {
            prefixSum[row][col] =
                prefixSum[row][col-1] + prefixSum[row-1][col] + matrix[row][col] - prefixSum[row-1][col-1]
        }
    }
    
    return prefixSum
}

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

문제 유형

그래프 - 다익스트라, BFS

비슷한 문제: https://programmers.co.kr/learn/courses/30/lessons/72413

풀이

문제에 오타가 좀 있고 지문이 불친절했다.

• 선택 가능한 땅의 위치: 정수 1 ~ n
• 구하고자 하는 것: 가장 가까운 친구(A, B, C) 집까지의 거리 기준 가장 먼 곳의 위치
• 가장 먼 곳이란? - 임의의 위치 X에서 A,B,C까지의 거리 중 가장 가까운 거리, 그리고 그 가까운 거리들 중 가장 먼 거리에 있는 곳
• 각 위치 ~ A,B,C의 거리 중 가장 가까운 거리를 찾아야 하므로 모든 거리는 최단거리 기준으로 생각한다. -> 다익스트라 알고리즘 사용

풀이 과정

1. A ~ (1..n), B ~ (1..n), C ~ (1..n)의 최단거리를 각각 구한다 (다익스트라 3번). -> 모든 위치마다 각 점까지의 최단거리를 구하지 않아도 된다. 그러면 시간복잡도가 O(N^2)이 된다.

2. 모든 위치마다 A,B,C까지의 거리 중 가장 짧은 거리와 장소를 계산한다. 

3. 그 중 가장 먼 거리의 장소를 구한다.

for (i in 1..n) {
    var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
    tempMinDist = min(tempMinDist, minDist[2][i])       // 그것과 i ~ C까지의 거리 비교

    // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
    if (maxOfMinDist < tempMinDist) {
        maxOfMinDist = tempMinDist
        answerLand = i
    }
}

코드

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

data class Edge(val from: Int, val to: Int, val dist: Int)

lateinit var graph: Array<MutableList<Edge>> // 인접 리스트

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val (a,b,c) = readLine().split(" ").map(String::toInt)
    val m = readLine().toInt()
    graph = Array(n+1) { mutableListOf<Edge>() }
    val minDist = Array(3){
        IntArray(n+1) { -1 }
    } // a,b,c에서 모든 지점까지의 최단 거리

    repeat(m) {
        val st = StringTokenizer(readLine())
        val land1 = st.nextToken().toInt()
        val land2 = st.nextToken().toInt()
        val dist = st.nextToken().toInt()
        graph[land1].add(Edge(land1, land2, dist)); graph[land2].add(Edge(land2, land1, dist))
    }

    // a,b,c에서 모든 위치까지의 최단거리를 각각 구한다 (다익스트라)
    calculateMinDist(minDist[0], a)
    calculateMinDist(minDist[1], b)
    calculateMinDist(minDist[2], c)

    var maxOfMinDist = 0 // 최단 거리중 가장 먼 거리
    var answerLand = 0   // 그에 연결되는 땅 - 정답
    
    for (i in 1..n) {
        var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
        tempMinDist = min(tempMinDist, minDist[2][i])		// 그것과 i ~ C까지의 거리 비교

        // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
        if (maxOfMinDist < tempMinDist) {
            maxOfMinDist = tempMinDist
            answerLand = i
        }
    }

    println(answerLand)
}

// 다익스트라
fun calculateMinDist(minDist: IntArray, src: Int) {
    val q: Queue<Int> = LinkedList()
    q.offer(src)
    minDist[src] = 0

    while (q.isNotEmpty()) {
        val currentLand = q.poll()

        for (nextEdge in graph[currentLand]) {
            val nextDist = minDist[currentLand] + nextEdge.dist
            // 첫 방문 or 기존 거리보다 짧으면 갱신
            if (minDist[nextEdge.to] == -1 || nextDist < minDist[nextEdge.to]) {
                minDist[nextEdge.to] = nextDist
                q.offer(nextEdge.to)
            }
        }
    }
}

https://leetcode.com/problems/3sum-closest/

유형

투 포인터

해결 과정

- 구하고자 하는 것

정수 배열에서 세 수의 합 가운데 target에 가장 가까운 것

- 쉽게 떠올릴 수 있는 방법

완전 탐색: 삼중 반복문으로 세 수의 합을 모두 확인한다.

==> 문제: O(n^3)으로 시간 내에 해결함을 보장할 수 없다.

- 시간 복잡도 개선한 방법

1. 배열에서 하나의 숫자(num1)를 선택해서 고정한다. -> O(n)
2. 나머지 수 가운데 num1과 더했을 때 target에 가장 가까운 두 수(num2, num3)를 찾는다.
3. 1번 과정을 모든 숫자에 적용해본다.

2번에서 투 포인터 방법을 사용하면 O(n)으로 두 수를 찾을 수 있다. 따라서 위 과정을 따르기 전에 우선 배열을 정렬한다. 따라서 시간 복잡도 = nlogn(정렬) * n(1번) * n(2번) = O(n^2)

- 투 포인터 사용 과정

기준): target에 가까운 정도

정답) target에 가장 가까운 합 -> 꼭 필요한 변수

과정)

1. 포인터를 오름차순 정렬된 배열의 가장 왼쪽(start)과 오른쪽(end)에 하나씩 둔다.

2-1) if 절대값(target - answer) > 절대값(target - num1 + num2 + num3) -> 정답 갱신

2-2)

if (target > num1 + num2 + num3) -> start++

else if (target > num1 + num2 + num3) -> end--

else -> 정답: num1 + num2 + num3

3. start < end일 때까지 2번 과정 반복

코드 (Kotlin)

import kotlin.math.abs

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var answerDiffer = Int.MAX_VALUE // 절대값(target - target에 가장 가까운 합)
        var answerSum = 0 // target에 가장 가까운 합
        nums.sort() // 투 포인터로 해결하기 위해 정렬
        
        for (i in 0 until nums.size - 2) {
            var start = i + 1
            var end = nums.lastIndex
            
            while (start < end) {
                val tempSum = nums[i] + nums[start] + nums[end]
                val tempDiffer = abs(target - tempSum)
                
                // target과 차이가 더 작은 합을 발견하면 정답을 갱신
                if (tempDiffer < answerDiffer) {
                    answerDiffer = tempDiffer
                    answerSum = tempSum
                }
                
                if (tempSum > target) {
                    end--
                } else if (tempSum < target) {
                    start++
                } else {
                    return tempSum // 정답은 꼭 하나라고 했으므로 리턴
                }
            }
        }
        
        return answerSum
    }
}

피드백

투 포인터는 정렬된 배열있고 특정 기준이 있을 때, 기준에 가장 부합하는 최적의 두 수를 빠르게 찾을 때 사용할 수 있다. 이분 탐색과 조건이 아주 유사하다.

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

프로세스

1. orders의 각 문자열을 오름차순으로 정렬해서 저장한다.
2. orders의 원소마다 즉, 각 주문마다 course에서 주어진 코스 요리의 단품 메뉴 개수별 모든 조합을 구한다. 문자열을 (오름차순으로 정렬해놨기 때문에 앞에서부터 조합을 구성하면 자연스럽게 오름차순이 된다.)
3. 각 조합을 문자열로 변환해서 Map에 count한다.
4. 길이 별로 count 값이 가장 큰 조합을 모두 리스트에 추가한다.
5. 리스트를 오름차순 정렬해서 반환한다. 

풀이

카카오 2021 공채에 2번으로 나왔던 문제로 프로그래머스에서 난이도가 2로 되어 있지만, 코테 정답률은 25%로 많은 사람들이 어려워 했다. 삼성 A형 처럼 약간의 단계를 거치며 풀어야 하기 때문에, 조합 구하는 방법과 Map 조작에 익숙하지 않다면 풀다가 멘탈이 터질 수 있다.

풀이를 요약해보면 어렵진 않다. 각 주문마다 course 원소에 해당하는 길이마다 조합을 구해서 빈도 수를 count한다. 그리고 제일 많이 count된 조합을 모두 구한다.

근데 막상 풀려고 하면 부담이 된다. "아니 조합을 길이 별로 구해야 돼?" 조합에 자신이 없는 상태에서 만나면 이렇게 무식하게 푸는 게 맞는 건지 의구심이 들 수도 있다. 그런데 그렇게 푸는 거 맞다(ㅡ_ㅡ)

그리고 길이 별로 조합을 따로 저장한다. 단품 개수별로 가장 많이 나온 조합을 찾아야 하기 때문이다. 길이가 최대 10이므로 배열로 길이를 구분하고, 그 안에 Map을 저장할 수 있다.

마지막으로 길이별 Map을 value(빈도 수) 내림차순으로 정렬해서 첫 번째 원소의 빈도 수와 같은 key(조합)를 모두 리스트에 저장한다. 그리고 리스트를 정렬하면 정답을 구할... 수도 있고 틀릴 수도 있다. (1) 빈도 수가 2 이상인 조합만 구해야 하고, (2) 각 조합도 오름차순으로 정렬되어야 하기 때문이다.

따라서, 다 구하고 나서 각 조합(원소)을 정렬하거나, 처음에 order의 각 값을 오름차순으로 정렬을 해놓고 조합을 구할 때 왼쪽에서부터 순서대로 선택을 해서 자연스럽게 오름차순으로 만들 수도 있다. 

정리

(1) 각 주문을 오름차순으로 정렬한다.

private val mOrders = mutableListOf<CharArray>()
//...
for (order in orders) {
	mOrders.add(order.toCharArray().sortedArray())
}

(2) 개수 별로 조합의 빈도 수를 count할 배열과 Map을 준비한다.

// 조합을 저장할 배열 - combs[단품 개수][Map<조합, 빈도 수>]
private val combs: Array<MutableMap<String, Int>> = Array(11){ HashMap() }

(3) 주문마다 단품 메뉴 개수(길이) 별로 조합을 구한다.

for (order in mOrders) {
    for (combSize in course) {
        findComb(0, CharArray(combSize), order, 0) // 주문마다 필요한 길이 별 조합을 구한다
    }
}

//...

// combCount: 지금까지 선택한 메뉴의 개수, currentComb: 선택한 메뉴 저장하는 배열
// order: 주문(선택할 메뉴 후보들), startIdx: 선택 가능한 메뉴 범위의 시작 - startIdx ~ order.lastIndex
private fun findComb(combCount: Int, currentComb: CharArray, order: CharArray, startIdx: Int) {
    if (combCount >= currentComb.size) { // 다 뽑았으면,
        // 조합을 문자열로 변환
        val combination = StringBuilder().append(currentComb).toString() 
        
        if (combs[currentComb.size].contains(combination).not()) {
            combs[currentComb.size][combination] = 0
        }
        
        combs[currentComb.size][combination] = combs[currentComb.size][combination]!! + 1
        return
    }

    // 남아있는 메뉴 개수 < 앞으로 더 뽑아야할 메뉴 개수
    if (order.size - startIdx < currentComb.size - combCount) return

    // order[startIdx ~ order.lastIndex]에서 하나를 선택한다
    for (i in startIdx until order.size) {
        currentComb[combCount] = order[i]
        findComb(combCount + 1, currentComb, order, i + 1)
    }
}

(4) 길이 별로 가장 많이 나온 조합을 저장한다.

for (size in course) {
    if (combs[size].isEmpty()) continue // 해당 길이의 조합이 없을 수도 있다

    // map을 리스트로 바꾸면 Pair<key, value> 형태가 된다
    // value 기준 내림차순으로 정렬
    val combList = combs[size].toList().sortedByDescending { it.second }
    val maxCount = combList[0].second
    if (maxCount <= 1) continue // 2개 이상 나온 조합이어야 함

    // 가장 긴 조합들을 저장한다
    for (order in combList) {
        if (maxCount > order.second) break
        answer.add(order.first)
    }
}

전체 코드

import java.util.*

class Solution {
    // 조합을 저장할 배열 - combs[단품 개수][Map<조합, 빈도 수>]
    private val combs: Array<MutableMap<String, Int>> = Array(11){ HashMap() }
    private val mOrders = mutableListOf<CharArray>() // 주문 마다 오름차순의 CharArray로 바꿔서 저장한다

    fun solution(orders: Array<String>, course: IntArray): Array<String> {
        val answer = mutableListOf<String>()

        for (order in orders) {
            mOrders.add(order.toCharArray().sortedArray())
        }

        for (order in mOrders) {
            for (combSize in course) {
                findComb(0, CharArray(combSize), order, 0) // 주문마다 필요한 길이 별 조합을 구한다
            }
        }

        for (size in course) {
            if (combs[size].isEmpty()) continue // 해당 길이의 조합이 없을 수도 있다

            // map을 리스트로 바꾸면 Pair<key, value> 형태가 된다
            // value 기준 내림차순으로 정렬
            val combList = combs[size].toList().sortedByDescending { it.second }
            val maxCount = combList[0].second
            if (maxCount <= 1) continue // 2개 이상 나온 조합이어야 함
            
            // 가장 긴 조합들을 저장한다
            for (order in combList) {
                if (maxCount > order.second) break
                answer.add(order.first)
            }
        }

        return answer.sorted().toTypedArray()
    }

    // combCount: 지금까지 선택한 메뉴의 개수, currentComb: 선택한 메뉴 저장하는 배열
    // order: 주문(선택할 메뉴 후보들), startIdx: 선택 가능한 메뉴 범위 - startIdx ~ order.lastIndex
    private fun findComb(combCount: Int, currentComb: CharArray, order: CharArray, startIdx: Int) {
        if (combCount >= currentComb.size) { // 다 뽑았으면,
            // 조합을 문자열로 변환
            val combination = StringBuilder().append(currentComb).toString()
            
            if (combs[currentComb.size].contains(combination).not()) {
                combs[currentComb.size][combination] = 0
            }
            
            combs[currentComb.size][combination] = combs[currentComb.size][combination]!! + 1
            return
        }

        // 남아있는 메뉴 개수 < 앞으로 더 뽑아야할 메뉴 개수
        if (order.size - startIdx < currentComb.size - combCount) return

        for (i in startIdx until order.size) {
            currentComb[combCount] = order[i]
            findComb(combCount + 1, currentComb, order, i + 1)
        }
    }
}

회고

알고리즘이나 아이디어가 어려운 문제는 아니었는데, 조합이나 Map을 다루는 것이 능숙하지 않아서 어렵게 느꼈던 것 같다. 조합 구하는 거 자신 있다고 생각했었는데 착각이었다..ㅋㅋ. 복잡한 문자열 관련 문제들 중 대부분이 조합과 Map을 사용하는 것 같아서 이번 기회에 정리하고 넘어간다.