재원블로그 재원블로그

이 문제는 구현 문제이다. 문제 설명 자체가 좀 어려운데, 간단하게 말하면 해당 위치의 배열 값으로 위치를 계속 바꿔가면서, 순환되는 숫자들을 그룹으로 묶고, 그 그룹들 중 가진 숫자가 큰 두개의 그룹의 숫자를 곱한 값을 리턴하면 된다. 기본으로 주어지는 cards는 인덱스가 0부터 시작해 문제가 복잡해질 것 같아 새로 card 배열을 만들고 인덱스와 카드 숫자가 일치하도록 만들었다. #include #include #include using namespace std; #define MAX 100 int card[MAX + 1]; int maxSize; void init(vector& cards) { for (int i = 0; i < cards.size(); i++) { card[i + 1] = car..

이 문제는 LIS 문제 알고리즘을 이용해서 푸는 문제이다. 입력 값 최대가 10만이므로, O(n^2) 알고리즘 사용이 불가능하다. 따라서 O(N log N) 이하의 알고리즘을 찾아야 한다. 전깃줄이 꼬이지 않게 하는 최소의 제거 전깃줄 수를 구하는 문제는 다르게 말하면 전깃줄이 꼬이지 않는 최대의 전깃줄 수를 구하는 것과 같다. 즉, 이는 입력 배열에서 LIS를 찾고 이를 N과 빼주면 된다는 말과 같다. LIS를 구하는 알고리즘 중 O(N log N) 시간을 요구하는 방법은 이분 탐색을 이용하는 방법이다. 해당 알고리즘을 통해 LIS를 구하고, 이를 N과 빼주면 정답이 나온다. #include #include #include using namespace std; #define MAX 100000 int ..

이 문제는 이분 탐색을 이용해서 푸는 문제이다. 사대의 수 M은 [1, 100,000] 이고, 동물의 수 N도 [1, 100,000]이다. 즉, 각 사대나 각 동물에 대해서 모든 동물 혹은 모든 사대를 루프로 검색하는 것은 시간 초과가 난다. 따라서 O(N log N) 이하의 알고리즘을 생각해야 한다. 각 사대에 대해 동물을 이분 탐색으로 찾는 것보다는 각 동물에 대해 사대를 이분 탐색으로 찾는 게 더 쉬워보였다. 따라서 사대 배열을 오름차순으로 정렬하고, 각 동물에 대해 루프를 돌며 이분 탐색을 수행한다. 이분 탐색 로직의 경우에는 우선 mid를 찾고, 해당 인덱스의 사대에 대해서 거리가 사정거리 이하면 true를 리턴한다. 만약 아닐 경우, 사대가 동물보다 오른쪽에 있는 경우에는 왼쪽 사대들을 검색해..

이 문제는 이분 탐색을 이용해서 푸는 문제이다. 이 문제는 일단 입력이 최대 40,000 이므로 O(N log N) 이하의 알고리즘으로 풀 수 있다. 이 문제의 핵심은 이 문제가 LIS (Longest Increase Subsequence) 문제임을 파악하는 것이다. 나는 이걸 파악하지 못해 검색을 통해 알게 되었다. 입력 예시를 보면 6 4 2 6 3 1 5 와 같은데, 꼬이지 않는 최대의 선 개수이므로 2, 3, 5를 고르면 된다. 이 형태가 최장 증가 수열이므로 LIS를 구하면 된다. LIS는 두 가지 방법이 있는데, 하나는 DP를 이용해서 푸는 방법이고 다른 하나는 이분 탐색을 이용해서 푸는 방법이다. DP를 이용할 때에는 dp[i] = i번째 값을 포함한 최장 증가 수열의 길이로 놓고 이중 루프..

이 문제는 수학을 이용해서 푸는 문제이다. 점 찍기 문제와 거의 동일한 문제이다. 한 가지 다른 점은 원 내부에 또 다른 원이 있고, 그 원 안에 점은 포함하지 않는 것이다. x가 1부터 r2 - 1 까지 루프를 돌며 y좌표를 계산하면 간단히 풀 수 있다. 이 때 유의할 점은 x가 r1 + 1부터 x가 r2 - 1까지인데, 이때는 calculateLow()가 엉뚱한 값을 내놓기 때문에 low를 1로 설정한 뒤 점의 개수를 세어주는 것이다. 또 하나 주의할 점은 이유는 모르겠지만 자료형을 전부 long long으로 놓아야 문제가 제대로 풀린다는 것이다. 두 가지만 주의하면 어렵지 않게 풀 수 있다. #include #include #include using namespace std; typedef long..

이 문제는 수학을 이용해서 푸는 문제이다. 콜라츠 추측에 대한 정보가 주어지는데 이는 그대로 구현하면 된다. 범위에 대한 설명이 헷갈렸는데, [a, -b]에 대해서 [a, 콜라츠 추측 루프 횟수 - b] 로 정의하는 것만 조심하면 된다. 정적분에 대해서는 루프를 돌면서 사다리꼴의 넓이를 구해주는 방식으로 구했다. #include #include #include using namespace std; vector collatz(int number) { vector results(1, number); while (number != 1) { if (number % 2 == 0) { number /= 2; } else { number = number * 3 + 1; } results.push_back(number..

이 문제는 재귀를 이용해서 푸는 완전 탐색 문제이다. 이 문제에서 중요한 점은 하나의 곡괭이를 잡으면 광물 5개를 무조건 캐고 버린다는 것이다. minerals의 최대 길이가 50이고, 곡괭이는 3개 중 하나를 선택하게 되는데, 곡괭이 하나당 광물 5개를 캐므로 실제 최악 시간 복잡도는 3^10 ~= 60,000 이 되어 충분히 완전 탐색으로 문제를 풀 수 있다. #include #include #include using namespace std; #define DIA 0 #define IRON 1 #define STONE 2 #define INF 1000000000 int fatique(int pick, string mineral) { switch (pick) { case DIA: if (mineral..

이 문제는 우선순위 큐를 이용하여 푸는 문제이다. 이 문제를 처음 봤을 때, 그리디 아니면 DP 문제라고 생각했다. 그러나 DP 배열을 만들기에는 입력 값들이 너무 컸고, 그리디는 어떤 방식으로 동작하는 지 끝내 찾아내지 못했다. 그래서 검색을 통해 찾아본 결과 우선순위 큐를 사용하는 아주 간단한 풀이가 있었다. 우선순위 큐를 최소 힙으로 만들고, enemy에 대해 루프를 돌면서 최소 힙에 삽입한다. 이 때 최소 힙의 크기가 k보다 커지는 순간은 무적권의 사용 한도를 넘었다는 것이 되므로, 최소 힙에서 하나를 빼어 현재 가지고 있는 병사에 수에서 뺀다. 만약 이 순간에 남은 병사보다 최소 힙에서 추출한 값이 더 크다면 라운드를 더 이상 진행할 수 없는 것이므로 현재 인덱스를 리턴한다. 만약 루프가 모두 ..