[백준] 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$)$는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경..
