Jenikeju

내가 푼 풀이

접근방법: 이분탐색

이전에 두용액문제를 풀고왔더니 너무 쉽게 파악해버렸다

두 용액을 섞을땐 용액의수가 최대 10만이였는데 이 문제에선 최대 5000 이다.

단순히 두 용액을 고정하고 한 용액을 순회하며 섞어봐도 정답은 나오지만 5000^3 = 1250억번 연산이므로 시간초과가 무조건 뜰것이다.

그래서 두개의 용액을 고정하고 한 용액을 구할때 이분탐색을 이용했다.

시간복잡도는 O(N^2logN)으로 이문제에선 약 9700만번연산(1억보다 적다)으로 시간안에 풀어졌다.

이분탐색

용액을 섞었을때, 음수면 start인덱스가 mid+1 양수면 end인덱스가 mid-1 해주어 0과 가장 가깝게 만든다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var minSum = Int.max
var answer = [Int]()
// 이분탐색 사용을위해 정렬
arr.sort(by: <)


// 이분탐색
for i in 0..<N {
    for j in i+1..<N {
        // 두용액을 고정한다.
        let first = arr[i]
        let second = arr[j]
        let sum = first + second
        var s = j+1
        var e = N-1
        // 나머지 한용액을 이분탐색을 이용해 구해준다.
        while s <= e {
            let m = (s+e)/2
            let total = sum + arr[m]
            // 0이되면 바로 값 갱신 후 탈출
            if total == 0 {
                answer = [arr[i],arr[j],arr[m]]
                minSum = total
                break
            }
            // 합쳐진 용액이 음수면 나머지 용액을 더 큰수로, 양수면 더 작은수로
            if total < 0 {
                s = m+1
            } else {
                e = m-1
            }
            // 최솟값이 나오면 항상 값을 갱신해준다.
            if minSum > abs(total) {
                minSum = abs(total)
                answer = [arr[i],arr[j],arr[m]]
            }
        }
        
    }
}

print("\(answer[0]) \(answer[1]) \(answer[2])")

분할정복

분할 정복은 문제를 부분문제로 나누어 문제를 해결할 수 있는단위까지 나눈 후, 해결하고 다시 조합하는 방법이다.

분할정복은 세단계로 구성되어있다.

분할: 문제를 분할할 수 있을 만큼 같은 유형의 문제로 분할한다.

정복: 분할된 작은 문제를 해결한다.

조합: 해결된 작은 부분문제들을 조합하여 정답을 출력한다.

※ 분할정복과 동적 계획법 차이:

분할정복은 큰 문제를 여러개의 작은 문제로 나누어 해결하고, 이를 모두 조합한다.

동적계획법은 작은 문제부터 해결하여 기록하고, 기록된 정보를 통해 큰문제를 해결해나간다.

분할정복은 대표적으로 합병정렬과 퀵 정렬이 있다.

합병정렬

분할정복의 대표적인 정렬 알고리즘이다.

합병정렬의 단계

1. 주어진 배열의 크기가 0또는 1이라면 이미 정렬이 되있다고 간주하고, 그렇지 않다면 2개의 부분배열로 나눈다.

2. 부분배열의 크기가 정렬할 수 있을만큼 작지않다면 1번을 재호출한다.

3. 나눠진 부분배열을 합친다. 이때 순서에 맞춰서 정렬한다.

4. 부분배열을 조합하여 결과를 출력한다.

합병정렬의 특징:

- 합병정렬의 조합단계에서 따로 저장해둘 배열로부터 값을 가져오므로 입력과 같은 공간의 임시배열이 필요하다.

- 재귀호출로 인해 오버헤드가 발생할 수 있다.

- 연결리스트를 정렬할때는 다른 정렬방법보다 더 효율적이다.

Swift 코드로 구현

// 합병 정렬
func mergeSort(arr: inout [Int], p: Int, q: Int) -> [Int] {
	// 따로 저장해둘 공간(입력된배열의 크기만큼)
    var result = Array(repeating: 0, count: arr.count)
    // 배열의 크기가 1 또는 0이 될때까지 최대로 나누어준다.
    if p < q {
        // 배열의 중간인덱스
        var k = (p + q) / 2
        // 배열을 둘로 나누었을때, 왼쪽배열과 오른쪽배열
        var leftArr = mergeSort(arr: &arr, p: p, q: k)
        var rightArr = mergeSort(arr: &arr, p: k+1, q: q)
        
        // 배열이 최대로 나누어졌을때 아래 행동이 시작된다.
        // 분할된 배열들을 정렬하며 합친다.
        var i = p
        var j = k+1
        var d = p
        
        // 왼쪽배열과 오른쪽배열중 한 배열이 모두 정렬이 완료될때까지
        while i <= k && j <= q {
            // 왼쪽배열 원소가 더크면 오른쪽배열 원소를 넣고, 오른쪽배열 원소가 더 크면 왼쪽배열 원소를 넣는다.
            if leftArr[i] < rightArr[j] {
                result[d] = leftArr[i]
                i += 1
            } else {
                result[d] = rightArr[j]
                j += 1
            }
            d += 1
        }
        // 한쪽의 배열이 모두 정렬되었을때, 다른 한쪽은 원소가 남아있기때문에 그대로 붙여준다.
        // 남아있는 원소는 이미 이전에 정렬되어있는 원소기때문에 그대로 붙여도 좋다.
        if i > k {
            for index in j...q {
                result[d] = rightArr[index]
                d += 1
            }
        } else if j > q {
            for index in i...k {
                result[d] = leftArr[index]
                d += 1
            }
        }
        
        // 정렬된 원소를 배열에 넣고 리턴
        for i in p...q {
            arr[i] = result[i]
        }
    }
    return arr
}

입력 & 결과:

var A = [37, 10, 22, 30, 35, 13, 25, 24]
print(mergeSort(arr: &A, p: 0, q: A.count-1))
// [10, 13, 22, 24, 25, 30, 35, 37]

위 코드 재귀호출의 흐름은 다음과 같다.

1. 왼쪽배열을 분할

2. [37, 10] 정렬 후 결합

3. [22,30] 정렬 후 결합

4. 두 배열을 정렬 후 결합

5. 왼쪽배열: [10,22,30,37]

6. 오른쪽배열을 분할

7. [35,13] 정렬 후 결합

8. [25,24] 정렬 후 결합

9 두 배열을 정렬 후 결합

10. 오른쪽 배열: [13, 24, 25, 35] 

11. 왼쪽배열과 오른쪽배열을 정렬 후 결합하여 리턴

퀵정렬

퀵정렬은 임의의 수 하나를 골라, 그 수보다 작으면 왼쪽에, 크다면 오른쪽에 정렬하는 방법이다.

퀵정렬 과정

정복: 임의의수 n을 기준으로 n보다 작은수는 왼쪽배열, n보다 큰수는 오른쪽배열에 배치

분할: 배치된 배열에서 왼쪽배열과 오른쪽배열 재귀호출

퀵정렬은 정복을 먼저하고 분할하여 재귀호출을 한다.

세부과정

1. 기준이되는 원소를 선택

2. 기준원소의 인덱스를 저장하고, 나머지 원소를 검사하며 기준원소보다 작다면 인덱스+1 후 원소와 저장된인덱스와 자리바꿈

3. 모든 원소 검사 후 기준원소와 인덱스와 자리바꿈

(여기까지 완료된다면 배열은 기준원소를 기준으로 왼쪽에는 작은값, 오른쪽엔 큰값 배치됨) (정복)

4. 기준원소를 제외한 왼쪽배열과 오른쪽배열을 재귀호출한다.(분할)

5. 1-4를 반복하여 결과 도출

코드로 구현하면 다음과 같다.

// 퀵 정렬
func quickSort(arr: inout [Int], left: Int, right: Int) -> [Int] {
    // 배열의 크기가 2 이상이면 정복, 아니면 그냥 출력
    if left < right {
        // 기준점 선택(가장왼쪽)
        var pivot = arr[left]
        // 기준점이 위치할 곳을 저장
        var j = left
        // 기준점을 제외한 배열의 원소들을 검사
        for i in left+1...right {
            // 원소가 기준점보다 작다면 j위치에 있는 원소와 바꿈
            // 원소가 기준점보다 크다면 패스
            // 이렇게 반복하면 j위치보다 이전에 위치한 원소들은 기준점보다 작은 원소들이다.
            if arr[i] < pivot {
                j += 1
                arr.swapAt(i, j)
            }
        }
        // 기준점과 j위치와 원소 바꾸기
        // 기준점은 중간에 위치하게되고, 기준점 왼쪽은 기준점보다 작은원소, 오른쪽은 기준점보다 큰원소가 배치됨
        arr.swapAt(j, left)
        // 분할
        // 왼쪽배열로 재귀호출
        // 오른쪽배열로 재귀호출
        quickSort(arr: &arr, left: left, right: j-1)
        quickSort(arr: &arr, left: j+1, right: right)
    }
    
    return arr
}

입력 및 결과:

var A = [25, 10, 22, 30, 35, 13, 37, 24]
print(quickSort(arr: &A, left: 0, right: A.count-1))
// [10, 13, 22, 24, 25, 30, 35, 37]

위 코드 재귀호출의 흐름은 다음과 같다.

1. 기준점:25 를 기준으로 [작은값, 25, 큰값] 배치

2. [작은값], [큰값] 재귀호출

3. 1-2 반복(기준점을 제외한 원소가 없을때까지)

퀵정렬의 최악의경우는 이미 정렬된 데이터를 정렬할 경우이다.

나타난 오류 및 막힌점

이번에 프로젝트 앱을 만드면서 앱 내 다크모드 기능을 구현하던 중 투명도를 조절하여 색을 넣어줬는데 원하는 색이 안나온다.

테이블 셀의 구조를 확인해보니, 셀이 두겹의 뷰로 이루어져 있었다.

https://developer.apple.com/documentation/uikit/uitableviewcell/1623229-contentview

맨 앞에 있는 뷰는 ContentView이다.

공식문서에 따르면 ContentView는 셀 객체의 컨텐츠 뷰이고, 테이블뷰셀의 ContentView는 셀이 표시하는 컨텐츠의 상위 뷰라고 한다.

이는 셀의 가장 상위에 존재하며, 셀에 표시될 컨텐츠를 담고 있다고 한다.

뒤에 있는 뷰는 이 셀의 뷰인것같다..

왜 생성됬을까 하면 아마 셀은 UIView를 상속받고 있기 때문에 셀을 쓴다면 셀 자체의 UIView가 생성되는 듯 하다.

그래서 셀 자체는 UIView의 변수 backgrounColor에 접근할 수 있고, 설정할 수 있다.

종합하자면 셀은 셀자체의 UIView와, 셀이 갖고있는 ContentView가 존재한다.

오류 해결

두개의 뷰중 하나만 색감을 입히기로 하고, 나머지 한개의 배경색을 투명색으로 바꾸었다.

셀의 accessoryView가 없어서 contentView가 셀의 모든 부분을 덮지않았다.

그래서 contentView의 배경색을 투명색으로하고, cell의 배경색을 사용했다.

잘된다!

내가 푼 풀이

접근방법: 플로이드 워셜 알고리즘

- 플로이드 워셜 알고리즘을 이용해 모든노드쌍의 최단거리를 구한다.

- 이때 최댓값과, 출력할때 갈수 없는경우를 0출력하는것을 주의한다.

import Foundation

// 입력
let n = Int(readLine()!)!
let m = Int(readLine()!)!
var graph = Array(repeating: Array(repeating: 1000000000, count: n+1), count: n+1)

// 인접행렬
for _ in 0..<m {
    let bus = readLine()!.split(separator: " ").map{Int(String($0))!}
    if graph[bus[0]][bus[1]] > bus[2] {
        graph[bus[0]][bus[1]] = bus[2]
    }
}
// i도시는 i도시로 갈 수 없다.
for i in 1...n {
    graph[i][i] = 0
}

// 플로이드-워셜 알고리즘
for m in 1...n {
    for i in 1...n {
        for j in 1...n {
            let im = graph[i][m]
            let mj = graph[m][j]
            graph[i][j] = min(graph[i][j], graph[i][m] + graph[m][j])
        }
    }
}

// 최단거리를 구하기위해 비교값으로 큰 값을 주었는데, 이동할 수 없음을 0으로 변환
for i in 0..<graph.count {
    for j in 0..<graph[0].count {
        if graph[i][j] == 1000000000 { graph[i][j] = 0 }
    }
}

// 출력
for i in 1..<graph.count {
    var answer = ""
    for j in 1..<graph[i].count {
        if j == graph[i].count - 1 {
            answer += "\(graph[i][j])"
        } else {
            answer += "\(graph[i][j]) "
        }
    }
    print(answer)
}

플로이드-워셜 알고리즘

그래프에서 최단거리를 구할때, 여러가지 알고리즘이 있고, 우리는 선택할 수 있다.

플로이드-워셜 알고리즘은 주어진 모든 노드쌍의 최단거리를 구하는 알고리즘이다.

이 알고리즘은 다익스트라와는 다르게 음의 가중치가 있는 그래프에서도 사용이 가능하며, 시간복잡도는 O(N^3)이다.

플로이드-워셜 알고리즘 과정

이 알고리즘은 노드 a에서 b까지 가는 최단거리를 구하기 위해, 두 노드 사이의 중간노드인 m을 이용하여 구한다.

m을통해 a에서 m까지의 최단거리와 m에서 b까지의 최단거리를 구하고 더하면 a에서 b까지의 최단거리가 된다.

그래프의 모든 노드를 중간노드로 설정해주며, 최단거리를 구해내간다.

아래 그래프로 플로이드 워셜 알고리즘을 이용해 최단거리를 구해보자.

이 그래프를 인접행렬로 나타내면 다음과 같다.

arr[i][j] : i에서 j로 가는 최단거리, INF: 연결되지않음

주어진 모든 노드들을 중간노드로 설정하며 최단거리를 구해줄 것이다.

노드 i와 j사이의 중간노드 m을 설정한다면

arr[i][j] = arr[i][m] + arr[m][j]가 될것이고,

먼저 저장된 arr[i][j]와 arr[i][m] + arr[m][j]의 값을 비교하여 더 작은값을 넣는다.

1. 중간노드 : A

중간노드 A로 설정시 갱신되는 최단거리가 없다.

2. 중간노드: B

중간노드를 B로 설정하면 위와 같이 최단거리값이 갱신된다.

이는 노드 i에서 j로갈때의 중간노드 m : arr[i][j] > arr[i][m] + arr[m][j]이 성립한다는것이다.

3. 중간노드: C

중간노드를 C로 설정하면 위와 같이 최단거리값이 갱신된다.

이렇게 그래프의 모든 노드를 중간노드로 하나씩 설정해주며 최단거리를 갱신하면 모든 쌍의 최단거리 배열이 완성된다.

이를 코드로 구현해보자.

import Foundation

// 그래프의 인접행렬
var graph = [
    [0, 5, 1, 1000000, 1000000],
    [5, 0, 2, 1, 4],
    [1, 2, 0, 4, 1000000],
    [1000000, 1, 4, 0, 2],
    [1000000, 4, 1000000, 2, 0]
]

// 플로이드-워셜 알고리즘
// 모든 노드를 중간노드로 설정해보고, 노드 i에서 j 사이 중간노드 m이라면
// arr[i][j] > arr[i][m] + arr[m][j]이라면 값 갱신
for m in 0..<5 {
    for i in 0..<5 {
        for j in 0..<5 {
            graph[i][j] = min(graph[i][j], graph[i][m] + graph[m][j])
        }
    }
}

결과:

// 결과
0 3 1 4 6
3 0 2 1 3
1 2 0 3 5
4 1 3 0 2
6 3 5 2 0

다익스트라 알고리즘을 이용하여 선형탐색을 한다면, 시간초과가 난다.

따라서 다익스트라 알고리즘을 이용하되, 최단거리가 가장 짧은(여기선 루피가 적은)것 먼저 우선순위로 고른다.

현재 위치에서 상하좌우로 이동가능하니, 현재위치의 인접한노드는 상하좌우로 한다.

코드로 구현하면 다음과 같다.

import Foundation

var index = 1
while true {
    // 입력받기
    let N = Int(readLine()!)!
    if N == 0 { break }
    var graph = [[Int]]()
    var md = Array(repeating: Array(repeating: 1000000, count: N), count: N)
    for i in 0..<N {
        graph.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    }
    md[0][0] = graph[0][0]
    var queue = [(x: 0, y: 0, cost: graph[0][0])]
    var dx = [0,1,0,-1]
    var dy = [1,0,-1,0]
    
    // 다익스트라
    while !queue.isEmpty {
        let node = queue.removeLast()
        // 맨 오른쪽아래에 도달하면 멈춤
        // 최단거리가 가장 적은것 우선순위로 탐색하기때문에, 멈춰도된다. 선형탐색이라면 정답이 아닐수도 있다.
        if node.x == N-1 && node.y == N-1 { break }
        // 인접한 위치들 선택
        for i in 0..<4 {
            let mx = node.x + dx[i]
            let my = node.y + dy[i]
            if mx >= N || mx < 0 || my >= N || my < 0 { continue }
            if md[my][mx] > md[node.y][node.x] + graph[my][mx]{
                md[my][mx] = md[node.y][node.x] + graph[my][mx]
                queue.append((x: mx, y: my, cost: md[my][mx]))
            }
        }
        // 큐의 우선순위를 루피가 가장적은것 우선(배열의 마지막을 뽑기때문에 내림차순으로 한다.)
        queue.sort{ $0.cost > $1.cost }
    }
    print("Problem \(index): \(md[N-1][N-1])")
    index += 1
}