[BOJ] 9466, 1202, 14003, 2166

BOJ 9466 : 텀 프로젝트

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

9466번: 텀 프로젝트

 

DFS 문제이다. 크게 어렵지는 않은데, 주의할 만한 점은 vertex의 개수가 100000이므로 (edge의 개수도 당연히 100000이다) 모든 정점에 대해 BFS를 수행하면 O(VE)니까 TLE가 뜬다. 

 

따라서 한 번 방문한 vertex에 대해서는 다시 방문하면 안 되고, cycle이 발생하는 경우에도 잘 체크를 해 줘야 한다. 어떤 방식으로든 한 번 방문한 vertex를 다시 방문하지 않도록 만드는게 중요한 문제였다.

 

난 처음에 분명히 O(V)로 짠 것 같은데 자꾸 TLE를 받았는데, 로직 자체는 O(V)인데 for문에 들어갈 때마다 10만짜리 vector를 계속 초기화시켜줘서 그런 거였다. .

 

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/9466/9466.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

 

---

BOJ 1202 : 보석 도둑

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

1202번: 보석 도둑

 

greedy하게 해결하면 된다. 큰 가방부터 담으면 안 되고, 선택지의 숫자를 줄이는 방향인 작은 가방부터 담아주면 된다. 따라서 가방 크기를 sort한다.(KlogK)

 

이제 작은 가방부터 집어서 담을 수 있는 보석 중 가장 비싼 보석부터 담는다. 이때 보석을 N번 돌아서 체크하면 O(NK)이므로 안 되고, 가능한 보석의 set을 설정해서 현재 가방보다 Mi가 작은 보석들을 set에 넣으면 된다. 그리고 set에서 Vi가 큰 보석부터 꺼내야 하므로 set을 priority queue로 구현하면 되겠다는 생각을 할 수 있다. 이 경우 time complexity는 O(KlogN + NlogN)이 된다.

 

따라서 총 time complexity는 O(KlogK + KlogN + NlogN)이다. 이대로 구현하면 그냥 풀리는데 나는 RTE를 받았다.

 

문제 조건에 의해 N<K인 경우가 있을 수 있기 때문이다. 이 경우 priority queue가 empty한데 pop()을 하려고 하는 경우가 생겨 RTE를 받을 수 있으므로 조심하도록 한다. 이것만 조심하면 AC를 받을 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1202/1202.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

---

BOJ 14003 : 가장 긴 증가하는 부분 수열 5

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

14003번: 가장 긴 증가하는 부분 수열 5

 

LIS는 well-known 문제다. LIS를 O(NlogN)으로 해결하는 알려진 풀이는 segment tree를 이용하는 것과 binary search를 이용하는 것이 있다. BOJ 12015 을 풀 때는 segment tree를 써도 크게 귀찮지 않았던 게, Ai의 값이 1e6 이하의 자연수로 제한되었기 때문이다.

 

이 문제는 좀 다르다. BOJ 12738 처럼 Ai의 범위가 -1e9 <= Ai <= 1e9다. 그냥 segment tree를 쓸 수 없다. 따라서 segment tree를 쓰려면 좌표압축을 먼저 해야 한다. 또한 LIS도 출력해야 하므로 좌표 압축을 통해 줄였던 값을 다시 원상 복구해 주어야 한다. 이게 귀찮아서 binary search를 이용하는 해를 사용했다.

 

binary search를 이용하는 풀이는 다음과 같다.

DP[i] = 길이가 i인 LIS의 마지막 숫자의 최솟값 

으로 설정하고 i를 1에서 N까지 돌리면 된다. 이게 가능한 이유는 DP[i]가 반드시 오름차순으로 만들어질 수 밖에 없기 때문이다. 따라서 Ai가 들어갈 적절한 자리를 DP[i]에서 O(logN)만에 찾으면 전체 O(NlogN)만에 해결할 수 있다.

 

이는 그런데, 이 문제는 BOJ 14002 처럼 backtracking을 필요로 한다. 이걸 구현하는게 좀 까다롭다. LIS를 만들 때 각 숫자가 만들어질 때 이전에 어느 숫자에서 왔는지를 기록해 두어야 한다. LIS 배열의 각 값은 계속 갱신되기 때문에 LIS[k]를 만들 때 사용되었던 LIS[k-1]이 갱신되어서 실제로 LIS를 만들었던 값이 아닐 수 있기 때문이다. 이런 예는 1 3 4 2 가 있다. 실제로 LIS를 만든 숫자들은 1 3 4지만 맨 마지막의 LIS는 1 2 4로 갱신되어 있다.

 

따라서 이전에 어느 숫자에서 왔는지를 기록해 둔 후 backtracking하면 된다. segment tree로 구현해도 크게 다르지 않을 것이다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/14003/14003.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

이건 BOJ 12015 풀이인데 segment tree를 이용해서 풀었으니 참조해 보길 바란다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/12015/12015.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

---

BOJ 2166 : 다각형의 면적

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

2166번: 다각형의 면적

 

외적을 이용하는 문제이다. 세 점 A, B, C로 만든 두 벡터 AB, AC의 외적값은 |AB||AC|sin(theta)이므로 ABC로 만들어지는 평행사변형의 넓이와 같다. 이를 반으로 나누면 ABC로 만든 삼각형의 넓이가 된다.

 

다각형의 넓이도 같은 방식으로 구하면 된다. 점 A1, A2, A3, ... An이 있다면

1/2{(A1A2 × A1A3) + (A1A3 × A1A4) + ... + (A1An-1 × A1An)}

은 전체 다각형 S의 넓이와 같다. 이는 볼록 다각형 뿐 아니라 오목 다각형의 경우에도 적용이 가능하다. 그 이유는 오목 다각형의 경우에는 cross product의 부호값이 -가 되어서 빠져야 하는 부분은 넓이에서 빼게 되기 때문이다.

 

이 부분에 대해서는 내가 이전에 썼던 https://jordano-jackson.tistory.com/27?category=1004558 를 참조해 보면 좋다.

[Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘

 

일반적으로 이 방법을 CCW라고 하는 경우가 있던데 왜 CCW 알고리즘이라고 하는지는 잘 모르겠다. cross product로 CCW, CW를 구별할 수 있는 건 맞는데 그게 알고리즘 이름이 되는 건 이해하기 어려운 구석이 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/2166/2166.cpp

GitHub - Jordano-Jackson/PS: Problem solving