알고리즘60 [Python] 백준 2250번: 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] childNode = [[0, 0] for _ in range(n+1)] node = [[] for _ in range(n+1)] ans = [-1, -1] root = [i for i in range(1, n+1)] for _ in range(.. 2021. 11. 18. [Python] 백준 10422번: 괄호 https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net '(' 괄호는 +1, ')' 괄호는 -1 로 계산하면 된다. 음수가 될경우 괄호가 아니므로 양수일때만 연산해준다. 0 1 2 3 4 5 6 7 8 1 1 2 1 1 3 2 1 4 2 3 1 5 5 4 1 6 5 9 5 1 7 14 14 6 1 8 14 28 20 7 1 T = int(input()) mod = 1_000_000_007 dp = [[0 for _ in range(5002)] for.. 2021. 10. 19. [Python] 백준 2698번: 인접한 비트의 개수 https://www.acmicpc.net/problem/2698 2698번: 인접한 비트의 개수 첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 수 2개가 공백으로 구분되어 이루어져 있다. 첫 번째 수는 n이고, 두 번째 수는 k이다. n과 www.acmicpc.net 1. 비트가 0으로 끝날 때와 1로 끝날 때를 나누어준다. 0으로 끝날 때는 같은 행의 이전 열의 합이고, 1로 끝날 때는 이전 열이 0으로 끝날 때 + 이전행 이전 열의 1로 끝날 때 1을 더해준다. 2. 점화식은 dp[i][j][0] = dp [i][j-1][1] + dp [i][j-1][0], dp [i][j][1] = dp [i-1][j-1][1], dp [i].. 2021. 10. 18. [Python] 백준 13302번: 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 1. bfs+dp를 이용하여 접근하였다. 쿠폰은 최대 100 / 5 * 2 = 40개를 가질 수 있으므로 열을 40으로 잡았다. 2. 다음날이 가능하면 현재날+1, 현재 날 + 3일, 현재 날+ 5일로 각각 받을 수 있는 쿠폰의 개수 배열에 최솟값을 넣어준다. 3. 다음날이 불가능하면 다음날을 queue에 삽입하고 반복문을 탈출한다.(다음날이 불가능하면 티켓을 아에 살수가 없음) INF = 21470000.. 2021. 10. 18. 이전 1 2 3 4 5 6 ··· 15 다음