알고리즘/문제풀이 - 백준

백준 11286 절댓값 힙

문제 : https://www.acmicpc.net/problem/11286 서론 1927 최소 힙 문제에서 힙 교환 조건을 크기에서 절댓값과 크기로 변경 1927 : https://hydroponicglass.tistory.com/54 구현 // c++ // min heap #pragma warning (disable:4996) #include #include #include typedef struct pq { int heap[100003] = { 0, }; int index = 0; }pq; void push(pq *q, int item) { q->index++; q->heap[q->index] = item; int index = q->index; while (abs(q->heap[index]) he..

2019. 8. 21. 14:36
알고리즘/문제풀이 - 백준

백준 1927 최소 힙

문제 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 서론 11279번 문제인 최대 힙을 변형했다. 백준 11279 최대 힙 문제 : https://www.acmicpc.net/problem/11279 서론 최대 힙에 관한 문제라서 최대 힙을 구현해봤다. 시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 � hydroponicglass.tistory.com 구현 최대 힙..

2019. 8. 21. 11:43
알고리즘/문제풀이 - 백준

백준 11279 최대 힙

문제 : https://www.acmicpc.net/problem/11279 서론 최대 힙에 관한 문제라서 최대 힙을 구현해봤다. 시간초과가 발생해서 무한루프를 예상하고 원인을 매우 아주 상당히 오래 찾았으나 cin, cout의 속도로 인한 문제였다. printf, scanf 를 사용하여 해결했다. 구현 // c++ // max heap #pragma warning (disable:4996) #include #include typedef struct pq { int heap[100003] = { 0, }; int index = 0; }pq; void push(pq *q, int item) { q->index++; q->heap[q->index] = item; int index = q->index; whi..

2019. 8. 20. 20:20
알고리즘/문제풀이 - 백준

백준 1504 특정한 최단 경로

문제 : https://www.acmicpc.net/problem/1504 서론 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이했다. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4가 최단경로일때 1에서 4까지의 최단경로는 1~2까지의 최단경로를 포함하고 2~3까지의 최단경로를 포함한다. 즉 목적지까지의 최단경로는 중간지점들의 최단경로 합이다. 두개의 정점이 n1, n2일때 시작정점부터 두개의 정점을 거쳐서 종료정점까지 가는 방법은 1. 시작정점 -> n1 -> n2 -> 종료정점 2. 시작정점 -> n2 -> n1 -> 종료정점 두개의 방법이 있다. 1번 방법은 시작정점 -> n1의 최단경로, n1 -> n2의 최단경로, n2 -> 종료정점의 최단경로의 합을 구하면 되고 2번 방법도 마찬가..

2019. 6. 27. 20:01
알고리즘/문제풀이 - 백준

백준 1753 최단경로

문제 : https://www.acmicpc.net/problem/1753 서론 다익스트라 방법으로 풀이했으나 시간초과. 이후 우선순위 큐를 이용한 다익스트라로 해결. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4 그래프에서 1번에서 4번까지의 최단경로는 1번에서 2번, 2번에서 3번, 3번에서 4번까지의 최단경로를 포함한다는것을 전제로한다. 즉 최단경로 + 최단경로 = 최단경로다. 정점을 이동할때마다 최단경로를 계속 누적시켜주면 된다. 여기에 우선순위큐를 이용하게 되면 경로 중 최단경로를 우선적으로 탐색하여 탐색횟수를 줄일 수 있다. 구현 우선순위 큐를 이용한 성공한 구현 // c++ #pragma warning (disable : 4996) #include #include #include..

2019. 6. 27. 17:17