다이나믹 프로그래밍
[백준] 2213번 - 트리의 독립집합
https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 💡 원리 트리의 정점에 가중치가 있으며, 독립집합을 찾는 문제이다. 문제를 잘 읽어보면 트리의 동적 프로그래밍을 사용하면 풀리는 문제인데, 이 문제는 더 나아가 출력으로 가장 큰 독립집합의 값의 정점을 찾아 출력을 해야한다. 우선 동적 프로그래밍을 사용해 가장 큰 독립집합을 찾아보자 트리의 형태이기 때문에 root=0 부터 차례대로 정점을 탐색할 수 있고, 동..
[백준] 10942번 - 팰린드롬?
이번 문제는 팰린드롬이라는 생소한 단어가 나왔는데, 문제에서 팰린드롬의 정의를 해주지 않아 인터넷에 팰린드롬이라는 단어를 찾아봤습니다. 위키백과에서는 palindrome을 회문이라 했으며, 회문이란 숫자나 문자를 정방향으로 읽어도, 거꾸로 읽어도 같은 숫자나 문자를 말합니다. 처음에 이 문제를 해결하기 위해서 각 위치에 맞는 짝을 찾아 비교하기 위해 규칙을 찾아보았는데, 따로 규칙을 찾을 필요없이 우리가 S, E를 선택했기 때문에 (S+i) = (E-i) 라는 규칙을 쉽게 생각 할 수 있었습니다. 그리고 이 문제 조건에서 시간 제한을 0.5초를 두었기 때문에 Dynamic programming을 이용해야 함을 알 수 있었습니다. int palin(int s, int e) { if (s >= e) { re..