어흥

문제 링크: https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 1. 주의할 점 - 값이 자주 변경 + 구간 합을 구해야 한다 → 세그먼트 트리 - TC가 여러개 → 사용하는 배열 초기화 필요 2. 구현 - TC가 여러개이므로 Tree[]와 Arr[] 배열을 적절히 초기화하고 시작한다 - 현재 디스크가 Num개 꽂혀있다 + M번의 이동을 수행한다 → 옮기는 디스크를 배열의 가장 뒤로 배치한다면? → 최소 N+M의 크기를 가지는 배열이 필요하..

문제 링크: https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 1. 주의할 점 - 세그먼트트리 혹은 펜윅트리에 대해 알고 있어야 한다 - 답의 경우, 구간합의 합이므로 LongLong으로 설정한다 2. 구현 - 서로 다른 두 선분이 만나서 생기는 교차점의 수를 구한다 → 첫째 행에서 둘째 행으로 선분을 잇는다 → 둘째행 기준 오른쪽에 이미 연결된 선분의 수만큼 교차한다 → 오른쪽에 연결된 선분의 수를 구간합으로 구한다 → 연결된 둘째행의 인덱..

문제 링크: https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 1. 주의할 점 - 분할정복 + 세그먼트 트리를 통해 해결한다 2. 구현 - 직사각형의 높이에 대한 정보를 Arr[] 배열에 담는다 - Tree[] 배열을 동적할당한다 - Init() 배열을 통해 Tree[] 배열에 최소 높이를 가지는 인덱스 번호를 저장한다 - findMinIdx() 함수를 통해 Left~Right까지의 Arr..

문제 링크: 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 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 - MOD 연산, 0으로 나누기를 유의해야 한다 2. 구현 - Num의 크기만큼 Arr[] 배열에 초기값을 입력 받는다 - Num을 통해 Height를 계산한 이후, Tree[] 배열을 동적할당한다 - Init() 함수를 통해 Tree[] 배열을 갱신한다 - 값이 ..

문제 링크: https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다(세그먼트 트리 ↔ 구간 합이라고 생각했던에서 벗어나게 해준 문제다) 2. 구현 - 모든 수들을 Arr[] 배열에 담는다 - 부모로 자식중에서 Max값을 지닐 maxTree[]와 Min값을 지닐 minTree[]를 생성한다. 이때, MinTree[]는 전부 MAX로 초기화하여 추후에 0만 나..

문제 링크: 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 1. 주의할 점 - 세그먼트 트리에 대해 알고있어야 한다 2. 구현 - Height을 통해 세그먼트 트리를 나타낼 Tree[] 배열의 크기를 설정한다 - 초기의 수를 Arr[] 배열에 입력받은 후, Init() 함수를 통해 Tree를 초기화한다 - Query수만큼 Sum()과 Update() 함수를 호출하며, X가 Y보다 클 수도 있으므로 Big, Sma..

문제 링크: www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 - 우선순위가 높은 사탕을 뽑을 방법은? 2. 구현 - Tree[]를 이용하여 세그먼트 트리를 구성한다. 이때, Tree의 크기는 사탕의 우선순위가 1~1000000이므로 N=1000000일때 완전이진트리의 높이를 구하고, 비트연산으로 배열의 메모리를 동적으로 할당한다 - Update() 함수를 통해 idx가 포함된 ..

문제 링크: www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 2. 구현 - Arr[] 배열을 통해 입력받는 수들을 저장한다(Index: 0~Num-1) - ceil(log2(Num))을 통해 Height을 구한다. Tree[] 배열을 만들 경우, Num보다 크거나 같은 2의 제곱수 중 가장 작은 제곱수*2만큼의 공간이 필요하기 때문이다. - ..