꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2263 직접 트리를 그려본 다음에 유도를 해보는 것이 제일 적절한 해법인 것 같습니다. 후위 순회를 기준으로 생각해보면 맨 마지막에 위치한 노드가 해당 트리의 루트입니다.그리고 중위 순회를 기준으로 생각해보면 루트가 나오기 전까지는 왼쪽 부분트리이고 나온 후에는 오른쪽 부분트리입니다.따라서, 이 성질을 이용해서 재귀함수를 호출하면 AC를 받을 수 있습니다. #include using namespace std; const int MAX = 100000 + 1; int inOrder[MAX], postOrder[MAX]; int idx[MAX]; void preOrder(int inBegin, int inEnd, int postBe..

문제 링크입니다: https://www.acmicpc.net/problem/11778 N, M이 매우 크기 때문에 시간복잡도 O(N)으로는 어림도 없는 문제였습니다.https://jaimemin.tistory.com/324?category=987849 이 문제를 보면 행렬의 곱셈을 통해 피보나치 수열을 구할 수 있는 것을 알 수 있습니다.따라서, 분할정복을 이용해 행렬의 N승을 빨리 구하는 것이 핵심이였습니다.이 때, 행렬의 곱셈을 진행할 때, int 범위를 안 벗어나도록 모듈라 연산을 적절히 하는 것 또한 핵심이였습니다. #include using namespace std; const int MOD = 1000000007; //행렬의 성질을 이용하여 피보나치 수열을 구함 class Matrix { in..

문제 링크입니다: https://www.acmicpc.net/problem/11997 kks227님이 친절하게 좌표 압축 기법을 설명해주셨기 때문에 풀 수 있었던 문제였습니다.또한 같은 학교 학우인 degurii가 부연 설명해줬기 때문에 AC를 받을 수 있었습니다. 알고리즘은 아래와 같습니다.1. 소가 위치할 수 있는 범위가 1,000,000 * 1,000,000이므로 이차원 배열로는 표현할 수 없습니다.2. 따라서, 좌표 해쉬 맵과 이진 탐색 트리(set)을 이용하여 좌표를 오름차순으로 압축합니다.3. 좌표를 압축한 순서대로 전처리를 진행합니다.4. 울타리를 모든 가능한 구간에 세워보고 사분면에 있는 소의 최대 수가 최소가 되는 지점을 업데이트합니다. #include #include #include #..

문제 링크입니다: https://www.acmicpc.net/problem/3273 배열을 오름차순으로 정렬한 뒤 이분 탐색을 통해 두 수의 쌍을 구해주면 되는 문제였습니다.'쌍'을 구해야하기 때문에 구한 값을 반으로 나눈 뒤 출력해주는 것이 핵심이였습니다. #include #include using namespace std; const int MAX = 100000; int arr[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, X; cin >> N; for (int i = 0; i > arr[i]; cin >> X; sort(arr, arr + N); int result = 0; for (int..

문제 링크입니다: https://www.acmicpc.net/problem/16723 N의 최대 범위가 1,000,000,000 즉, 10억이기 때문에 완전탐색법으로 접근하면 TLE가 발생하는 문제였습니다.그래서 참가자들을 다 나열해보고 규칙을 찾아보도록 하겠습니다. $$2 + 4 + 6 + 8 + 10 + 12 + 14 + ... + 2 * N$$$$2 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N) $$$$2 * (1 + 3 + 5 + 7 + ... + 2 * (1 + 2 + 3 + 4 + 5+...))$$$$2 * (1 + 3 + 5 + 7 + ... + 2 * (1 + 3 + 5 + ... + 2*(1 + 2 + 3 + ...)))$$ 이로써 규칙을 찾았고 반복문을 이용해서..

문제 링크입니다: https://www.acmicpc.net/problem/6523 조세퍼스 문제를 변형시킨 문제였습니다. 알고리즘은 아래와 같습니다.1. 두 번 걸린 사람이 나올 때까지 while문을 돌리고 map에 이 사람이 몇 번째인지 표시해줍니다.2. 1번을 마치면 정답을 알 수 있는데 N명 중에 cnt명이 지목을 당했었고 그 중 drinker[cur] 즉, 제일 처음으로 술을 마시게 된 사람이 몇 번째로 지목을 당했었는지 알기 때문에 답은 N - cnt + drinker[cur]입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); while (1) { long lon..

문제 링크입니다: https://www.acmicpc.net/problem/1168 Algospot JOSEPHUS(https://jaimemin.tistory.com/554)와 동일한 문제였습니다. 시간 복잡도를 단축시키기 위해 (M - 1)번 포인터를 옮기는 대신 모듈러 연산을 통해 포인터를 옮겼습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; vector v; for (int i = 1; i

문제 링크입니다: https://www.acmicpc.net/problem/16507 백준 11660번 구간 합 구하기 5(https://jaimemin.tistory.com/1144)를 살짝 응용한 문제입니다. 링크의 그림을 보면 코드가 금방 이해가 될 것입니다! #include using namespace std; const int MAX = 1000 + 1; long long pSum[MAX][MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int R, C, Q; cin >> R >> C >> Q; for(int i=0; i > num; ..

문제 링크입니다: https://www.acmicpc.net/problem/10986 Algospot CHRISTMAS(https://jaimemin.tistory.com/487) 문제의 첫 번째 부분문제와 똑같은 문제였습니다. 알고리즘은 아래와 같습니다.1. 부분합을 구할 때 M에 대해 모듈러 연산을 한 값을 저장하고 해당 값이 몇 번 나왔는지 기록합니다.2. 해당 부분합의 모듈러 연산의 결과가 0이라면 M에 나누어떨어지므로 결과에 더해줍니다.3. 같은 나머지가 나온 구간의 부분합은 M에 나누어떨어지므로 (해당 나머지가 나온 횟수)C2 를 구해주고 결과에 더해줍니다.$$_{(해당 나머지가 나온 횟수)}C_2$$ #include #include using namespace std; const int MA..

문제 링크입니다: https://www.acmicpc.net/problem/10211 간단한 부분합 문제였는데 주의할 점은 길이가 1인 즉, 원소가 하나인 부분합도 고려해야합니다! #include #include #include using namespace std; const int MAX = 1000 + 1; int pSum[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int t = 0; t > N; for (int i = 1; i > num; pSum[i] = pSum[i - 1] + num; } int result = INT_MIN; for (in..