목록책장 (89)
서랍장
약간의 기술이 필요한 투 포인터 문제였다. 일단 기본적으로 5000의 입력값에 1초의 제한시간이기 때문에 O(N^2) 의 복잡도까지는 잘 통과할 것이다. O(N*NlogN) 까지도 가능할거라 생각한다. 여튼 3개의 용액을 골라야 하므로 N의 복잡도는 첫 시작 용액을 고르는 것에, 나머지 N은 투포인터 탐색으로 나머지 2개의 용액을 고르는 것에 사용하여 O(N^2)의 복잡도로 끝마무리 할 수 있다. 로직은 다음과 같다. 첫 번째 용액을 순서대로 선택한다. 고른 용액 이후의 용액들 중 2개의 용액을 투포인터 탐색을 통해 찾는다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #inclu..
전형적인 투포인터 문제이다. 10만의 입력값에 1초의 시간 제한을 보자마자 최소 O(NlogN)의 복잡도를 사용해야 한다는 것을 생각해야 한다. 또한 정렬이 되어있다는 조건을 본 후 이분탐색 또는 투포인터탐색을 떠올린 뒤 로직을 생각하면 된다. 이 문제의 경우 간단한 로직을 사용한다. lo, hi 를 양끝으로 잡은 뒤 값을 비교하며 투 포인터 탐색을 진행한다. 진행 시 계산한 값이 음수이면서 0에 가까운지 양수이면서 0에 가까운지 체크한다. 각 경우에 따라 lo를 증가시킬지 hi를 감소시킬지 정해주며 답을 찾아가면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include..
그래프 + dp 문제 이다. 이 문제를 풀기 이전에 dp와 dfs 를 같이 사용해서 생각하는 방법을 기를 수 있어야 한다. 일단 해당 문제는 top-down dp 방식으로 풀이할 수 있다. 예를 들어 7 부터 tree 를 순회한다고 할 때, 7번째 마을을 우수마을로 선정하는 경우 7번째 마을을 우수마을로 선정하지 않는 경우 2가지의 경우로 DP 상태를 선정할 수 있다. 또한 7번째 마을을 우수마을로 선정하기 위해서는 7번째 마을과 연결된 마을들이 선정되지 않는 경우를 알아야 하고, 7번째 마을을 우수마을로 선정하지 않기 위해서는 상관이 없다. 이를 이용해서 dp 로직을 구할 수 있다. 특정 마을이 선정되는 경우 = (자식 마을이 선정되지 않은 경우의 합) + 특정 마을의 인원수 특정 마을이 선정되지 않는..
좀 단순한 dfs 탐색 문제였다. 각 크기의 색종이의 개수를 배열에 저장해둔 다음, 해당 위치 부터 차례대로 5, 4, 3, 2, 1 크기의 색종이를 대조하고, 다음 노드를 탐색하는 로직만 구현하면 된다. 전체 배열의 크기가 10*10 로 크지 않으며, 색종이의 종류 역시 5개이므로 시간 제한은 매우 널널하다. #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; typedef long long LL; int arr..
간단한 탐색 문제이다. 바로 로직을 보면 다음과 같다. 입력받은 문자열을 알파벳 순으로 정렬해준다. 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..