개구리의 개발 블로그 개구리의 개발 블로그

백준 14427번 수열과 쿼리 15 파이썬 문제 링크 - https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 문제를 공부해야겠다고 생각한 지 벌써 3개월은 된 것 같다. 심지어 이 문제도 트리를 이용한 해시 문제를 풀기 위해 시도했지만 도저히 안풀려서 알고리즘 분류를 보고 세그먼트 트리를 공부하게 되었다. 우선 쿼리 문제이기 때문에 python을 사용한다면 sys.stdin.re..

백준 2213번 트리의 독립집합 파이썬 출처 - https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 트리에서 DP를 사용하는 문제였다. 독립집합의 크기를 구하는 것은 쉽게 생각할 수 있었다. 백준 트리DP 알고리즘 분류에서 가장 위에 있는 SNS 문제와 거의 유사했다. 경로를 구하기 위해서 따로 추적을 하는 함수를 작성했는데 간단하게 만드는 방법도 존재할 것 같다. 1. 풀이 1. 최대값 구하기 트리의 독립집합에 포..