일지 & 개발

문제 요약 알고리즘 분류: 트리 난이도: Gold3 문제내용: 도로는 방향이 없고 웜홀은 방향이 있다. 웜홀로 이동하면 시간은 거꾸로 흘러 간다. 자기 자신으로 돌아 올때 거꾸로 흘러 가는지 출력해라. 사이트: https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제풀이 이번에는 문제 유형은 벨만-포드 알고리즘이다. 벨만-포드 알고리즘에 대한 자세한 설명은 여기에서 보면된다. 기본적으로 벨만-포드 알고리즘 지식과 구현 하면되기 때문에 ..

이론 이번에 볼 알고리즘은 벨만-포드 알고리즘이다. 최단 거리를 알고리즘 구하는 알고리즘 중 하나이다. 일반적인 다익스트라 알고리즘이나 플루이드-워셜 알고리즘이랑 다른점은 가중치가 음수인 점이다. 가중치가 음수라는 점에서 다익스트라 처럼 몇개의 간선만 선택 할 수 있는 점과 다르게 벨만-포드는 모든 간선을 봐야 된다는 점이다. 일단 벨만-포드 알고리즘을 알기위해서는 그래프에 대한 개념이 있어야 되기 때문에 그래프를 먼저 보고 공부하는 것을 추천한다. 그래프: https://jih3508.tistory.com/100 [알고리즘 이론] 그래프(Grape) 이론 이번에 볼 자료구조는 그래프이다. 트리는 노드간에 부모-자식, 형제 이런 개념이 있지만 그래프는 노드하나 이상이 사이클을 가진 개념이다. 사이클이란 ..