SCCC - Soongsil Computing Contest Club/2019 Spring-Study
-
다익스트라(dijkstra)SCCC - Soongsil Computing Contest Club/2019 Spring-Study 2019. 6. 3. 01:25
1. 다익스트라 특정 하나의 노드에서 각 노드까지의 최단길이를 모두 구하는 알고리즘. 제일 작은 노드 탐색 갈 수 있는 노드들 값 갱신 이거 1,2 무한반복 : 다익스트라. 쉽죠? 일종의 그리디라고 할 수 있는 다익스트라. 그리디의 모순에 의한 증명으로 증명 할 수 있다. >>위의 알고리즘을 사용해서 최단경로를 만들었을 때 다른 노드를 경유하여 들어오는 경로가 최단이지 않으면 증명 완료. 대표적인 다익스트라 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V..
-
STL Vector, 그래프, 트리 (20190517)SCCC - Soongsil Computing Contest Club/2019 Spring-Study 2019. 5. 17. 20:49
1. vector vector name; array와 같다. (1) push_back(value) : 벡터에 value를 맨 뒤에 집어넣는다. (2) pop_back() : 맨 뒤의 값을 뺀다. (3) size() : 벡터의 사이즈 리턴. 2. 그래프 정점과 간선의 집합. 정점(node, vertex) 간선(edge, arc) 표현 방법에는 어떤게 있을까? (1) 인접행렬 이차원배열로 정점과 정점의 연결관계를 나타냄. arr[i][i]는 0이고 , 양방향그래프에선 arr[i][j]와 arr[j][i]의 값은 같다. 메모리 낭비가 너무 심해서 10^6만 되어도 터진다. (2) 인접리스트 각 정점에서 연결된 정점만 표현해주는 리스트. 벡터를 사용하면 완젼 편리하다. vector graph[5]이렇게 하면 굿..
-
STL Priority_queue(heap), (20190503)SCCC - Soongsil Computing Contest Club/2019 Spring-Study 2019. 5. 3. 20:31
1. Heap (=priority queue) 값이 들어가면 정렬된 형태로 저장하는 구조. 넣을때 logN, 뺄 때 logN의 시간이 걸린다. priority_queue pq; pq.push() pq.pop() pq.top() => 특이하게 top을 쓴다 작은거부터 뽑고싶을 때는 priority_queue pq; 혹은 priority_queue pq; 그대로 해놓고 3을 넣지말고 -3을 넣고 뺄때 - 붙여주면 됨 ㅋㅋㅋㅋㅋ 신박하다 문제 : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수..