백준

1. 문제 풀이 이진 탐색과 누적 합의 응용으로 풀이하였습니다. 처음엔 부배열의 값들이 연속적으로 이루어져 있었기에 투 포인터를 사용해야 하는 거 아닐까? 하는 의문이 생겼습니다. 그러던 중 배열의 크기가 1,000이므로 누적합 배열을 구해놓는다면 O(N^2)으로 부 배열의 모든 합을 구할 수 있다고 판단하게 되면서 이진 탐색을 사용하는 것이 적합할 것 같다는 생각을 하게 됩니다. A, B의 누적합 배열로 중복되지 않은 범위의 부 배열 합 값들을 모두 저장했습니다. 이를 정렬한 다음 lower_bound와 upper_bound를 사용해 경우의 수를 계산해주었습니다. [ 시간복잡도 ]$$ O(N^{2}log M^{2})$$ 2. 코드#include using namespace std;typedef long..

1. 문제 풀이 이번 문제는 에라토스테네스 채의 틀을 응용하여 최적화하는 문제였습니다. 처음부터 이 사실을 알고 진행한 것은 아니었고, 어떤 알고리즘을 적용할지 난해하여 시간복잡도를 개선하기위해 방법을 생각해놓고보니 에라토스였습니다. 임의의 카드를 하나 선택한 다음, 그 카드에 적힌 수의 배수를 탐색하면서 다른 플레이어의 카드 수가 존재한다면 승, 패를 확인할 수 있습니다. 이를 위해서 다른 플레이어의 카드의 수가 존재하는지를 판단하는 1'000'001 크기의 배열을 선언하였고, 있다면 그 플레이어의 인덱스 값을 저장해놓았습니다. [ 시간 복잡도 ] $$O( \sum_{i = 1}^{n}\frac{1000000}{card[i]} )$$ 입니다. 최악의 경우 n = 100'000이고, card[i] = i..

1. 문제 풀이 문제를 처음 읽었을 때, 그래프 자료구조에 간선이 하나씩 추가될 때마다 dfs를 통해 사이클을 탐지하는 naive 한 풀이 방법이 먼저 떠올랐습니다. 문제의 입력을 그래프 자료구조로 보게 되면 정점이 n개이고 간선이 m개인 그래프를 입력받는데 정점이 최대 500'000개이고 간선은 1'000'000개라 이러한 풀이 방법은 시간 내 정답을 구할 수 없다는 생각이 들었습니다. 생각의 발상으로 분리 집합(disjoint-set)을 구현하는 union-find 알고리즘을 사용하면 이 문제를 풀이할 수 있습니다. 두 선분을 잇는다를 두 점을 한 집합으로 union한다고 생각하시면 됩니다. 사이클을 탐지하는 방법은 이 union-find가 진행되는 과정을 그림으로 그려보시면 알 수 있는데 서로 같은..

1. 문제 풀이 lower_bound, 즉 이분 탐색을 사용하여 풀이하였습니다. 각 배열에 값이 증가하는 부분 수열에서 어느 위치에 존재하는가를 저장하는 방법을 통해 풀이할 수 있습니다. 증가하는 부분 수열은 항상 오름차순으로 정렬이 되어있기 때문에 lower_bound로 각 배열의 값이 위치할 수 있는 곳을 알아낼 수 있습니다. 만약, 부분 수열 내 값보다 배열의 값이 크다면 부분 수열의 크기를 증가하고 추가하면 되고 아니라면 해당 위치에 배열의 값을 삽입합니다. 그리고 배열의 값이 부분 수열에서 위치하는 인덱스 정보를 따로 저장하여 처리합니다. 모든 과정이 끝나게 되면 부분 수열의 길이가 LIS의 길이가 됩니다. 그리고 배열의 각 값마다 LIS에서 위치할 수 있는 정보를 바탕으로 역추적하여 LIS의 ..

1. 문제 풀이 비트마스킹을 활용한 다이나믹 프로그래밍을 사용하여 풀이하였습니다. dp 테이블은 다음과 같이 정의하였습니다. dp[i][j][k] : i자릿 숫자에서 마지막 자리의 숫자가 j이고 사용한 숫자가 1, 사용 안 한 숫자가 0인 비트필드 k 모든 계단 수를 구해주어야하는데 사용한 숫자 리스트에 대한 비트필드 k를 두어서 다이나믹 프로그래밍을 진행했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector v..

1. 문제 풀이 너비우선탐색을 사용해서 구현해야 하는 문제였습니다. 알파벳 대문자는 문을 의미하고 알파벳 소문자는 열쇠를 의미합니다. 그리고 탐색을 통해 얻거나 이미 가지고 있던 열쇠로 문을 열 수 있습니다. 따라서 문제의 요구사항은 두 가지로 함축할 수 있습니다. 1. 열쇠를 이용해서 문을 여는 방식2. 최대로 얻을 수 있는 문서가 몇 개인지 판별하는 방식 여기서, 우선 배열의 가장자리 부분을 통해 출입이 가능하다고 되어있으니 가장자리 중 들어갈 수 있는 위치 정보를 저장하게 했습니다. 주의할 점은 열쇠나 문서가 가장자리에 있어도 출입이 가능하다는 사실에 유의해야 합니다.  열쇠를 이용해서 문을 열기 위해서는 탐색을 통해 어떤 열쇠를 얻었는지 정보가 필요합니다. 그 열쇠정보를 통해 해당하는 문을 열 수..

1. 문제 풀이비트마스킹을 활용한 dynamic programming을 사용하여 풀이하였습니다. 비트필드는 어떤 정점을 방문했는지 아닌지를 판별하는 용도로 사용하였고 이에 따라 dp table은 [n][1 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector vtl;typedef ve..

1. 문제 풀이문제를 대충 읽고 풀었더니 정말 오래 걸렸습니다. 너비우선탐색을 진행하면서 각 칸에 대한 거리를 구하고 자신보다 큰 물고기가 있는 곳은 탐색할 수 없고 크기가 같은 물고기는 먹진 못하고 지나칠 순 있습니다. 그리고 자신보다 크기가 작은 물고기의 위치에 대해서 가장 짧은 거리에 위치하면서 여러 개일 경우 상단 좌측에 있는걸 우선순위로 구해줍니다.그렇게 구한 물고기의 위치가 갱신되지 않았다면 루프를 종료하시고, 갱신되었다면 너비우선탐색으로 구한 거리값을 더해주고 빈칸으로 만들어줍니다. 이때, 상어의 크기만큼 물고기를 먹었다면 상어의 크기를 1 증가시킨 다음 물고기의 위치로 상어의 위치를 옮기고 루프를 반복하시면 됩니다. 2. 코드 #include using namespace std;typede..