목록책장/알고리즘 (57)
서랍장
전형적인 BFS 문제이다. 단순히 길만 따라서 check 배열에 메모 후 탐색, 메모 후 탐색 의 로직으로 문제를 풀게 되면 틀리게 된다. 탐색하는 경우의 수가 사실 2배 더 많기 때문이다. 칼이 있는지, 없는지에 대한 경우를 생각해야 하기 때문에 2배이다. 예를 들어 (2,3) 위치에 이동할 때, 칼을 가진 상태로 이동하는 것과 칼을 가지지 않은 상태로 이동하는 것은 명백히 다른 경우의 수이다. 떄문에 이 두 가지 경우를 다르게 봐야하고 그에 따라 check배열 또한 3차원 배열로 만들어주어야 한다. 그 후에는 다음 코드와 같이 단순히 BFS 탐색을 때리면 끝! #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #i..
모든 경우이 수를 다 보는 것은 1초의 제한시간과 30만의 입력값을 보았을 때 당연히 되지 않는구나~ 라고 느껴야 한다. 때문에 뭔가 다른 방법을 생각해야 한다. 이 문제의 경우는 인접한 수끼리의 차를 정렬한 뒤 N-K 만큼 앞부터 원소를 고르는 식으로 집합을 생각하면 간단하다. 이와 같이 구현만 하면 문제는 간단히 풀린다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long LL; deque arr; int main() { ios_base::sync_with_stdio(false); cin.tie(NU..
경우를 잘 나눠야 하는 문제이다. 일단 문제의 시간제한 1초를 봤을 때 10만의 입력값으로 통과하기 위해서는 답은 O(Nlog(N)) 의 시간 제한으로 풀 수 있어야 한다. 때문에 이분탐색, 세그먼트 트리 등등의 알고리즘을 떠올릴 수 있다. 이 문제의 경우에는 다른 자료구조가 필요한 것이 아니라 전체 경우가 최대값을 가지기 위해서는 특정 경우로 나뉜다 정도만 알면 풀 수 있다. 전체 최대값을 가질 수 있는 경우는 다음과 같다. "벌꿀 - 벌 - 벌" 순서로 있는 경우 "벌 - 벌 - 벌꿀" 순서로 있는 경우 "벌 - 벌꿀 - 벌" 순서로 있는 경우 각 경우마다 왼쪽 끝, 오른쪽 끝에 위치해야하고, 중간 특정 지점이 위치해야 한다. 위 3가지 경우에 대해 값을 다 확인하며 최대값을 구할 때 O(N) 의 복..
heap 2개를 가지고 Nlog(N) 의 시간 내로 중앙값을 뽑아내는 로직을 사용하면 쉽게 풀린다. heap 2개는 다음과 같다. 절반의 작은 값들을 저장하는 max heap 절반의 큰 값들을 저장하는 min heap 이 때 min heap 이 max heap 크기 이상의 특징을 계속 가지도록 한다면 홀 수 개의 값이 입력되었을 때 min heap 의 top 을 출력하도록 하면 쉽게 풀린다. 예를 들어 입력되는 수가 1, 5, 4, 3, 2 라고 해보자. 1 이 들어오게 되면 먼저 min heap 에 넣는다. 그 후 5가 들어오면 size 가 작은 max heap 에 넣는다. 넣은 후 max heap 의 top과 min heap의 top 을 비교해서 max heap 의 것이 더 크다면 서로 top 을 s..
시간 복잡도가 1초이고, 입력값이 10만개, query 의 값이 만개 이므로 각 query 마다 log(N) 의 복잡도 내로 답이 나오도록 처리해야 문제가 풀리게 된다. 이를 위해 입력 시에만 Nlog(N) 의 복잡도가 걸리고 query 에 따른 값을 뽑아 낼 때는 log(N) 의 복잡도를 가지는 min heap, max heap 2개와 solved 된 문제를 체킹하기 위한 배열 1개가 잇으면 간단히 풀리게 된다. 단, solved 된 문제를 체킹할 때 해당 문제의 난이도를 배열에 저장함으로써 이 후 top 의 값이 체킹해두었던 난이도가 아니라면 pop 하고 다음 수를 보는 로직을 통해 문제를 해결할 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include #i..
단순한 그래프 탐색을 진행하게 되면 바로 시간이 터지게 된다. 오른쪽위 → 오른쪽 → 오른쪽 아래 순으로 탐색을 하는 그리디 1, 빵집의 가스관 위쪽부터 차례대로 파이프를 연결할 수 있나? 없나? 를 확인하며 파이프를 만드는 방식의 그리디 2 총 2개의 2그리디 방식을 사용해야 한다. 첫 번째 그리디의 경우 어찌저찌 잘 생각할 수 있겠지만, 두 번째 그리디의 경우에는 생각하기 어려워서.. 매우 오랜 시간이 걸린 문제이다. 로직은 다음과 같다. 빵집의 가스관 위쪽 부터 dfs 탐색을 돌며 파이프를 만들 수 있는지 확인한다. ( 만들 수 있으면 response 에 +1, 없으면 +0 을 해준다. ) 그리디만 알면 생각보다 간단한 문제이나 생각하기 힘들다... #define _CRT_SECURE_NO_WARN..
시간 복잡도가 중요한 문제이다. 일단 제한 시간을 보면 10초인 것을 볼 수 있다. 허나 입력값이 100개인 배열에서 일일이 다 비숍을 넣어가면서 백트래킹을 하게 된다면 O(2^(10*10)) 이 되어 터져버리게 된다. 이를 위해 체스판의 특징을 생각해 흑,백 으로 나눠 로직을 짜보려고 한다. 이렇게 되면 복잡도가 O(2^(5*5)) 가 되어 문제 없이 제한시간을 맞추게 된다. 분할해서 생각한다면 로직은 일반 백트래킹과 다를바 없어 넘어가도록 하겠다. 다만 흑,백으로 나누어 check 배열을 두고 확인하는 로직만 유심히 보면 될것 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using na..
DP 에 비트마스킹까지 포함시킨 문제이다. 일단 수를 일일이 다 확인해가면서 0부터 9까지 있는지 확인하는 작업은 복잡도 측면에서 몇십배 정도 더 늘어나게 된다. 때문에 이를 위해 비트마스킹 기법을 통한 체킹 로직이 필요하다. 추가로 DP 메모라이징 기법을 통해 이 문제를 비교적 간단하게 풀 수 있다. 처음에만 봤을 때 어렵지 한 번 이해하면 다음에는 쉽지(??!) 않을까 생각하는 문제이다. 다음에 한 번 더 풀어보는 걸로.. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long LL; int N; int..
구현 + DFS 문제였다. 네트워크 개수를 세는 듯한 문제인데 입력받은 U, D, L, R 에 따라 쭉~ 이어주는 동시에 다음 값이 현재 있는 값으로 들어올수도 있는지 확인하는 로직을 구현하면 간단한 문제였다. 다시 로직을 정리하면 다음과 같다. 지도 (0,0) 부터 check 되어있지 않으면 dfs 로 해당 지점으로부터 연결되어있는 모든 지도지점을 check SAFE ZONE 개수 한개 추가 그 후 check 안되어있는 지점으로부터 dfs 처리해서 똑같이 네트워크 check SAFE ZONE 한개 추가 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; typedef pair pi..
단순 BFS 를 사용하면 100만 + 300만 정도의 복잡도가 나오게 되어서 전혀 복잡도가 터질 일이 없다. 따라서 BFS 를 따라 로직만 잘 처리해주면 된다. 로직은 다음과 같다. 처음 입력된 수와 비어있는 문자열을 queue 에 넣는다. 이 후 queue 의 front 를 빼고 3가지 연산 각각을 할 수 잇는지 확인하고 연산이 가능하면 연산된 값을 다시 queue 에 넣고 해당 숫자를 더한 문자열또한 queue 에 넣는다. 위의 과정을 1이 나올 떄까지 반복한다. 생각보다 간단한 알고리즘이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; typedef pair pii; i..