Doby's Lab

https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 이번 문제에서 저번 수열과 쿼리 15에서 실수했던 update arr[0] = INF;를 쿼리에서 사용하면 된다. (수열과 쿼리 15 포스팅: https://draw-code-boy.tistory.com/176) #define INF (1000000000 + 1) arr[0] = INF; int query(int st..

https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 이번 문제는 두 개의 포인트가 있었다. 1~n까지 중 최솟값을 찾는 거라 따로 쿼리 함수가 필요 없다. 배열의 인덱스를 노드에 담아야 한다. 처음에는 배열의 인덱스를 어떻게 반환할까 생각하다가 그냥 함수 하나 만들었다. ll compareMIN(ll a, ll b) { if (arr[a] == arr[b]) return min(a, b); r..

https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 이번 문제는 테스트 케이스가 몇 개인지 제한이 없고, 몇 개인지 주어지지도 않아서 이 부분을 참고해야 했다. while (cin >> n >> k) { // 입력이 계속 들어오는 동안 (?) // 코드 } 이 부분에 집중하느라 50%에서 계속 틀렸어서 입력 부분이 문제인 걸까 생각해봤지만 조금만 생각했다면 이유를 찾을 수 있었다. 우선 이번 세그먼트 트리에서 나는 구간 곱을 넣으려 했었다. 하..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 구간합 세그먼트 트리 문제였다. 이번 문제를 토대로 조금씩 세그먼트 트리에 대한 감이 잡히고 있다. 쿼리 선, 업데이트 후 방식으로 진행해주면 된다. x > y 인경우 swap 해주는 거 잊지 않기. #include #define MAX (100000 + 1) #define ll long long using namespace std; ll arr[MAX]; ll sg..

https://www.acmicpc.net/problem/1325 > 사실 이유는 2번이다. 하지만, 접근했던 방법이 1~2번이라 적어보았다. 여담이지만 다익스트라로 돌렸다가 시간 초과가 나왔어서 알게 된 방법이다. [1. 배열의 크기가 너무 크다.] 배열의 크기가 너무 커서 기존의 BFS가 1~N까지 연결되어있나 확인하는 게 메모리 초과를 유발한다고 생각했다. (그럴 수도 있겠지만 방문 체크를 하지 않아서다.) while (!q.empty()) { int front = q.front(); q.pop(); for (int i = 1; i > n >> m; int a, b; for (int i = 0; i > a >> b; map[b].push_back(a); } vector..

https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 이번 문제는 구간 합 lazy propagation을 조금만 응용하면 풀릴 줄 알았다. 하지만, 이 문제는 세그먼트 트리와 lazy propagation을 정확히 꿰뚫고 있어야 풀리는 문제다. 맨 처음에 떠올린 방법은 leaf노드에 도달하면 leaf노드가 0이면 1, 1이면 0의 방식으로 전환을 해주고, 업데이트를 하면 될 거라고 생각했다. 이렇게 되면 따져..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 앞선 세그먼트 트리 정리에서 구간 업데이트를 할 때는 Lazy Propagation을 통해 O(logN)으로 구현할 수 있다고 했다. 물론 구간합 함수를 참고하여 구간 업데이트를 할 수 있지만 이는 O(NlogN)으로 시간 초과가 난다. Lazy Propagation에 대해서는 다음 블로그를 참고하여 공부했다. (https://ya..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이번 문제는 어떤 인덱스를 입력받은 값으로 바꿔주는 update가 많이 헷갈렸다. 세그먼트 트리 초기화 함수, 구간 곱 구하기 함수 같은 경우는 구간 합을 참고하여 구현할 수 있었지만 update부분은 구간 합 부분을 참고하면 오류가 난다. [구간 합 업데이트] void update(int start, int end, int node,..