[백준] 11444번 피보나치 수 6 [Python]
$10^18$ 이하의 자연수 n에 대해서 n번째 피보나치 수를 $10^9+7$로 나눈 나머지를 구하는 문제 더보기 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 $(n ≥ 2)$가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연..
[백준] 1167번 트리의 지름 [Python]
트리의 지름을 구하는 문제 N개의 노드에 대해서 각 노드마다 한 줄에 그 노드, 연결된 노드1, 거리1, 노드2, 거리2, ... -1 이런 구조로 정보가 주어진다. 예$)$ 3, 1, 2, 4, 3, -1 >>> 3과 1은 거리가 2; 3과 4는 거리가 3; -1: 끝 의미 트리$($tree$)$는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경..
[백준] 1865번 웜홀 [Python] - 벨만 포드
테스트 케이스의 개수만큼 아래 주어진 정보로 답을 구해야 한다. N개의 지점에 M개의 도로$($무방향$)$와 W개의 웜홀$($단방향$)$이 있다. 도로와 웜홀은 시작 위치, 도착 위치, 소요 시간으로 주어진다. 소요 시간은 0 이상, 10,000 이하인데, 웜홀은 도로와 다르게 소요 시간만큼 시간이 줄어든다. - 음수처럼 생각하면 쉽다. 각 테스트 케이스에서 처음 위치로 되돌아 올 때, 시간이 과거로 갈 수 있다면 YES, 불가능하면 NO를 출력하는 문제 TC N, M, W 도로 정보 M개 웜홀 정보 W개 x TC 수만큼 반복 더보기 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. $(단 도로는 방향이 없으..
[백준] 11657번 타임머신 [Python] - 벨만 포드
n개의 도시가 있고, 1번 도시에서 나머지 도시로 가는 최소 시간을 구하는 문제 m개의 버스 노선이 시작도시, 도착도시, 시간 정보로 주어진다. 시간은 양수, 0$($순간 이동$)$, 음수$($타임머신$)$일 수 있다. 소요 시간을 음의 무한대로 향하게 할 수 있다면 -1을 출력한다. 그게 아니라면 순서대로 소요시간을 출력하고, 해당 도시로 가는 경로가 없는 경우는 시간 대신 -1을 출력한다. 더보기 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C ..
