본문 바로가기
반응형

priority queue30

[코드트리] 토끼와 경주 (삼성 SW 역량테스트 2023 상반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고- B형 필수 : 우선순위 큐 Priority Queue- BOJ 10825 : 국영수 https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race 2차원 좌표 N x M이 100,000 * 100,000이다. → 2차원 배열 선언 시, 메모리 초과토끼가 움직이는 거리 d → d 만큼 움직이면 시간 초과 따라서, 토끼 구조체에서 좌표를 관리하고, 효율적으로 움직여야 한다. 좌표를 관리할 구조체와 토끼.. 2024. 7. 28.
BOJ 6593 : 상범 빌딩 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/6593 참고 - BOJ 11779 : 최소비용 구하기 2 최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다. 상범 빌딩은 다익스트라를 3차원에 적용하면 된다. tc가 여러 개이므로 매 tc마다 dist를 INF로 visit을 0으로 초기화한다. for (i = 1; i 2023. 3. 26.
BOJ 1504 : 특정한 최단 경로 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1504 참고 - BOJ 11779 : 최소비용 구하기 2 최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다. 이 문제에서는 임의의 두 정점(n1, n2)을 통과하는 최단 경로를 구하려고 하므로, 다익스트라를 여러 번 사용하면 된다. 즉, 출발점 - n1 - n2 - 도착점에 대해 각각 다익스트라를 이용해 거리를 구한다. 여기서 n1이 반드시 n2 보다 먼저 도착해야할 이유는 없다. n1 - n2와 n2 - n1 경로를 비교해서 더 작은 경우가 정답이 된다. ans1 = getDijkstra(1, n1) + getDijkstra(n1, n2) + getDijkstra(n2,.. 2023. 3. 25.
유니티 - 다익스트라를 이용하여 최단 경로 이동하기 (Move the Shortest Path using Dijkstra) Unity 전체 링크 다익스트라(데이크스트라)를 이용하면 최소 경로를 찾을 수 있다. 그리고 최소 경로를 찾을 때 해당 경로를 저장해두면 경로도 구할 수 있다. 관련 알고리즘은 아래 링크를 참고하자. - BOJ 11779 : 최소비용 구하기 2 (최단 경로 기억) - BOJ 1261 : 알고스팟 (2차원 배열 다익스트라) 그리드 기반으로 맵을 탐색한 후, 빨간 큐브 (0, 1, 0)가 보라색 큐브 (-7, 1, 4)로 가기 위한 최단 경로를 찾아보고 직접 이동도 해보자. 그리드 보다 높게 보이기 위해 y = 1로 설정하였다. 최단 경로를 찾으면 아래와 같다. Invoke는 필요 없으므로 원래대로 돌린다. 아래의 코드에서 다익스트라를 시작한다. 다익스트라 관련 코드는 #region Dijkstra Algo.. 2022. 7. 17.
BOJ 1261 : 알고스팟 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1261 ※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다. BOJ 11779 : 최소비용 구하기 2의 다익스크라(데이크스트라) 알고리즘을 2차원 배열에서 사용하면 된다. 2차원 배열의 각 인접한 노드는 dr, dc 배열로 탐색한다. int dr[] = { 0, 1, 0, -1 }; int dc[] = { 1, 0, -1, 0 }; 그리고 벽(1)이 비용이 된다. int MAP[110][110]; 거리를 저장할 2차원 배열과 방문 여부를 체크하는 배열, 그리고 최소 힙을 만든다. int distance[110][110]; int visit[110][110]; typedef struct st2 { in.. 2022. 7. 17.
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.
Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다.제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다.   PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver  Inde.. 2022. 1. 13.
BOJ 14427 : 수열과 쿼리 15 (Reference) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 B형에서는 Reference로 우선순위 큐 code가 주어진다. 하지만 STL(priority_queue) 사용이 가능하더라도, 갱신이 가능한 우선순위 큐는 직접 만들어야 한다. 여기서는 Reference 우선순위 큐로 문제를 풀었다. (Indexed Priority Queue, Heap) 해설은 이전 글을 참고하자. #include int N, M; typedef struct st { int value; int id; }HEAP; HEAP heap[100100]; int heapIdx[100100]; int heapSize; int isMin(HEAP a, HEAP b) { if (a.value < b.value).. 2021. 7. 3.
BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 참고 - BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리 우선순위 큐의 갱신을 이용하여 문제를 풀 수 있다. update를 위해 우선순위 큐를 최악의 값으로 초기화한다. for (int i = 0; i < 200100 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000; 처음의 값들은 순서대로 A1 ~ AN 이므로 heapIdx(id)를 각각 i = 1 ~ N으로 본다. for (int i = 1; i 1; i /= 2) { if (isMin(heap[i / 2], heap[i])) break; tmp = heap[i]; heap[i] = he.. 2021. 7. 3.
반응형

티스토리툴바