본문 바로가기

알고리즘/BAEKJOON87

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.

BOJ 1395 : 스위치 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1395 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) Si ~ Ti까지 스위치를 반전시켜야 하므로, 구간의 갱신이 매우 많다. 따라서 느리게 갱신되는 세그먼트 트리를 이용해서 문제를 풀 수 있다. 예를 들어서 1 ~ 16까지 스위치가 있고 1, 2, 4, 5번 스위치가 켜져있다고 하자. 이 상태에서 1 ~ 4번 스위치를 반전시키면 아래와 같이 트리가 갱신되어야 한다. 1 ~ 4번의 스위치가 3개 켜져 있는 상태에서 4개의 스위치를 반전시.. 2023. 1. 19.

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

티스토리툴바