반응형 메모리 풀13 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 11779 : 최소비용 구하기 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/11779 ※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용과 도시의 개수 그리고 최소 비용이 되는 경로도 출력해야 한다. 메모리 풀 방식으로 각 도시 간의 연결과 가중치를 저장한다. typedef struct st { int value; int weight; struct st *next; }NODE; NODE HEAD[1010]; NODE POOL[100100]; int pcnt; void Make(int p, int c, int w) { NODE *nd = &POOL[pcnt++]; nd->value = c; nd->weight = w; nd-.. 2022. 7. 16. BOJ 2252 : 줄 세우기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2252 A가 학생 B 앞에 서야 한다는 조건이 있으므로 위상 정렬을 이용하여 풀면 된다. 즉, A → B에 대해 B의 indegree가 1 증가하고, indegree가 0인 학생부터 BFS를 시작하면 된다. 설명은 BOJ 1005 : ACM Craft와 동일하다. #include int N, M, A, B; int indegree[32100]; int queue[100100]; int rp, wp; typedef struct st { int value; struct st *next; }NODE; NODE HEAD[32100]; NODE POOL[100100]; int pcnt; void Make(int p, int c) .. 2021. 7. 17. BOJ 1005 : ACM Craft 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1005 위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다. 4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다. 따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다. 이런 문제는 위상 정렬을 이용해서 풀 수 있다. 1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다. 2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다. 입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다. ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다. #.. 2021. 7. 14. BOJ 1939 : 중량제한 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1939 문제의 답이 되는 최대 중량을 X라고 하자. 그리고 두 섬이 연결되어 있는 것은 DFS를 이용하자. 섬 1과 섬 2가 중량 X로 다리를 건널 수 있다면, DFS(X, 섬 1)은 섬 2로 연결된다. 그러면 DFS(X, 섬 1)은 true다. DFS(X + 1, 섬 1)은 반드시 false가 된다. 이유는 문제의 답이 되는 최대 중량이 X이므로, X + 1의 중량을 견딜 다리가 없기 때문이다. 반대로 DFS(X - 1, 섬 1)은 반드시 true가 된다. 중량 X를 견디는 다리는 최대 중량 X보다 작은 값도 견딜 수 있기 때문이다. 따라서 정답 X에 대해 X보다 작거나 같은 값은 섬을 연결할 수 있고, X보다 큰 값은.. 2021. 5. 22. BOJ 2606 : 바이러스 (Linked List Tail ver) 삼성 B형 전체 링크 삼성 C형 전체 링크 www.acmicpc.net/problem/2606 참고 - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List - 링크드 리스트 Linked List Tail ver - 더블 링크드 리스트 Double Linked List - 더블 링크드 리스트 Double Linked List Tail ver Linked List는 HEAD만으로도 충분하지만, 가~~~끔 들어온 순서를 고려해야하는 경우가 있다. 이 때는 TAIL을 써서 끝 node의 주소를 기억해두면 된다. Make 함수를 보자. void Make(int p, int c) { NODE *nd = &POOL[pcnt++]; nd->node = c;.. 2021. 2. 16. 이전 1 2 다음 반응형
