목록전체 글 (95)
서랍장
단순한 그래프 탐색을 진행하게 되면 바로 시간이 터지게 된다. 오른쪽위 → 오른쪽 → 오른쪽 아래 순으로 탐색을 하는 그리디 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..
생각보다 간단한 문제였다. N번째 큰 수를 찾아야하므로 크기가 N 초과가 되면 안되는 우선순위 큐를 선언한 다음에 하나씩 입력받다가 N 초과가 되는 경우 제일 작은 값을 뺴주어 N개를 유지시키는 식으로 쭉 입력받고 맨 마지막에 우선순위 큐에 있는 N개의 수 중에서 제일 작은 값이 N번째 큰 수가 된다. #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; priority_queue pq; int main() { int n, input; scanf("%d", &n); for (int i = 0; i n) { pq..
단순 탐색 문제인것 같다. 문자와 정수 pair 를 저장하는 vector 를 만든다. 그 후 문자열의 값을 하나씩 확인하면서 문자를 vector 에 넣되, 넣을 때 비교할 폭탄 문자열과 확인하여 같은 값이라면 몇번재 index 와 같은지를 정수로 같이 넣어준다. 이로써 폭탄이 만일 터지더라도 그 다음에 저장되어있는 정수를 확인해 계속해서 이어지는 문자가 들어올 시 폭탄이 터지도록 로직을 구현할 수 있다. 복잡도는 100만 * 36 + 36n? 정도? 라서 2초에 비해 넉넉한 복잡도를 가질 것이라 생각된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include..
#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; typedef pair pii; int n, cnt = 0, a, b; priority_queue pq; vector v; int main() { int n; long double a, b; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%Lf %Lf", &a, &b); v.push_back({ a, b }); } long double x1, y1, x2, y2, x3, y3; x1 = v[0].first; y1 = v[0].second; long d..
간단한 백트래킹을 사용한 구현 문제이다. 로직은 생각보다 간단하다. dfs 순회를 하면서 넣으려는 숫자가 행에 있는지 열에 있는지 박스에 있는지 3가지만 확인하면 된다. 이 때 각각을 전부 순회를 때리게 되면 각각 9번의 연산이 생기게 된다. 그렇게 되면 81번의 공간에 9개의 숫자를 확인하되 각각 27번의 check 연산을 하게 되어 복잡도에 큰 문제가 생기지 않는다고 판단된다. 허나 좀더 빠르게 연산하기 위해 해쉬를 두어 숫자를 체크하게 되면 메모리를 조금 더 두어 check 연산을 O(1) 만큼의 복잡도로 처리할 수 있게 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #..
전형적인 세그먼트 트리 문제이다. 일단 시간 제한이 2초이기 때문에 일일이 10만개의 정수 쌍 입력에 대해 10만개의 배열에서 최솟값과 최댓값을 뒤지게 되면 복잡도가 터지게 된다. 이를 위해 미리 답들을 트리 형태로 저장해놓는 세그먼트 트리를 사용하여 복잡도를 줄일 수 있다. 값을 저장할 때마다 최솟값과 최댓값을 log(n) 의 복잡도로 저장해놓는 식이다. 그 후 정수 쌍 입력을 받을 때마다 만들어 두었던 세그먼트 트리에 query를 날리는 식으로 문제를 풀게 되면 답이 금방 나오게 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include..