2568번: 전깃줄 - 2
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결
www.acmicpc.net
간단한 문제 요약
두 전봇대 사이에 여러 개의 전깃줄이 있다. 이 전깃줄 등 교차하는 경우가 발생했다. 그래서 교차하지 않도록 몇 개의 전깃줄을 최소한으로 제거하려 할 때 없애야 하는 전깃줄의 A 전봇대에 연결되는 위치 번호를 오름차순으로 출력하시오.
고려해야 할 사항
- 답이 여러 개의 경우가 있을 수 있습니다. 그 중 하나를 출력해야 합니다.
- 전깃줄의 개수가 최악의 경우 100,000개입니다.
문제 풀이
이 문제는 LIS 알고리즘 + 역추적(정말 쉽습니다)을 알면 정말 편하게 풀 수 있습니다... LIS 관련 문제 14002: 가장 긴 증가하는 부분 수열4 문제는 이 문제랑 같은데 O(N^N)으로도 풀 수 있습니다. 문제 관련 포스트를 작성했습니다.
시간복잡도
LIS(Longest Increasing Suqsequence) 알고리즘, o(n^n). 이중 포문으로 가장 긴 증가하는 부분 수열을 찾는 방법을 알고 있으셔야 좋습니다. 위에서 언급한 문제와 다르게 이 문제는 최악의 경우 A, B 두 전봇대에서 연결할 수 있는 연결 위치가 각각 100,000개씩 존재합니다. 그래서 이중 루프를 활용한 LIS 알고리즘을 사용할 경우 100,000 * 100,000 = 10,000,000,000 번의 연산 횟수가 나오고 백준에선 약 10억 연산당 1초로 가정하는데(불확실할 수 있습니다.) 탈락 나옵니다.
반면 이분 탐색을 통한 LIS 알고리즘으로 이 문제를 접근할 경우 O(n*logn)입니다. 루프 한 개에 각각의 경우에 대한 이분탐색을 통해 최악의 경우 100,000* log100,000 = 100,000 * log10^5 = 500,000의 연산 횟수?????? 아무튼 확 줄어듭니다. (대단한데,,)
그래서 이분 탐색을 통한 LIS 알고리즘으로 이 문제를 접근해야 합니다. 옛날에 LIS 개념을 몰라서 전깃줄 문제를 풀었을 때 3일 동안 고민했는데 결국 풀지 못했었습니다.. LIS를 알고나니 알고리즘의 대단함을 느꼈습니다.
LIS로 이 문제를 풀 수 있는 이유 + 접근법
이 문제를 LIS 알고리즘을 적용할 수있는 이유는 한 전봇대의 연결 위치 번호를 순차적으로 소팅하면 B 전봇대의 위치 번호는 데이터, A 전봇대의 위치 번호는 index의 역할로 가정할 수 있게 됩니다. 초점을 양 전봇대 두 개의 경우에서 한 전봇대의 위치 번호에만 집중할 수 있게 됩니다. 또한 각 연결 위치 번호는 중복되지 않기 때문입니다.
| A 전봇대 | B 전봇대 |
| 1 | 8 |
| 3 | 9 |
| 2 | 2 |
| 4 | 1 |
| 6 | 4 |
| 10 | 10 |
이 문제는 없애야 하는 전깃줄의 A 위치번호를 출력하기 때문에 B 전봇대의 위치 번호를 오름차순으로 소팅합니다.
| A 전봇대 | B 전봇대 |
| 4 | 1 |
| 2 | 2 |
| 6 | 4 |
| 1 | 8 |
| 3 | 9 |
| 10 | 10 |
B 전봇대는 순차적으로 증가합니다. B = [1,2,4,8,9,10] 이는 결국 [1,2,3,4,5,6]로 퉁 쳐도 됩니다. 어차피 B 전봇대 각각의 연결 번호를 바꿔도 순서에 지장이 없기 때문입니다. ( 치환 했다는 느낌으로다가,,)
그렇게 가정을 새롭게 하면
| A 전봇대 | B 전봇대 |
| 4 | 1 |
| 2 | 2 |
| 6 | 3 |
| 1 | 4 |
| 3 | 5 |
| 10 | 6 |
좋습니다. 한쪽이 정렬 되었을 때, "이분 탐색"을 사용할 수 있습니다. 이분 탐색은 정렬된? sequence일 때 사용이 가능하기 때문입니다. B 전봇대는 index, A 전봇대는 값 느낌.
이제 A전봇대에만 집중해서 한 개의 루프를 사용해 A 전봇대의 위치 번호에서 증가하는 원소를 찾아 가장 긴 개수를 반환하는 LIS 알고리즘을 사용하면 됩니다. 사실 이 문제 이전에 LIS 관련 문제 14002: 가장 긴 증가하는 부분 수열4 문제에서 O(nlogn)으로 푸는 방법에 대해 고민을 했고 한 가지 재밌는 해결 방법을 얻게 되었습니다. 이 풀이가 맞는지는 모르겠지만..
이분 탐색O(logn)을 활용한 LIS 알고리즘O(n*logn) 간단 개념
LIS에서 이분 탐색을 사용할 때 가장 중요한 것은 이분 탐색 시 탐색에 사용될 배열이 정렬되어 있어야 합니다. 그리고 이분 탐색을 통한 LIS 알고리즘을 사용했을 때 결과적으로 삽입 or 이분 탐색을 통해 교체 된 원소들로 이루어진 배열의 크기로 LIS 길이만 반환한다는 것입니다. 중요한 것은 배열 안에 들어있는 원소들은 정확한 부분적으로 증가하는 원소들로 이루어져있을 수도 이루어지지 않을 수도 있습니다.
[1 3 4 2 5 6]
이 경우에 LIS를 통해 LIS길이가 들어있는 배열 안 원소는 [1 2 4 5 6]입니다. 하지만 실제로 부분적으로 증가하는 가장 긴 수열은 [1 3 4 5 6]입니다. 배열 값이 전자의 경우가 나오는 이유는 이분 탐색의 개념을 사용할 때 포문을 사용하는 것보다 시간복잡도 측면에서 가성비가 있고, 특정 조건 -> 이분탐색에 의해 교체된 원소는 실제로 가장 긴 증가하는 부분 수열이 아니지만 길이 측정에서는 다음원소보다 똑같이 작기 때문입니다. 2 vs 3 뭐든 4보다 작다 == LIS 길이에 영향x.
func binarySearch(_ seq: inout [Int],_ target: Int) {
var l = 0, r = seq.count-1, mid = 0
while l<r {
mid = (l+r)/2
if target > seq[mid] {
l = mid + 1
}else {
r = mid
}
}
seq[r] = target
}기본적인 이분 탐색 알고리즘입니다.
let lists = [1,3,4,2,5,6]
var sequence = [lists.first!]
// 루프 한 개!
(1..<n).map{
if lists[$0] > sequence.last! {
sequence.append(lists[$0])
}else {
binarySearch(&sequence, lists[$0])
}
}헉 이렇게 보니 이분 탐색을 활용한 LIS 대박 간단하네요..
LIS 알고리즘은 루프 단 한 개 사용합니다. 그리고 sequence 배열은 lists에서 오름차순으로 증가하는 원소들을 LIS 알고리즘에 의해 추가되거나 교체되어 LIS 길이를 반환합니다. 원리는 간단합니다.
처음에 lists의 첫 원소를 sequence배열에 삽입합니다. sequence는 현재 정렬 되어있다고 말 할 수 있습니다.( == 이분 탐색 사용 가능)
그리고 lists의 다음 원소들부터 마지막 원소까지 순차적으로 탐색하는데!!!!!
만약 sequence의 마지막 값이 순차적으로 탐색중일 때 lists의 특정 원소보다 작다면, 즉 특정 원소가 sequence의 마지막 값보다 크다면 sequence에 추가합니다. ( 추가하기 전 마지막 원소보다 크다! 그 추가했을 때 추가된 원소가 가장 크다! == 정렬 되있다. == 이분 탐색 사용 가능합니다.)
ex) lists = [1,3,4,2,5,6]일 때
case: $0 == 1
if lists[$0] > sequence.last! == 3 > 1이므로
sequence = [1,3]
case: $0 == 2
if lists[$0] > sequence.last! == 4 > 3이므로
sequence = [1,3,4]
sequence 원소들은 실제로도 현재 lists의 원소가 들어있고 가장 긴 증가하는 부분 수열입니다.
만약 lists의 특정 원소 "$0"가 sequence의 마지막 값보다 작다면 이분 탐색을 실행합니다.
case: $0 == 2
if lists[$0] > sequence.last! == 2 < 3이므로 else 구문의 이분 탐색 실행.
[1,3,4]에서 2가 들어갈 자리, 교체 자리는 sequence에서 lists[$0] == 2보다 큰 next원소의 index가 됩니다. 즉 3의 위치에 2가 삽입됩니다.
[1,2,4] 사실 1,2,4는 1 3 4 2 에서 가장 증가하는 부분 수열이 될 수 없습니다. 1 2가 되야 합니다. increasing subsequence이기 때문입니다. 하지만 단순히 가장 긴 증가하는 부분 수열의 길이를 반환받고 싶을 경우엔 교체 해도 4보다 작기에 상관이 없습니다. 이 점을 이용하는 것입니다.
계속해서 루프가 끝나면
sequence = [1,2,4,5,6]. count = 5입니다. 즉 가장 긴 증가하는 부분 수열 길이는 5 입니다. 그러나 실제로 라면 1 3 4 2에서 1 2 4가 될 수 없습니다.
전깃줄 - 2 문제 이분 탐색O(logn)을 활용한 O(nlogn) 풀이
이 문제에서 요구하는 것은 잘라야 하는 가능한 적게 전깃줄을 끊었을 때 교차 지점이 없는 그 각각의 전깃줄 A 위치번호입니다. 잘라야 하는 것은 가장 긴 부분 수열에 포함되지 않는 원소들을 잘라야 합니다.
| A 전봇대 | B 전봇대 |
| 1 | 1 |
| 3 | 2 |
| 4 | 3 |
| 2 | 4 |
이 부분에서 가장 긴 증가하는 부분 수열의 A 전봇대 번호들은 1 3 4 입니다. 2를 제거하기만 하면 됩니다. 그리고 제거 된 2를 출력하면 됩니다.
하지만 이분 탐색을 통한 LIS을 했을 때 결과가 담긴 sequence는 원소 개수로 LIS길이 3임은 알고있지만 내부 값은 [1,2,4] 입니다. 이 경우 lists에서 1,2,4를 뺀 나머지는 A 전봇대 위치는 3이 됩니다. (오답) // 2가 되야합니다.
LIS 개념 응용.
그래서 머리를 굴려봤는데 앞에서 언급한 LIS 알고리즘 map의 로직 각각에 dp를 추가하는 것입니다.( dp배열은 현재 순차적으로 탐색중인 각각의 위치에 대해서 해당 원소가 앞의 원소들 중에서 몇번째로 증가하는 원소인지 값 저장)
추가적으로 binarySearch(_:_:)에는 target 원소가 들어갈 자리 right(에 담겨있는)를 반환합니다. 여기서 반환된 위치는 예를들어
[1 3 4] 에서 2가 들어갈 위치 index 1(값:3)라는 것을 알았을 때 [1,2,4]가 되면 앞에 원소1이 있습니다. subsequence에서 index1이라는 말은 두 번째로 증가한다. 하지만 제가 사용한 이분탐색에서 left,right,mid 변수.. left가 index 0부터 시작합니다. 그래서 index 1이라는 말은 결국엔 앞에 원소가 하나 더 있다 index0.. 그래서 binarySearch() +1 했습니다.
subsequence는 항상 LIS 최고 길이를 담고 있습니다. 이를 이용했습니다. 결국에 sequence배열에 lists의 값을 추가한다는 것은 이제 막 추가된 따근따근한 원소가 lists의 특정 위치에서 가장 긴 길이라는 것을 알고 있고 이 정보를 dp[$0]에 저장해주면 됩니다.
LIS 응용 개념 예시
1 3 4 2 5 를 예시로 들자면
lists[1,3,4,2,5]
subsequence[1]
case $0 == 1
if lists[$0] > subsequence.last! ( == 3 > 1)
subsequence.append(3) // 현재 1,3 중에서 LIS길이 = 2. 이정보를 dp[1]에 담습니다. 당연히 dp[0]은 1입니다. 각 원소들은 최소한 1씩 최장 증가 부분 느낌으로,,
dp == [1,2] // lists 각각의 원소가 최대한 몇 증가하는 부분 수열 길이인지
subsequence == [1,3]
case $0 == 2
if lists[$0] > subsequence.last! (== 4 > 3)
subsequence.append(4) // lists에서 index == 2일때 가장 증가하는 부분 수열 길이는 subsequence.count == 3입니다.
dp == [1,2,3] // 각각의 index일 때 lists는 이전 원소보다 몇 개나 큰가.(증가하는 부분 수열 개수인가)
subsequence == [1,3,4]
case $0 == 3
if lists[$0] > subsequence.last! (== 2 > 4) x
else {
let idx = binarySearch(..) == subsequence의 원소 3 index 1이 반환됩니다.
dp[$0] == idx + 1
dp == [1,2,3,2] // lists 의 index == 3일 때 원소 2는 1,2,3,2 에서 1,2. LIS길이가 2입니다.
subsequence == 1,2,4 // 역시 최장 증가 부분 수열의 개수는 여전히 3.
case $0 == 4
if lists[$0] > subsequence.last! (== 5 > 4)
subsequence.append(5) // 4보다 큰 원소 5!! subsequence.count == 4 !!! lists[1,3,4,2,5]에서 LIS는 4
dp[$0] = subsequence.count
dp == [1,2,3,2,4]
subsequence.count = 길이 4
여기까지 이분 탐색을 활용했기에 !! O(n*logn)입니다.
역추적. Backtracking
그리고 남은건 dp 에 담긴 특정 원소가 lists 에서 몇 번째로 증가하는 길이인지에 대한 정보를 토대로 역추적 하는 개념입니다.
다른 것은 없고 dp에 담긴 정보는 결국!!! subsequence.count길이가 순차적으로 증가된 정보 or 더 작은 값을 담고 있기에
dp의 가장 큰 원소를 기준으로 dp 배열 마지막 원소부터 첫번째 원소까지 반대로 순차적으로 큰 값들을 찾아가면 됩니다.
글로 설명하는 것보다 코드를 보는게 더 ..
func backtracking(_ dp: [Int]) -> [Int] {
var target = dp.max()!
var sequence: [Int] = []
for i in stride(from: dp.count-1, through: 0, by: -1) where dp[i] == target {
sequence.append(lists[i].left)
target -= 1
}
return lists
.map { $0.left }
.filter{ !sequence.contains($0)}
.sorted()
}여기서 중요한 것은 target은 dp의 max 값이 담겼는데 바로 위에서 언급했지만 subsequence.count // 1씩 증가됨,, 결과에 대한 lists원소를 추출하기 위함입니다.
if 문 대신 where 키워드를 사용했습니다. (where 키워드 정리 관련 포스트)
sequence의 원소를 역으로 루프 하면서 dp[i] == target인 경우
위 그림처럼.
dp.max() == 4. target == 4. target -1
dp[3] == 2인데 순차적으로 감소하는게 아니기에 패스
dp[2] == 3 . target = = 3 . sequence에 추가...
반복
sequence = [1,3,4,5] //증가하는 부분 수열
lists에서 sequence를 없는 원소를 찾아 뺀 값이 잘라야 할 전선이 됩니다.
코드
//MARK: - Properteis
var lists: [Cable] = []
(0..<Int(readLine()!)!).map{ _ in
let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
lists.append(Cable(left: input[0], right: input[1]))
}
//MARK: - Models
struct Cable {
let left: Int
let right: Int
}
extension Cable: Comparable {
static func <(lhs:Cable,rhs:Cable) -> Bool {
return lhs.right < rhs.right
}
}
//MARK: - Helpers
func binarySearch(_ seq: inout [Int],_ target: Int) -> Int {
var l = 0, r = seq.count-1, mid = 0
while l<r {
mid = (l+r)/2
if target > seq[mid] {
l = mid + 1
}else {
r = mid
}
}
seq[r] = target
return r
}
//주요 로직
//MARK: - Helpers
func backtracking(_ dp: [Int]) -> [Int] {
var target = dp.max()!
var sequence: [Int] = []
for i in stride(from: dp.count-1, through: 0, by: -1) where dp[i] == target {
sequence.append(lists[i].left)
target -= 1
}
return lists
.map { $0.left }
.filter{ !sequence.contains($0)}
.sorted()
}
func solution() {
lists.sort()
let n = lists.count
var subsequence = [lists.first!.left]
var dp = Array(repeating: 1, count: n)
(1..<n).map{
if lists[$0].left > subsequence.last! {
subsequence.append(lists[$0].left)
dp[$0] = subsequence.count
}else {
let idx = binarySearch(&subsequence, lists[$0].left) + 1
dp[$0] = idx
}
}
let res = backtracking(dp)
print(res.count)
print(res.map{String($0)}.joined(separator:"\n"))
}
solution()'백준 PS일지 > LongestIncreasingSubsequence' 카테고리의 다른 글
| [백준/Swift] 3745: 오름세. while문 무한 입력 EOF처리 방법 | PS일지 (0) | 2023.02.21 |
|---|---|
| [백준/Swift] 14002: 가장 긴 증가하는 부분 수열4 파해치기 | PS일지. (0) | 2023.02.18 |
| [백준/Swift] 2565 : 전깃줄 (0) | 2022.07.20 |
