c++ (3) 썸네일형 리스트형 [알고리즘] Dijkstra 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로는 하나의 시작점이 정해져있을 것, 그리고 음수 값을 가진 간선이 없을 것이다. Greedy 적인 방법으로 접근하기 때문에 음수 값의 간선이 존재하면 알고리즘이 성립하지 않는다. 자세한 설명들은 다른 블로그에 잘 나와있으니까.. 헷갈릴 만한 개념들만 되짚어보자. 진행 방향은 다음과 같다. 초기조건 : 일차원 Distance를 저장할 수 있는 배열(이하 Dist[]). 무한대에 비슷한 큰 값을 넣어준다. 시작 집합에 시작점을 넣어준다. 알고리즘 : 1. 시작집합과 연결된 노드 중 가장 거리가 짧은 노드(이하 a).. [C++] STL sort 시간복잡도 : O(n*logn) 추가해줘야할 헤더 : #include 사용법 : sort(A,A+n); (구조체, 배열) sort(A.begin(),A.end()); (vector 형식) #include #include #include using namespace std; int n; struct tuple2 { long long s,e; }; tuple2 A[100000+5]; bool sf(tuple2 a,tuple2 b) { if(a.e==b.e) { return a.s [Day 2] 백준 1931 : 회의실 배정 해법 : 정렬 후 greedy 사실 처음보고 무조건 DP로 짰다가 시간초과가 나와서 다시 생각해보았다. 해답은 회의가 끝나는 시간을 기준으로 오름차순 정렬한 뒤에 배열의 앞에서부터 보면서 조건에 맞는(회의 시작 시간이 내가 담은 회의들이 끝나는 시간이 크거나 같은 애들)을 담으면 된다. 왜 Greedy 가 해법일까? 조건에 맞는애가 있을 때 그 애를 선택하지 않고 다음 거를 선택했을 때 얻을 수 있는 이익이 없다. 즉, 현재 지점을 i라고 한다면 i대신 i+1을 선택했을 때(i+1도 조건에 맞는다고 가정하면) 얻는 이익이 없다는 것이다. 그 이유는 회의 종료 시간을 기준으로 정렬했기 때문에 i의 회의 종료 시간이 i+1의 회의 종료시간보다 작거나 같기 때문이다. #include #include #incl.. 이전 1 다음