기록보관소

https://www.acmicpc.net/problem/11657 11657번 타임머신 문제의 핵심은 벨만-포드 알고리즘입니다. 벨만-포드 알고리즘에 대한 설명은 다음의 게시물에 있습니다. 2022.01.02 - [알고리즘/이론] - [알고리즘/이론] 벨만-포드 알고리즘 [알고리즘/이론] 벨만-포드 알고리즘 벨만-포드 알고리즘 벨만-포드 알고리즘은 가중치를 가지는 방향그래프의 최단거리를 구하는 데 사용되는 알고리즘입니다. 특징으로 음의 가중치를 가지는 경우에도 사용할 수 있습니다. 또한 ark-hive.tistory.com 해당 문제는 벨만 포드 알고리즘을 그대로 적용하여 해결할 수 있습니다. 주의사항 실제 구현에서 정점까지의 경로가 존재하지 않을 때의 무한대 값을 실제 숫자로 치환하여 구현하기 때문에..

벨만-포드 알고리즘 벨만-포드 알고리즘은 가중치를 가지는 방향그래프의 최단거리를 구하는 데 사용되는 알고리즘입니다. 특징으로 음의 가중치를 가지는 경우에도 사용할 수 있습니다. 또한 출발점에서 도달가능한 음의 순환의 존재 여부를 확인할 수도 있습니다. 음의 순환이 존재하면 최단거리는 구할 수 없습니다. 모든 최단경로는 순환을 가지지 않으며 따라서 한 정점을 두 번 이상 방문하지 않습니다. 그래프에 정점이 V개 있다면 최단 경로는 최대 V-1개의 간선을 가질 수 있습니다. 최단거리 계산에는 출발점에서 도착점까지의 경로를 순서대로 완화함으로써 최단거리 값을 구할 수 있다는 정리가 이용됩니다. 그래프의 모든 간선을 V-1번 완화(노드의 추정최단거리 값을 갱신하는 행위)하면 한 출발점에서의 모든 다른 노드까지로..

R2 문제는 단순한 수학문제입니다. 작성한 코드는 다음과 같습니다. #include using namespace std; int R1, S; int main(void) { cin >> R1 >> S; cout

별 찍기 - 7 문제는 단순한 구현 문제입니다. 작성한 코드는 다음과 같습니다. #include using namespace std; int N; int main(void) { cin >> N; for (int i = 1; i

별 찍기 - 8 문제는 단순한 구현 문제입니다. 작성한 코드는 다음과 같습니다. #include using namespace std; int N; int main(void) { cin >> N; for (int i = 1; i

별 찍기 - 13 문제는 단순한 구현 문제입니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int N; int main(void) { scanf("%d", &N); for (int i = 1; i

별 찍기 - 6 문제는 단순한 구현 문제입니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int N; int main(void) { scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { printf(" "); } for (int j = 1; j

별 찍기 - 5는 단순한 구현 문제입니다. 문제의 조건을 읽고 적당히 구현하면 됩니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int N; int main(void) { scanf("%d", &N); for (int i=1; i