nextcoder nextcoder

✔️ 다익스트라 최단 경로 알고리즘 개요 : 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 음의 간선이 없을 때 정상적으로 동작 (현실 세계와 유사) 그리디 알고리즘으로 분류 (매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복) ✔️ 동작 방법 1. 출발 노드 설정 2. 출발 노드 기준으로 각 노드의 최소 비용 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 후 방문 노드로 설정 4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신 5. 3~4번 반복 [문제] https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, ..

기준 좌표(0,0)에서 (x, y)와 (a, b) 두 좌표 간의 각도를 구해보자. 단, (x,y)나 (a,b)가 (0,0)이면 안된다. 1. 첫 번째 좌표(벡터)의 크기를 구한다. #include double v1 = sqrt(pow(x, 2) + pow(y, 2)) 2. 두번째 좌표(벡터)의 크기를 구한다. #include double v2 = sqrt(pow(a, 2) + pow(b, 2)) 3. 백터의 내적을 구한다. #include double inner = (x * a) + (y * b) 4. 각을 계산하기 위해 방정식에 값을 대입한다. #include double theta = acos(inner / (v1 * v2)) *acos는 cmath라이브러리에서 지원하는 역 코사인 함수다.* 반환된 ..

- 모든 정점에서 모든 정점까지의 최소 거리를 구한다. - 다익스트라 알고리즘과 유사하나 다익스트라는 한 정점에서의 모든 정점과의 최소 거리를 구할 뿐이다. - 다이나믹 프로그래밍이 적용된 알고리즘 이다. - 정점끼리의 2차원 배열에서 [i][k] 가 연결되어 있고, [k][j]가 연결되어 있을 때, [i][k]가 연결되어 있음을 표시해준다. - k를 첫번째 정점(1) 부터 정점의 수 n까지 반복한다. 예제) 프로그래머스 - 순위 https://programmers.co.kr/learn/courses/30/parts/14393 #include #include using namespace std; bool Node[101][101]; int solution(int n, vector results) { in..