뜌릅

LCS문제 입니다. 저는 처음 봤는데, 구글링을 해본 결과, 유명한 문제 유형이더군요. 이 문제도 전에 풀었던 Knapsack문제와 매우 유사하게 풀었습니다. 역시 dp를 사용했습니다. Dp문제는 너무 어려운 것 같습니다. 보고나면, 쉬운데 발상 자체는 떠올리기가 힘듭니다. 이 문제를 풀기위해서는 한글자씩 비교하면서, 맞으면 갯수+1를 해야 합니다. 하지만, 단순히 모든걸 비교하면, 시간초과가 발생합니다. 결국에는 어떤 방식으로 비교하는 문제가 되는 겁니다. 이 문제는 BFS같은 느낌으로 풀었습니다. 둘이 비교해서 같으면 +1, 다르면 첫번째 문자열만 다음 문자로 넘긴것과 두번째 문자열만 다음 문자로 넘겼을 경우를 비교하여, 둘중 최댓값을 출력하는 겁니다. #import using namespace st..

이 문제는 knapsack유형의 문제라고 한다. 나는 이 문제를 처음 봤지만, 풀는데에 구글링을 해서 솔루션을 보았기에, 앞으로 dp유형과 knapsack유형이 익숙해질때까지 많이 풀고자 한다. 어느 dp문제가 그렇듯이, 점화식을 작성해야 한다. 처음 이 문제를 접했을 때, 기준점을 잡기가 어려웠다. 하지만, 구글링을 하게 된 결과, 기준은 내가 정하게 되는거란 것을 알게 되었다. 나는 기준을 입력순대로 정하였다. 이 기준대로, 물건의 종류를 처음에는1개에서 2개, ....... n개까지 1개씩 증가시키면서 그때마다의 최댓값을 얻어냈다. 1개일 때의 최댓값을 구하는건 쉽다. 무게보다 낮을경우 0, 높을 경우 해당 물건의 무게값. k개일 때의 최댓값은 k-1개일 때의 최댓값에서 k번째 물건을 추가시킨 경우..

백준에서 The Triangle문제를 풀어보았습니다. 처음에는 실버2난이도여서, 대충 recursive algorithm으로 풀려고 했으나, 시간을 초과했고, 이후 dp문제임을 깨닫고 dp를 사용하여 풀어보았습니다. 처음 보는순간 recursive algorithm을 이용한 dfs이면 풀수 있지 않을까?? 라는 생각이 먼저 들었습니다. dfs()함수를 새로 만들어서, 왼쪽으로 간경우와 오른쪽으로 간경우를 호출하고, 그 둘의 값을 비교하여 더 큰값을 return시키는 함수를 만들었습니다... int n; vector v[500]; int dfs(int i,int floor){ if(floor >n; rep(i,n){ int a; int j =i+1; while(j--) { cin >> a; v[i].pb(..

내가 문제풀때 볼려고 쓴 글입니다. 나를 위한 팁 1. 트리는 배열로 구현하는데, PS시 배열의 크기를 맞게 할 필요는 없으므로, 넉넉하게 하자. 2. 세그먼트 트리를 항상 Sum으로 할 필요는 없다. 상황에 잘 맞게 운용할수 있는걸 명심하자. (초기화 방법)segment tree int h = (int)ceil(log2(n)); int tree_size = (1