본문 바로가기

728x90

IT/Python

(167)

[백준] 12865번 이진 검색 트리 [Python] 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제 이진 검색 트리 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 후위 순회: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 더보기 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 $($루트-왼쪽-오른..

[백준] 12865번 평범한 배낭 [Python] - 다이나믹 N개의 물건과 각 물건의 무게 W, 가치 V가 주어질 때, 최대 무게 K 내에서 가치의 합이 최대가 되는 그 최댓값을 구하는 문제 더보기 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의..

[백준] 9251번 LCS [Python] - 다이나믹, 문자열 LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제 최장 공통 부분 수열 더보기 문제 LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. https://www.acmicpc.net/problem/9251 한 단어의 철자를 순서대로 다른 단어의 철자와 비교하면서 같은 철자가..

[백준] 2096번 내려가기 [Python] - 다이나믹 N행 3열에 0 이상 9 이하의 숫자가 적혀 있다. 첫번째 줄부터 내려가면서 숫자를 하나씩 선택해서 총 N개의 숫자를 모두 더하면 점수가 된다. 아래 그림처럼 현재 선택 된 곳이 ☆이면 그 아래 줄에서 바로 아래거나 그 옆인 곳만 선택할 수 있다. 위 조건을 만족하면서 최대/ 최소 점수를 구하는 문제이다. 더보기 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이..

[백준] 2003번 수들의 합 2 [Python] - 누적 합 N개의 수열과 자연수 M이 주어지면, i번째 수 부터 j번째 수 까지의 합이 M이 되는 경우의 수를 구하는 문제 더보기 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N$(1 ≤ N ≤ 10,000)$, M$(1 ≤ M ≤ 300,000,000)$이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. https://www.acmicpc.net/problem/2003 수열을 ..

[백준] 1916번 최소비용 구하기 [Python] - 그래프 이론 도시의 수: N, 버스의 수: M와 정보: $($A -> B, 버스 비용$)$, 출발 도시: S, 도착 도시: E에 대한 정보가 주어질 때, 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 문제 더보기 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N$(1 ≤ N ≤ 1,000)$이 주어지고 둘째 줄에는 버스의 개수 M$(1 ≤ M ≤ 100,000)$이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주..

[백준] 11660번 구간 합 구하기 5 [Python] - 다이나믹, 누적 합 N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 문제. $(x, y)$는 x행 y열을 의미한다. 1차원 수열의 구간 합 문제 https://savvy0402.tistory.com/216 위 문제와 비슷하지만 이번에는 2차원 수열의 구간 합을 구하는 문제라고 보면 된다. 더보기 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 프로그램을 작성하시오. $(x, y)$는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 $(2, 2)$부터 $(3, 4)$까지 합을 구하면 3..

[백준] 11659번 구간 합 구하기 4 [Python] - 누적 합 N 개의 수가 주어졌을 때, 1 ≤ i ≤ j ≤ N인 i번째 수부터 j번째 수까지 합을 구하는 문제 i, j 순서쌍은 M번 주어짐 더보기 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N https://www.acmicpc.net/problem/11659 수열 $A_{n}..

[백준] 1991번 트리 순회 [Python] - 재귀 문제 이진 트리를 입력받아 전위 순회$($preorder traversal$)$, 중위 순회$($inorder traversal$)$, 후위 순회$($postorder traversal$)$한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // $($루트$) ($왼쪽 자식$) ($오른쪽 자식$)$ 중위 순회한 결과 : DBAECFG // $($왼쪽 자식$) ($루트$) ($오른쪽 자식$)$ 후위 순회한 결과 : DBEGFCA // $($왼쪽 자식$) ($오른쪽 자식$) ($루트$)$ 가 된다. 더보기 입력 첫째 줄에는 이진 트리의 노드의 개수 N$(1 ≤ N ≤ 26)$이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼..

[백준] 9465번 스티커 [Python] - 다이나믹 2행 n열로 배치된 스티커 2n개에 각각 점수가 매겨졌다. 스티커를 떼어내면 상하좌우가 찢어져서 주변 스티커는 사용 못한다. 사용한 스티커의 점수 합이 최대가 되는 그 최댓값을 구하는 문제 더보기 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 $(a)$와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내..

[백준] 1932번 정수 삼각형 [Python] - 다이나믹 아래 그림 같은 정수 삼각형이 주어질 때, 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 맨 위에 있는 꼭짓점부터 바로 아래에 있는 숫자 중 하나$($아래층의 대각선 왼쪽 또는 대각선 오른쪽$)$를 골라서 내려올 때, 합이 최대가 되는 경로의 그 합을 구하는 문제 더보기 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형..

[백준] 1629번 곱셈 [Python] $A^{B} \,\%\, C \,=\, ?$ A, B, C 가 주어졌을 때 위 식의 답을 구하는 문제 더보기 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. https://www.acmicpc.net/problem/1932 분할 정복을 이용한 거듭 제곱 B가 2의 거듭제곱일 경우 재귀적으로 A의 제곱을 반복해서 너무 큰 지수 연산을 피한다. B가 홀수 일때, $($B-1$)$의 절반에 대해서 위의 과정이 가..

이전 1 2 3 4 5 6 ··· 14 다음

티스토리툴바