재원블로그 재원블로그

이 문제는 이분 탐색을 이용한 LIS 알고리즘으로 풀었다. 이 문제에서 전깃줄의 개수는 최대 100,000개이므로 O(N^2) 알고리즘으로는 불가능하다. 즉, O(N log N) 이하의 알고리즘을 생각해야 한다. 전깃줄이 교차하는 것을 제거하는 것을 반대로 생각해보면 아무것도 없는 상태에서 전깃줄이 교차하지 않게 가장 많이 설치하는 문제와 같게 된다. 이는 전봇대 A의 순서로 정렬했을 때 랜덤하게 있을 전봇대 B의 순서에서 가장 긴 증가하는 부분 수열, LIS를 구하는 문제와 동일하게 된다. DP를 이용한 LIS 문제는 O(N^2)이 걸리지만, 이분 탐색을 이용한 LIS 문제는 O(N log N) 시간이 걸리므로 충분히 시간 안에 풀 수 있다. #include #include #include #inclu..

이 문제는 유니온 파인드, CCW 알고리즘을 사용해서 풀었다. CCW 알고리즘을 처음 알게 된 문제였다. CCW 알고리즘은 간단히 말해서 외적을 통해 세 점의 방향성을 찾는 알고리즘인데, 이를 이용하여 두 선분간의 교점 여부를 파악하는데 사용했다. 또한 그룹 관련 요구사항도 존재하므로 이는 유니온 파인드로 쉽게 해결할 수 있었다. 각 선분에 대해 다른 선분들을 루프를 돌기 때문에 O(N^2) 시간 복잡도가 걸리지만, 선분이 최대 3,000개이므로 충분히 2초 안에 풀 수 있다. #include #include #include #include #include using namespace std; #define COUNTER 1 #define LINE 0 #define CLOCK -1 struct Line ..

이 문제는 이분 탐색을 이용한 LIS 문제이다. 수열의 최대 크기가 1,000,000이므로 O(N^2) 알고리즘으로는 시간 초과가 나고, O(N log N) 이하 알고리즘을 고안해야 한다. 수열에 대해 루프를 돌면서 벡터의 적절한 위치에 값을 넣는다고 생각하면 쉽다. 이 알고리즘은 워낙 유명해서 그냥 외우고 있었다. 그러나 아직도 왜 이게 답이 나오는 알고리즘인지는 잘 모르겠다. 만약에 {10, 20, 9, 30, 20, 50} 이라는 수열에 대해 LIS의 길이를 구하면 4가 나오는데, 아래의 코드로 출력해보면 9 20 30 50 이라는 전혀 맞지 않는 부분 수열이 나오게 된다. 근데 길이는 정답이 나온다. 백준 14003 문제가 이를 출력까지 하는 문제인데, 여기서 제대로 파봐야겠다. #include ..

이 문제는 구현 문제이다. 규칙성을 찾아내는 것이 가장 중요한 포인트이다. N이 주어졌을 때 가로의 길이는 N번째 홀수와 같다. 따라서 2 * N - 1이 된다. 또한 높이가 주어졌을 때 높이 / 2 한 부분에서 2개의 삼각형이 나오게 된다. 또한 각 2개의 삼각형의 x좌표는 각각 x - height / 2, x + height / 2가 된다. 이러한 규칙성을 찾았다면 재귀를 통해 구현하고, 높이가 3일 때를 base case로 잡아 문제를 해결할 수 있다. #include #include #include using namespace std; vector output; void draw(int y, int x, int height) { if (height == 3) { output[y][x] = '*';..

이 문제는 다이나믹 프로그래밍 문제이다. 이 문제는 LIS 문제를 두 번 쓴 다음에 합치면 되는 간단한 문제이다. dp1[i] : i를 마지막으로 하는 가장 긴 증가하는 부분 수열 (왼쪽 기준) dp2[i] : i를 마지막으로 하는 가장 긴 감소하는 부분 수열 (오른쪽 기준) 으로 세우고 마지막에 각 인덱스 i에 대해 이를 합친 결과 중 가장 긴 것을 답으로 내면 정답이 나온다. #include #include using namespace std; #define MAX 1000 int N; int arr[MAX]; int dp1[MAX]; int dp2[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; f..

이 문제는 분할 정복을 이용해서 푸는 문제이다. 문제가 아주 어려운 얘기로 가득한데, 결론적으로 S1/N1 + S2/N2 + ... + SM/NM 을 구해야 하고, 여기서 곱셈 역원을 계산할 때 b^(x - 2) (mod X) 를 사용하라는 얘기이다. 따라서 이 문제는 분할 정복을 사용하여 거듭제곱을 풀 수 있으면 된다. 값이 매우 크기 때문에 모듈러 연산을 곳곳에 배치해두었다. 중요한 점은 마지막 answer에도 모듈러 연산을 해줘야 정답이 나온다는 것이다. #include #include #include #include #include using namespace std; #define MOD 1000000007 typedef long long LL; LL calculate(LL a, LL x) { ..

이 문제는 다익스트라 알고리즘을 사용해서 풀었다. 이 문제는 얼핏 보면 그냥 dfs와 같은 방식으로 풀릴 것 같지만, 그렇지 않다. 어떤 점에서 다른 점으로 가는 방식이 여러가지라면, 그 중에 가장 cost가 적게 드는 방법으로 가야 한다. 이를 위해 다익스트라 알고리즘을 사용해서 nextCost가 m보다 작거나 같을 때까지 실행한다. 이 때 주의할 점은 다익스트라 알고리즘을 돌리는 와중에 아이템 개수를 추가하면 오답이 나온다. 이는 다익스트라 알고리즘 특성상 이미 방문했더라도 더 짧으면 다시 방문할 수도 있기 때문이다. 따라서 다익스트라 알고리즘을 다 돌린 뒤에 INF가 아닌 점들의 개수를 더해주면 정답이 나온다. #include #include #include #include #include usin..

이 문제는 시뮬레이션 문제로, 구현이 매우 어려운 문제였다. 중간에 풀다가 안 풀려서 구글링을 했지만 bfs를 이용한 풀이가 많았고, 이는 내가 처음에 구현한 것과 접근 방식이 너무 달라 적용하지 못했다. 결국 다시 반례들을 적용하면서 천천히 디버깅했고, 문제를 발견하여 해결할 수 있었다. 내 풀이의 핵심은 RED를 먼저 굴리고, BLUE를 그 다음, RED 한번 더, BLUE 한번 더 이다. 여기서 시간 초과가 나지 않으려면 위 과정을 거쳐도 두 구슬 모두 제자리에 있으면 바로 continue를 해버리는 것이다. 그렇지 않으면 가만히 있는 모든 케이스를 탐색하므로 시간 초과가 발생한다. 내가 놓쳤던 부분은 첫번째로 RED와 BLUE를 탐색하고, 한번 더 탐색하는 부분이었는데, 이 때 매개변수로 받은 r..