재원블로그 재원블로그

이 문제는 세그먼트 트리를 이용해서 풀었다. 값을 저장하는 쪽에는 모두 long long 을 써줘야 풀린다. 세그먼트 트리를 구현할 수만 있으면 풀리는 기초 문제였다. 몇 가지 주의할 점이 있는데, 첫번째로는 update를 할 때 차이를 더해줘야 하므로 c - arr[b]를 한 값을 update의 인자로 던져줘야 한다. 이 때문에 update 전에 입력 배열인 arr[b] = c를 해줘야 한다. 이거 안해줘서 계속 틀렸었다. 두번째는 update의 dif 또한 long long으로 선언해야한다는 것이다. 값이 int 자료형을 가뿐히 뛰어넘을 수 있기 때문이다. 로직은 단순하나 자료형으로 정답률을 낮춘 문제였다. #include #include #include #include #include using n..

이 문제는 최소 스패닝 트리 문제이다. 별의 개수 n개의 최대는 100이므로, O(N^2) 으로 모든 간선을 만들 수 있다. 모든 별들을 잇는 대신에, 직/간접적으로 이어저야한다. 이는 최소 스패닝 트리를 의미하므로, 크루스칼 알고리즘을 사용해서 문제를 풀었다. 절대/상대 오차를 10^(-2) 까지 허락하므로 cout > n; for (int i = 0; i > x >> y; stars.push_back({ x, y }); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { pair &s1 = stars[i]; pair &s2 = stars[j]; double x = s1.first -..

이 문제는 투 포인터를 이용해서 풀었다. 자연수 N이 최대 400만이므로, 400만 이하의 소수를 찾으면 된다. 연속된 소수의 합으로만 나타내야하므로, 투 포인터를 쓰면 딱 맞다. 만약 acc가 N보다 작다면 right을 증가시켜주고, 크다면 left를 증가시켜 문제를 해결할 수 있다. 400만 이하의 소수의 개수는 약 30만개이므로, 충분히 시간 안에 풀 수 있다. #include #include using namespace std; #define MAX 4000000 int N; bool isPrime[MAX + 1]; vector primes; void init() { for (int i = 0; i

이 문제는 다이나믹 프로그래밍으로 풀었다. 시간 제한이 0.5초로 약 5,000만번의 연산만을 사용해야 한다. dp[i][j] = i번 집을 j 색으로 칠했을 때의 최소 비용 으로 설정하고 문제를 풀었다. 가장 까다로운 부분은 N번 집의 색이 N - 1번, 1번 집과 색이 같지 않아야 한다는 것인데, 이는 dpRed, dpBlue, dpGreen과 같이 첫 집을 어떤 색으로 칠했냐로 설정할 수 있었다. 사실 이럴 필요 없이 배열 하나로 충분하지만, 코드 쓰다 헷갈리지 않기 위해 이렇게 썼다. #include #include #include using namespace std; #define MAX 1000 #define RED 0 #define GREEN 1 #define BLUE 2 int N; int..

이 문제는 이분 탐색을 이용한 LIS 알고리즘으로 풀었다. 전형적인 LIS 문제지만, 최대 배열의 크기가 100만이므로 이분 탐색을 사용해야 한다. 또한 단순히 길이를 출력하는 데서 그치지 않고, 직접 답을 내야하므로 record 배열을 따로 두었다. #include #include #include using namespace std; int arr[1000000]; int N; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 0; i > arr[i]; } vector lis; vector record; for (int i = 0; i < N; i++) { in..

이 문제는 이분 탐색을 이용한 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 ..