목록분류 전체보기 (95)
서랍장
간단한 탐색 문제이다. 바로 로직을 보면 다음과 같다. 입력받은 문자열을 알파벳 순으로 정렬해준다. map 을 두어 이미 체크한 문자열을 탐색하지 않도록 설정해준다. 그 후 문자열의 idx 에 대해 check 해주며 브루트 포스 탐색을 실시한다. 이러면 그냥 답이 나온다... 간단~ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii; typedef tuple tiii; int arr[100001]; int check[100001]; int visit..
트릭이 필요한 탐색 문제였다. 일단 기존 DFS 를 사용해서 단순하게 check 하며 탐색한다. 이 때 cycle 이 생기는 경우 해당 cycle 에 포함되지 않는 노드의 개수를 구하기 때문에 visit 배열을 하나 더 만든다. 그 후 다음과 같은 규칙을 세운다. check는 color 로 칠하되 다른 컬러의 check 를 만났다면 그건 이미 만들어진 cycle 이므로 해당 color 구축시에는 cycle 노드 개수가 0이다. (0 return) check 가 0으로 되어있어 순회하는 경우 visit 배열에 몇 개의 노드를 탐색 중인지 메모해놓는다. check 가 color 로 칠해져있는 노드에 다시 한번 더 접근한 경우 해당 color 단계에서 cycle 이 발생했다는 것이다. 이 때 visit 에 저..
시간 제한은 1초에 테스크 케이스의 개수가 1000개이니 각 테스트 케이스마다 최소 10만 이내의 복잡도로 끝내야 하는 문제이다. 이때 수가 20000까지의 수이기 때문에 반복문 2개를 놓는순간 제한에 걸리게 된다. 이 문제는 조건과 나머지의 규칙을 통해 풀 수 있다. 다음 식들을 쭉보자 10 = (1 * 7) + 3 100 = (10 * 7) + 30 101 = (10 * 7) + 31 ...... 이 식들을 보았을 때 나누게 되는 수가 10곱만큼 늘어나게 되면 나머지 역시 10곱만큼 늘어나게 된다. 또한 나누게 되는 수가 1만큼 늘어나게 되면 나머지 역시 1만큼 늘어나게 된다. 이를 이용해서 string, int 값을 queue 에 넣어가면서 나머지가 0이 될 때까지 탐색을 돌릴 수 있다. #defi..
약간의 테크닉이 필요한 탐색 문제였다. 예전에 바이러스 관련해서 비슷한 문제를 푼거 같긴한데 로직은 다음과 같다. 불 위치에서 BFS 탐색을 시작해 번지는 시간대를 check 배열에 메모 메모된 check 배열에 따라 지훈이의 위치에서 탐색을 시작 양 모서리 지점까지 도달했으면 탈출한 것으로 체크 딱 봤을 때는 간단한데 1번과 2번을 연동시키는게 좀 생각하기 어렵다. 허나 여러번 풀어보면 간단해보이니 계속 풀어대자 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii;..
단순한 탐색 문제였다. 직사각형의 범위에 벽이 있나없나만 체크하며 queue 에 넣어주면서 탐색을 진행하면 풀리는 단순한 문제였다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii; struct Square { int x, y; int tm; }; Square initSquare(int _x, int _y, int _tm) { Square tp; tp.x = _x; tp.y = _y; tp.tm = _tm; return tp; } int arr[1001][1001]; int ch..
전형적인 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..