Jenikeju

예로 수열 [10, 20, 10, 30, 15, 50]이 주어졌을 때, 이분탐색을 이용하여 구한다면

[10, 15, 30, 50]배열이 구해지고 이는 최장증가 부분수열이 아니다.

이유는 15는 50이전의 원소로 30보다 나중에 나오는 원소이므로 옳지 않다.

부분수열은 구할 수 없지만 길이는 알고있다.

이 점을 이용하여 이분탐색을 통해 부분수열을 구할 때, 해당 원소의 인덱스를 저장한다.

괄호안 숫자는 해당원소가 주어진 수열의위치를 의미한다.

첫번째 원소 10

첫번째 원소는 비교대상이 없으므로 첫번째에 넣는다.

result = [10(1)]

idx = [1]

두번째 원소 20

두번쨰 원소는 이분탐색을 이용하여 10뒤에 오는 숫자임을 알 수 있다.

result = [10(1), 20(2)]

idx = [1, 2]

세번째 원소 10

세번째 원소는 이분탐색 결과 첫번째 오는 숫자와 같음을 알 수 있다.

result = [10(3), 20(2)]

idx = [1, 2, 1]

네번째 원소 30

네번째 원소는 20뒤에오는 숫자임을 알 수 있다.

result = [10(3), 20(2), 30(4)]

idx = [1, 2, 1, 3]

다섯번째 원소 15

다섯번째 원소는 이분탐색 결과 10과 20사이에 오는 숫자임을 알 수 있다.

이분탐색 결과 부분수열은 아래와 같다.

result = [10(3), 15(5), 30(4)]

idx = [1, 2, 1, 3, 2]

-> 이분탐색으로 만들어진 부분수열은 이미 정답과는 다른 부분수열이 만들어졌다. 해당원소의 위치를 배열안에 저장한다.

여섯번째 원소 50

여섯번째 원소는 이분탐색결과 마지막에 오는 숫자임을 알 수 있다.

result = [10(3), 15(5), 30(4), 50(6)]

idx = [1, 2, 1, 3, 2, 4]

-> 결과

result = [10(3), 15(5), 30(4), 50(6)]

idx = [1, 2, 1, 3, 2, 4]

이전의 이분탐색을 이용하면 result 배열을 얻고 길이는 정답이지만 부분 수열은 옳지않은 수열이 된다.

이분탐색을 통해 부분수열의 값이 변경될때 해당 원소가 위치하는 인덱스값을 저장함으로써 길이를 차감하며 부분수열을 구할 수 있게된다.

길이가 4이므로 역순으로 4 3 2 1의 원소를 뽑으면 [50, 30, 20 ,10]이고 이배열의 역순은 정답이 된다.

이분탐색을 이용하는 방법은 알았지만, 부분수열을 뽑아내는 과정은 쉽게 떠올리지 못했다.

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

import Foundation

// 입력받기
let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map{Int(String($0))!}
A.insert(0, at: 0)
let INF = 1000000001
// 이분탐색 결과배열과 인덱스 배열
var result = Array(repeating: INF, count: N+1)
var idxArr = [Int]()
result[1] = A[1]

// 이분탐색
func binarySearch(num: Int) {
    var left = 1
    var right = result.count-1
    
    while left <= right {
        let mid = (right + left) / 2
        
        if result[mid] < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    // 해당위치에 넣고, 인덱스배열에 저장
    result[left] = num
    idxArr.append(left)
}

for i in 1...N {
    binarySearch(num: A[i])
}

var answer = [Int]()
var count = 0

// 부분수열의 길이 구하기
for i in 1...N {
    if result[i] != INF {
        count += 1
    } else {
        break
    }
}
// 부분수열 구하기
for i in (0..<idxArr.count).reversed() {
    if idxArr[i] == count {
        count -= 1
        answer.append(A[i+1])
    }
}
// 출력
print(answer.count)
print(answer.map{String($0)}.reversed().joined(separator: " "))

내가 푼 풀이

접근방법 1: 브루트포스(조합) (시간초과)

N = 30이니까 밑져야본전식으로 가능한 모든 물건 합산의 경우의수를 구해봤지만 시간초과가 났다.

접근방법 2: Meet in the Middle / 이분탐색 / 조합

이 문제에서 새롭게 알게된 알고리즘이 있는데 바로 Meet in the Middle이다.

이 알고리즘은 브루트포스를 이용하기에 경우의수가 매우 많은경우 분할하여 연산횟수를 줄이는 기법이다.

접근방법 1번대로 모든 경우의수를 구한다면 $2^{30}$ 만큼 연산이 필요하고 이는 1,073,741,824번으로 시간초과가 발생한다.

이를 절반으로 나누어 경우의수를 구하면

$2^{15}  = 32,786$ 으로 연산횟수를 대폭 감소시킬 수 있다.

두개의 배열로 분할하여 경우의수를 갖는 부분집합을 구한다.

이때, 무게 C보다 큰 수는 불가능한 경우므로 부분집합에 넣지 않는다.

1. 주어진 무게의 배열을 절반으로 나눈다.

2. 절반으로 나눈 배열의 부분집합을 구한다.(배열의 원소를 더해서 나올 수 있는 모든 무게의 경우의수)

3. 두개의 부분집합 배열이 생성된다.

위 과정을 통해 오른쪽부분집합과 왼쪽부분집합이 구해졌다.

양쪽의 원소를 한개씩 가져와 더한 값이 C보다 작거나 같다면, 이는 가능한 경우의수가 된다.

따라서 (C - 오른쪽부분집합의 원소)보다 작거나 같은값은 모두 가능한 경우의 수가 된다.

갯수를 구하기 위해 이분탐색을 활용한다.

부분집합은 중복된 값을 가질 수 있다. 이는 가능한 모든 무게의 경우의수이기 때문이다.

이분탐색을 이용하여 중복된값을 갖는 배열의 가장 뒤에 위치한 인덱스를 구하면 해당 원소보다 작거나 같은 원소의 갯수를 구할 수 있다.

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

import Foundation

// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], C = input[1]
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var left = [Int]()
var right = [Int]()
var leftSums = [Int]()
var rightSums = [Int]()
var answer = 0
let mid = arr.count / 2

// 주어진 물건의 배열을 절반으로 나눈다.
for i in 0..<mid {
    left.append(arr[i])
}
for i in mid..<arr.count {
    right.append(arr[i])
}

// 조합
// 조합을 이용해 배열내 모든원소의 합 부분집합을 구한다.
func combi(targetArr: [Int], targetNum: Int, sum: Int, cnt: Int, index: Int, right: Bool) {
    if targetNum == cnt {
        if right {
            rightSums.append(sum)
        } else {
            leftSums.append(sum)
        }
        return
    }
    for i in index..<targetArr.count {
        let total = sum + targetArr[i]
        // 무게 C보다 큰수는 버린다. (불가능한 경우의수 이므로)
        if total <= C {
            combi(targetArr: targetArr, targetNum: targetNum, sum: total, cnt: cnt+1, index: i+1, right: right)
        }
    }
}

// 반으로 나눈 배열의 각 부분집합을 조합을 이용해 구한다.
// 오른쪽 배열
for i in 0...right.count {
    combi(targetArr: right, targetNum: i, sum: 0, cnt: 0, index: 0, right: true)
}
// 왼쪽 배열
for i in 0...left.count {
    combi(targetArr: left, targetNum: i, sum: 0, cnt: 0, index: 0, right: false)
}

// 이분탐색을 위해 정렬
leftSums.sort{$0 < $1}
rightSums.sort{$0 < $1}

// 이분탐색
// 부분집합의 합이 무게 C보다 작아야한다.
// 이는 오른쪽 부분집합 원소 하나를 꺼낸 값이 (C - 왼쪽부분집합의 값) 보다 작거나 같다면 가능한 경우의 수다.
// 이분탐색을 이용해 가능한 경우의수중 가장 큰수의 인덱스를 구한다.
// 여기서 인덱스는 곧 해당 원소보다 작거나 같은 원소의 갯수를 의미하므로 해당 인덱스를 더해준다.
// 중복된 값이 존재하는 이분탐색은 가장 뒤쪽의 인덱스를 구하는방법을 사용하자.
for rNum in rightSums {
    let sub = C - rNum
    var lidx = 0
    var ridx = leftSums.count - 1
    while lidx <= ridx {
        let mid = (lidx + ridx) / 2
        if leftSums[mid] <= sub {
            lidx = mid + 1
        }else {
            ridx = mid - 1
        }
    }
    answer += ridx+1
}

print(answer)

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

import Foundation

// 입력받기
let N = Int(readLine()!)!
var num = 4000000
var arr = Array(repeating: true, count: num+1)
var primeNums = [Int]()
let sqrtNum = Int(sqrt(Double(num)))
arr[1] = false
// 에라토스테네스의 체를 활용하여 소수 구하기
for i in 2...sqrtNum {
    if arr[i] == true {
        var j = 2
        while i * j <= num {
            arr[i * j] = false
            j += 1
        }
    }
}
// 구했던 소수를 배열에 저장
for i in 2...num {
    if arr[i] {
        primeNums.append(i)
    }
}

var lidx = 0
var ridx = 0
var cnt = 0
var sum = primeNums[lidx]

// 투포인터 알고리즘
// 주어진 소수배열에서 왼쪽인덱스부터 오른쪽 인덱스까지의 합을 N과 비교한다.
// N이 된다면 cnt + 1 , N보다 작다면 오른쪽인덱스를 증가, N보다 크다면 왼쪽인덱스를 증가
// N이 작아서 오른쪽 인덱스를 늘려서 배열의 마지막인덱스를 초과한다면, 범위를 벗어난경우이고 왼쪽 인덱스를 올려도 합계 자체는 오르지 않기때문에 탈출
while lidx < primeNums.count && lidx <= ridx {
    if primeNums[lidx] > N { break }
    if sum == N {
        cnt += 1
        sum -= primeNums[lidx]
        lidx += 1
    } else if sum > N {
        sum -= primeNums[lidx]
        lidx += 1
    } else if sum < N {
        ridx += 1
        if ridx > primeNums.count - 1 {
            break
        }
        sum += primeNums[ridx]
    }
}

print(cnt)

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

내가 푼 풀이

접근방법: 다익스트라

다익스트라로 시작점으로 부터 최단거리를 구한다.

시작점 s에서 목적지 후보들까지의 최단거리를 구하고, 이 최단거리가 g-h 경로를 포함한 최단거리라면 가능한 목적지가 된다.

이 문제는 이해하기도 어려웠는데..

위 사진은 예제코드 두번째의 그래프이다.

목적지 후보 5,6 중 6번만 가능한데 이유는 다음과 같다.

g: 3, h: 1 , 출발지점은 2번이다.

2번-> 5번의 최단거리는 2 - 5:  5 이지만 g-h경로를 지나가는 최단경로가 아니므로 불가능한 목적지가 된다.

2번 ->6번의 최단거리는 2 - 1 - 3 - 6: 6으로 g-h경로를 지나가는 최단경로가 된다. 따라서 6번은 가능한 목적지가 된다.

알고리즘 접근은 다음과 같이 했다.

다익스트라를 이용하여 최단거리를 총 3번 구한다.

1. 시작점부터 모든 지점과의 최단거리

2. g지점부터 모든 지점과의 최단거리

3. h지점부터 모든 지점과의 최단거리

g -h경로를 통하는 최단거리를 구하려면, g또는 h까지 최단거리를 구해야한다.

주의) g또는 h까지 최단거리가 둘다 같을 수 있기 때문에 2가지 경우의 수를 구해야 한다.

(시작점: s, 도착점: m)

1. s -> g -> h -> m

2. s -> h -> g -> m

위 두가지 경우중 하나가 시작점부터 목적지까지의 최단거리와 같다면, g-h경로를 지나간 최단거리가 되므로 가능한 목적지가 된다.

(minS: 시작점에서의 최단거리, minG: g지점에서의 최단거리, minH: h지점에서의 최단거리)

minS[m] = minS[g] + (g-h거리) + minH[m]

minS[m] = minS[h] + (h-g거리) + minG[m]

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

import Foundation

// 테스트케이스 수
let T = Int(readLine()!)!

for i in 0..<T {
    // 입력받기
    let input1 = readLine()!.split(separator: " ").map{Int(String($0))!}
    let n = input1[0], m = input1[1], t = input1[2]
    let input2 = readLine()!.split(separator: " ").map{Int(String($0))!}
    let s = input2[0], g = input2[1], h = input2[2]
    var graph = [Int: [(loc: Int, cost: Int)]]()
    var destination = [Int]()
    var answer = [Int]()
    var middleCost = 0
    
    // graph 저장
    for _ in 0..<m {
        let load = readLine()!.split(separator: " ").map{Int(String($0))!}
        // g-h거리 저장
        if (load[0] == g || load[1] == g) && (load[0] == h || load[1] == h) {
            middleCost = load[2]
        }
        if graph[load[0]] == nil {
            graph[load[0]] = [(loc: load[1], cost: load[2])]
        } else {
            graph[load[0]]?.append((loc: load[1], cost: load[2]))
        }
        if graph[load[1]] == nil {
            graph[load[1]] = [(loc: load[0], cost: load[2])]
        } else {
            graph[load[1]]?.append((loc: load[0], cost: load[2]))
        }
    }
    // 목적지 후보 저장
    for _ in 0..<t {
        destination.append(Int(readLine()!)!)
    }
    
    // minS: s지점에서 모든 점까지 최단거리
    // minG: g지점에서 모든 점까지 최단거리
    // minH: h지점에서 모든 점까지 최단거리
    var minS = dijkstra(s: s, n: n, graph: graph)
    var minG = dijkstra(s: g, n: n, graph: graph)
    var minH = dijkstra(s: h, n: n, graph: graph)
    
    // s: 시작점, m: 목적지
    // 두 경우의수 (s - g - h - m)의 최단거리 , (s - h - g - m)의 최단거리 가 (s - m)최단거리와 같다면 가능한 목적지
    for m in destination {
        let sumG = minS[g] + middleCost + minH[m]
        let sumH = minS[h] + middleCost + minG[m]
        
        if sumG == minS[m] || sumH == minS[m] {
            answer.append(m)
        }
    }
    // 오름차순으로 출력
    answer.sort{$0 < $1}
    print(answer.map{String($0)}.joined(separator: " "))
}

// 다익스트라
func dijkstra(s: Int, n: Int, graph: [Int: [(loc: Int, cost: Int)]]) -> [Int] {
    var needVisit = [(loc: s, cost: 0)]
    var idx = 0
    var min = Array(repeating: 2000000000, count: n+1)
    min[s] = 0
    
    while idx < needVisit.count {
        let node = needVisit[idx]
        idx += 1
        if graph[node.loc] == nil { continue }
        for i in graph[node.loc]! {
            let dist = i.cost
            if node.cost + dist < min[i.loc] {
                min[i.loc] = node.cost + dist
                needVisit.append((loc: i.loc, cost: min[i.loc]))
            }
        }
    }
    return min
}

내가 푼 풀이

접근방법: BFS

이 문제는 이분그래프의 성질을 이해하고 있다면 더 쉽게 풀 수 있습니다.

저는 이분그래프의 성질을 알고 나서 풀었습니다..

이분그래프의 성질은 인접한 점끼리는 서로 다른 집합이어야합니다.

집합1: [1,3] , 집합2: [2,4] 으로 위 그래프는 이분그래프입니다.

위 그래프는 2번과 인접한 점 [1, 3, 4]이 있습니다.

두개의 집합으로 분할했을 때, [1,3,4], [2]로 나눌 수 있지만 3번과 4번이 서로 인접한 관계이므로 이분그래프가 될 수 없습니다.

위 성질을 이용해 BFS탐색을 통해 현재지점과 인접한 지점을 다른 집합으로 분리한다.

탐색을 진행하며 현재노드와 인접한 노드가 같은 집합으로 속한다면, 해당 그래프는 이분그래프가 아니라고 판단한다.

예제그래프)

- 현재노드 1번 - 인접노드 2번

결과: [1], [2]

- 현재노드 2번 - 인접노드 1번, 3번, 4번

1번은 이미 다른집합으로 분리되었다.

결과: [1,3,4], [2]

- 현재노드 3번 - 인접노드 2번, 4번

현재노드인 3번과 인접노드 4번이 이전 탐색을 통해 같은 집합으로 저장되어 있었다.

결과 -> 이분그래프가 아님.

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

import Foundation

// 테스트케이스 수
let K = Int(readLine()!)!

for i in 0..<K {
    // 입력받기
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let V = input[0], E = input[1]
    var graph = [Int: [Int]]()
    for j in 0..<E {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        if graph[input[0]] == nil {
            graph[input[0]] = [input[1]]
        } else {
            graph[input[0]]?.append(input[1])
        }
        if graph[input[1]] == nil {
            graph[input[1]] = [input[0]]
        } else {
            graph[input[1]]?.append(input[0])
        }
    }
    
    var visited = Array(repeating: 0, count: V+1)
    var isBinaryGraph = true
    
    // BFS
    // 그래프 정점을 이분했을때 두개의 집합으로 나누자 1번집합과 -1번집합
    // visited 0: 방문하지않음, 1: 1번집합에 속함, -1: -1번집합에 속함
    // BFS탐색을 통해 인접한 접점은 현재 집합과 다른 집합에 속해야한다.
    // 만약 현재 노드의 접점과 인접한 접점이 같은 집합에 속한다면, 이분그래프로 나타낼 수 없다.
    // 간선 연결없는 접점이 존재할 수 있으므로 모든 접점을 BFS탐색 진행한다.
    for i in 1...V {
        if visited[i] != 0 { continue }
        var needVisit = [i]
        visited[i] = 1
        var idx = 0
        while idx < needVisit.count {
            let node = needVisit[idx]
            let color = visited[node] == 1 ? -1 : 1
            if graph[node] == nil { break }
            for j in graph[node]! {
                if visited[j] != 0 {
                    if visited[node] == visited[j] {
                        isBinaryGraph = false
                        break
                    }
                } else {
                    visited[j] = color
                    needVisit.append(j)
                }
            }
            if !isBinaryGraph { break }
            idx += 1
        }
    }
    if isBinaryGraph {
        print("YES")
    } else {
        print("NO")
    }
}