[백준] 11054번 가장 긴 바이토닉 부분 수열 [Python]
수열 S가 어떤 수 $S_k$를 기준으로 $S_1 S_N$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 주어진 수열의 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제 더보기 문제 수열 S가 어떤 수 $S_k$를 기준으로 $S_1 S_{k+1} > ... S_{N-1} > S_N$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토..
[백준] 17070번 파이프 옮기기 1 [Python] - 다이나믹
아래 규칙에 의해서 NxN 격자판에서 $($1, 1$)$에서 $($N, N$)$으로 파이프를 연결하는 경우의 수를 구하는 문제, 불가능할 경우 0을 출력 처음에는 $($1, 1$)$, $($1, 2$)$에 걸친 파이프가 놓여있다. 파이프를 이동하려면 위 그림처럼 가로는 오른쪽, 세로는 아래, 대각선은 오른쪽, 아래, 오른쪽 아래에 아무것도 없어야 합니다. 격자 내에 벽이 존재할 수 있습니다. 더보기 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 $(r, c)$로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 ..
[백준] 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개의 웜홀이 있다. $(단 도로는 방향이 없으..
