목록전체 글 (95)
서랍장
백트래킹 문제이다. 일단 2차원 위치를 하나의 num으로 두고 나머지와, 몫으로 좌표를 설정하도록 한다. 그 후 하나씩 돌아가면서 해당 수만 직사각형 종이에 포함할 것인가 해당 수의 아래를 직사각형 종이에 포함할 것인가 해당 수의 오른쪽을 직사각형 종이에 포함할 것인가 를 하나씩 처리해주면서 문제를 풀면 간단하다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; // 입력값이 100만 -> nlogn 으로 끝내야 한다. int arr[5][5]; int check[5][5]; int dx[] = { -1, 0 }; int dy[] ..
+-누적합 문제이다. 값의 변경을 일일이 배열에 체킹해주면 터지게 된다. 때문에 이를 +-누적합을 통해 구해줄 수 있다. ground : 첫 값이 들어가있는 배열 arr : "+ -" 체킹 배열 sum : 최종적으로 몇 만큼 변경해야하는지 들어있는 배열 #include using namespace std; typedef long long LL; int sum[100001]; int arr[100002]; int ground[100002]; int main() { int n, m, a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i
20만의 입력값에 대응하기 위해 nlogn 또는 n의 복잡도로 문제를 풀어야 한다. 이를 위해 누적합을 통해 문제를 풀 수 있다. 다만 전체 합에 대한 누적합과 각 색상에 대한 누적합을 따로 구하여 해당 값을 처리해주면 된다. 이를 2가지 방법으로 구현하였다. 각 색상에 대한 누적합을 구해놓고, 각각의 답을 구할 시에 이분탐색을 돌린다. 모든 명령어를 정렬한 뒤 색에 대한 누적합과 전체에 대한 누적합을 동시에 진행해준다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; typedef long long LL; typedef pair pii; LL input; LL arr[2001]; LL all_..
누적합과 조합 계산식이 필요한 문제다. 일단 입력값을 보면 100만임을 봐서 최소 O(NlogN) 의 복잡도 내로 끝내야 함을 알 수 있다. 허나 이 문제의 경우 각 누적합을 통해 O(N) 복잡도로 끝낼 수 있다. 로직은 다음과 같다. 입력되는 배열을 순서대로 sum 배열에 넣되 m으로 나눈 나머지 값을 쭉 넣어준다. sum 배열을 순회하면서 원소를 pai 배열에 체킹해준다. pai 배열에 체킹된 순서로 순회하면서 조합식을 더하면 답이 된다. 이렇게 pai 배열을 둔 이유는 sum[i] - sum[j] = 0 이 되는 경우의 수를 찾아야 하는데 결국 sum[i] == sum[j] 인 경우를 찾는 것과 다름이 없다. 따라서 같은 값을 가지는 sum 배열의 원소들을 쭉 체킹해준 다음 nC2의 조합식에 따라 ..
구간합을 구하는 간단한 문제였다. 세그먼트 트리 나 누적합 으로 풀면 간단하게 풀린다. 누적합 로직은 다음과 같다. (a~b)의 합 = b까지의 합 - (a-1)까지의 합 코드는 두가지 버전으로 작성해보았다. // 세그먼트 트리 로직 #include using namespace std; typedef long long LL; LL tree[300000]; LL query(int node, int s, int e, int l, int r) { if (e < l || r < s) return 0; if (l
카카오 6번 효율성 에 대해 검색하던 중 찾은 누적합 문제이다. 비슷하게 좌표를 통해 2차원 DP로 푸는 문제이다. 로직은 다음과 같다. (i,j) 까지의 누적합 = (i,j)의 값 + (i-1,j)까지의 누적합 + (i,j-1)까지의 누적합 - (i-1,j-1) 까지의 누적합 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define MAX_NUM 1000000009 using namespace std; typedef long long LL; typedef pair pii; int arr[1300][1301]; int main() { int row, col, a;..
약간의 기술이 필요한 투 포인터 문제였다. 일단 기본적으로 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..