출항사

N개의 u, v가 주어진다. 구하고 싶은 값은 K인데 i uj, vi < vj를 만족하는 K를 구해야 한다. K를 기준으로 생각해보자. K의 왼쪽과 오른쪽을 기준으로 가장 큰값과 가장 작은 값들만 전처리 해놓는다면, O(1)에 K가 조건을 만족하는지 알 수 있을 것이다. 왜냐면 결국 왼쪽에서 가장 큰값이 오른쪽에서 가장 작은값보다 클때 무조건 정답이 될 수 있기 때문이다. 그래서 O(N) 탐색 두번을 통해 왼쪽, 오른쪽을 기준으로 최소 최대값을 전처리하고, 전처리한 값을 기준으로 K를 찾으면 된다. 시간복잡도는 O(N)이 소요된다. #include #define MINF 0x7f7f7f7f #define INF 2000000000 #define MOD 10007 #d..

문제를 해석하니 Set + 오프라인 쿼리 + 유니온 파인드 세 가지 기법을 활용하면 무조건 정답을 구할 수 있다는 풀이가 나왔다. 우선 모든 간선을 끊어주자. 그리고 쿼리를 뒤에서부터 수행하면서 노드를 하나씩 연결해 주자. 이때 부모 노드를 찾아줘야 하는데, 부모 노드에서 K개의 색깔을 얻을 수 있다면 해당 집합에 속한 모든 노드는 K개의 색을 얻을 수 있다. 부모 노드를 찾기 위해서는 유니온 파인드 알고리즘을 사용하면 된다. 그리고 색을 중복되지 않게 세줘야 하기 때문에 set으로 관리해 주자. 하지만, 여전히 문제가 있다. 자식 노드와 부모 노드가 merge 될 때, 자식 노드에 들어있는 색을 부모로 모두 옮겨야 하는데, 이 작업을 수행하는 시간 복잡도는 O(NlogN)이고, 최대 N번 수행되므로 최..

각 노드간의 거리가 주어졌을때, A -> B로 이동하는 최소 시간이 C보다 작거나 같은지 확인하는 문제이다. 노드의 개수가 500개, 쿼리의 개수가 1만개이다. 노드의 개수를 N, 쿼리의 개수를 K라고 하자. 그렇다면 간선의 개수는 N^2개가 되는 것을 알 수 있다. 쿼리가 들어올때마다 다익스트라를 돌리면 O(KN^2 log N)의 시간복잡도가 소요되기에 시간안에 문제를 해결할 수 없다. 따라서 N이 작은 것을 이용하면 되는데, 플로이드 와샬을 사용하면 된다는 것을 눈치챌 수 있다. O(N^3)에 모든 노드간의 거리를 전처리 해놓는다면 쿼리를 해결하는데 O(1)의 시간복잡도가 걸린다. 따라서 O(N^3)에 문제를 해결할 수 있다. #include #define MINF 0x7f7f7f7f #define ..

동전 2개가 주어질때, 하나의 동전만 떨어뜨리도록 적절히 움직이라고 한다. 최대 움직일 수 있는 횟수가 10회인점에 집중해보자. 매번 움직일 수 있는 경우의 수는 최대 4회이다. 따라서 4^10번의 경우의 수를 전부 돌려 동전 중 하나만 밖으로 나가는 경우가 존재하는지 확인하면 된다. 움직인 방향을 vector로 관리하고, 이 vector에 들어있는 방향으로 시뮬레이션을 돌려 움직여보자. 이때 하나의 동전만 밖으로 나가는 값을 찾으면 된다. 4^10번 만큼 경우의 수를 찾고, 시뮬레이션을 돌리는 최대 움직임이 10회이므로, 시간복잡도 O(4^10 * 10)에 문제를 해결할 수 있다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #define MOD ..

문제는 길지만 간단하게 해결할 수 있는 시뮬레이션 문제이다. 4개의 톱니바퀴가 주어지고, 특정 톱니바퀴를 회전시킬 때, 양옆에 존재하는 톱니바퀴에 영향을 준다고 한다. 회전을 모두 수행했을 때 최종 상태를 맞추면 되는 문제이다. 톱니바퀴는 시계 방향, 반시계 방향으로 회전할 수 있다. 따라서 덱 자료구조로 톱니바퀴를 구현해주면 아주 간단하게 양쪽 방향의 회전을 구할 수 있다. 그다음은 쿼리가 들어올때마다 회전시키기만 하면 된다. 초록색으로 표시된 값들이 무엇인지가 중요하기에, 이를 기준으로 비교해 주고 회전의 영향을 퍼뜨려주면 된다. 주의해야 할 점은 각 톱니바퀴가 회전할 것인지, 한다면 어느 방향인지 모두 표시를 해놓은 후 한 번에 회전을 해야 한다는 점이다. 순차적으로 회전시키면 비교할 때 잘못된 계..

간단한 다이나믹 프로그래밍 문제이다. 각 도시별로 [ 홍보 비용, 고객의 수 ] 정보가 주어진다. 이때 최소 C명을 모으기 위해 필요한 최소 비용을 구하라고 한다. 단, 도시별로 여러번 홍보할 수 있다. DP[i][j] = i번째 도시까지 j명을 모으기 위한 최소 홍보 비용이라고 정의하자. 그러면 점화식을 도출할 수 있는데, j가 i번째 사람의 고객의 수보다 크거나 같을때 DP[i][j] = DP[i][j-고객의 수] + 홍보 비용이 된다. 그리고 j가 i번째 사람의 고객의 수보다 작다면, DP[i][j] = DP[i-1][j]가 된다. 이를 2중 for문으로 구해주면 된다. 주의 해야할점은 '최소한 C명'이 되는 비용을 구하는 것이다. 따라서 j의 범위는 최댓값인 1100까지 잡고 점화식을 돌려야 한다..

정말 간단한 그래프 탐색 문제이다. 나를 기준으로 친구들과는 적대적인 관계이지만, 친구의 친구와는 우호 관계라고 한다. 이를 만족하는 그래프인지 확인해야 하는데, 그래프가 순환하는 형태인지 확인하면 된다. 왜냐면 트리 구조일 경우에는 무조건적으로 위의 조건을 만족하기 때문이다. 자 그럼 그래프가 순환하는지 확인해보자. 현재 노드와 연결된 노드 중 이전에 방문한 적이 있음에도 나와 우호적인 관계로 표시된 노드가 있다면 그래프가 순환하는 상태라고 판단할 수 있다. 그래서 boolean 변수를 하나 두고, dfs 탐색에 조건문 하나를 추가해 이를 판별하도록 구현했다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #define MOD 1000000009 #..

이분탐색 + 우선순위 큐 자료구조를 사용해야하는 문제이다. N개의 재료중 Oi가 1인 재료 K개를 제외했을때, 세균의 합이 G이하라면 먹을 수 있다. 이때 최대 유통기한을 얼마나 만들 수 있을까? 문제를 보자마자 이분탐색인걸 파악했다. mid로 날짜를 대입해보면서 만족하는 최대 mid를 구하면 되겠다 싶었다. 그러면 K개를 어떻게 선정할까? 그리디하게 생각해보고 싶지만, Si * max(1, x - Li)를 항상 보장할 수는 없다. 그래서 우선순위 큐에 현재까지 뽑은 재료 K개를 유지하도록 접근해봤다. mid를 이용해 모든 세균의 합을 구하고, 마지막에 우선순위 큐에서 K개의 재료로 인해 발생한 세균을 빼주면 간단하게 구할 수 있다. 날짜는 최대 20억이 가능하므로 left = 1, right = 2e9..