본문 바로가기

알고리즘/BAEKJOON88

BOJ 2042 : 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List 이전 글에서는 tree의 크기를 넉넉하게 잡았다. 구간의 길이가 100만이기 때문에 실제로는 2배 정도의 크기만 있으면 된다. 여기서는 필요한 만큼만 적절히 잡아서 다이나믹하게 트리를 만들어보자. 배열의 index를 이용하는 방법 원래 update 코드는 아래와 같다. void update(int left, int right, int node, int index, ll value) { if (inde.. 2023. 2. 8.

BOJ 13545 : 수열과 쿼리 0 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13545 참고 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort - BOJ 10866 : 덱 with Linked List - BOJ 13546 : 수열과 쿼리 4 수열과 쿼리 4에서 구해야하는 값은 아래와 같다. ● l r : max{|x - y| : l ≤ x, y ≤ r and Ax = Ay} 를 출력한다. 즉, 구간 [left, right]에서 같은 원소가 있는 경우 그 원소의 index의 차이가 가장 큰 값이다. 수열과 쿼리 0에서는 [left, right]에서 부분 수열 중 합이 0인 가장 긴 부분 수열의 길이를 구해야 한다. .. 2023. 2. 7.

BOJ 13546 : 수열과 쿼리 4 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13546 참고 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort - BOJ 13547 : 수열과 쿼리 5 - BOJ 10866 : 덱 with Linked List 수열과 쿼리 5에서 사용한 방법으로 문제를 푼다. 여기서는 주어진 구간 [left, right]에서 값이 같은 원소의 index의 차이를 구한다. 제곱근 분할법으로 원소의 길이 저장하기 [left, right]를 Mo's로 한 칸씩 움직이면서 각 원소마다 가장 긴 길이를 갱신하면 된다. 예를 들어 5번 원소가 7번 구간에 존재하고, 이 원소가 추가된다면, 5번 덱에 index .. 2023. 2. 7.

BOJ 10866 : 덱 with Linked List 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10866 참고 - BOJ 10866 : 덱 - 메모리 풀 Memory Pool - 링크드 리스트 Linked List - 링크드 리스트 Linked List Tail ver - BOJ 13546 : 수열과 쿼리 4 배열로 구현했던 덱(deque)을 링크드 리스트를 이용해서 구현해보자. 구조체를 이용하여 DEQUE을 아래와 같이 정의한다. 값을 저장할 value와 앞과 뒤를 연결할 포인터를 선언한다. 그리고 최초로 사용할 deque와 front, back 포인터를 선언하고 메모리 풀을 적절히 잡는다. typedef struct st { int value; struct st* next; struct st* prev; }DEQUE; DEQU.. 2023. 2. 7.

BOJ 13547 : 수열과 쿼리 5 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13547 참고 - BOJ 2531, 15961 : 회전 초밥 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort 원소의 개수 세기 구간에 업데이트가 없다면, 모스(Mo's) 알고리즘을 이용해 쿼리를 처리할 수 있다. 만약에 [left, right] 구간에 대한 답을 알고 있다면, [left, right ± 1]이나 [left ± 1, right]의 쿼리는 쉽게 처리할 수 있다. 즉, 이미 답을 구한 구간을 최대한 효율적으로 활용하는 방법이다. 위 문제는 회전 초밥에서 슬라이딩 윈도우를 사용했던 방법으로 원소의 개수를 셀 수 있다. 원소가 1.. 2023. 2. 7.

BOJ 8983 : 사냥꾼 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/8983 참고 - 머지 소트 Merge Sort 어떤 동물이 사대에서 잡을 수 있는 동물이라면, 이 동물을 기준으로 가장 가까운 사대만 확인하면 된다. 즉, 동물을 기준으로 왼쪽과 오른쪽 사대에 대해서만 거리를 계산해 L과 비교하면 된다. 왼쪽과 오른쪽 사대가 동물을 사냥할 수 없다면, 다른 사대는 더 멀리 있으므로 검사할 필요가 없다. 사대의 좌표(= x)를 작은 순으로 정렬하고, 동물도 x 좌표를 기준으로 정렬한다. 모두 정렬했으니, 사대의 좌표가 animal보다 가장 가깝게 작은 곳을 찾을 수 있다. while (index != M - 1 && place[index + 1] 2023. 1. 25.

BOJ 2751 : 수 정렬하기 2 with 계수 정렬 (Counting Sort) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2751 주어지는 숫자가 -1,000,000 ~ 1,000,000이기 때문에 0 ~ 2,000,000으로 바꾼다. 그리고 a[0 ~ 2,000,000]에는 각 원소의 개수를 증가시키고, 출력할 때는 작은 값부터 원소의 개수만큼 출력하고 다음으로 넘어간다. #include #define MINUS (1000000) int N; int a[1000000 + MINUS + 1000]; int main(void) { scanf("%d", &N); for (int i = 0; i < N; i++) { int tmp; scanf("%d", &tmp); a[tmp + MINUS]++; } for (int i = 0; i 2023. 1. 22.

BOJ 6549 : 히스토그램에서 가장 큰 직사각형 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/6549 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 문제의 예시대로 사각형을 그려보자. 전체 구간 [1 ~ 7]을 포함하는 가장 큰 직사각형의 넓이는 7이다. 예를 들어 구간 [6 ~ 7]만 포함하는 가장 큰 직사각형의 넓이는 6이 된다. 이 넓이는 어떻게 구할 수 있을까? 구간 [a ~ b]에서 가장 작은 높이와 (b - a + 1)을 곱하면 된다. 그리고 구간 [a ~ b]에서 가장 작은 높이의 index가 c라면 구간 [a ~ c - .. 2023. 1. 20.

BOJ 3653 : 영화 수집 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/3653 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) 6개의 영화가 있고 최대 M = 10번 영화를 본다고 가정하자. 그러면 세그먼트 트리를 아래와 같이 만들 수 있다. 마지막 leaf에서 10개는 비워두고, 6개의 영화를 순서대로 노드에 넣고 값을 1씩 증가시킨다. 영화를 10번 보기 때문에 앞의 노드를 그만큼 비워둔다. 영화가 순서대로 1, 2, 3, 4, 5, 6이 쌓여있는 상태다. 예를 들어 3번 영화를 본다고 가정하면, 3번 앞에는 1번과 2번 영화가 있기 때문에 .. 2023. 1. 20.

이전 1 2 3 4 5 ··· 10 다음

티스토리툴바