오늘은 DP문제를 하나 풀어보았다. 저번에 애를 먹었던 https://miffu-bh.tistory.com/7 이 문제와 풀다보니 비슷했다. 사실 공통점이라곤 뒤에서 부터 dp값 저장을 시작한 다는 것 말고는 없긴 하지만 이것을 예전에 풀어보지 않았다면 이 문제도 한참이 걸렸을 수도 있을 것 같다. 하지만 다행히 뒤에서부터 dp값을 변경해보면 되겠다는 생각을 빨리 할 수 있었고 쉽게 풀 수 있었다! 숫자들이 연속해서 들어오고, 연속한 수들만 더해 나갔을 때 가장 큰 값이 되는 것을 구하면 된다. 누가봐도 dp로 풀어야 함을 알 수 있어서 사실 나말고 다른사람들한테도 쉬웠을 것 같다ㅜ 그래도 이정도면 늘긴는거다! 처음부터 더해나가다 보면, 음수가 나왔을 때 이 음수를 더하고 계속 연속해 나가야 할지, 아니..

오늘은 초등학교 동창이자 대학 동기인 이ㅇㅇ군 과 함께 스타벅스에서 공부를 하게 되었다. 함께 공부를 잠깐 하다 같이 알고리즘 1문제를 풀어보기로 하였고, DP문제가 구현이 쉽다 주장하는 이ㅇㅇ군의 의견을 적극 반영해 DP문제를 함께 풀게 되었다. 열심히 문제를 풀던 와중, 스타벅스 직원이 와서 2인 이상은 1시간 밖에 이용이 안되니 나가달라고 하였다. 거의 다 풀었다 생각했는데 중간에 쫓겨나게 된 우리는 아쉬움을 달래기 위해 코인노래방에서 잠깐 노래를 부르고 집에 왔다. 하지만 알고보니 난 거의 다 푼것이 아니었다. 내가 잘못 접근하고 있던 방식이 내가 대부분의 DP문제를 풀 때 접근하는 방식이었기 때문에 그렇게 풀면 안된다는 사실을 깨닳았던 좋은 문제였다. DP배열에는 그 날까지 최대로 얻을 수 있는..

알고리즘 수업에서 분할 정복을 가르치기에 분할정복 문제를 풀어보았다. 찾아보니 이렇게 푸는 문제는 분할 정복을 이용한 거듭제곱 이라고 부르는것 같다. 기존에 어떤 수 의 n승(x^n) 을 계산하는데 걸리는 시간은 x를 n번 곱하기 때문에 O(n) 의 시간이 기존 걸린다. 하지만 그 수가 워낙 커지게 되면 정해진 시간안에 문제를 해결 할 수가 없게된다. 그럴 때 분할정복을 이용하면 된다! 이 문제의 경우 도착해야 할 징검다리까지 도달하는 모든 방법의 수를 세야 한다. 이 때 1번 징검다리에서 n번 징검다리까지 도달해야 한다면, 그 사이 징검다리마다 그 다리를 거치는경우, 거치지 않는 경우 2경우가 생긴다. 따라서 모든 경우의 수가 (2)^n-2 에 달하게 되는데, 이 때 문제에서 가능한 n의 크기가 너무 ..

오늘은 동기 김재원과 카페에서 만났다. 함께 한 문제를 풀어보기로 하였는데, 역시 김재원이 먼저 풀었다. 이게 바로 그 문제이다. 백준 2565번. DP를 이용하여 푸는 문제인데, 나는 초반 접근을 잘못해서 해맸다. 요즘 DP라는 드라마가 유행이라, 이제 DP를 대표하는 단어가 다이나믹 프로그래밍이 아니게 되어 조금 아쉽다.. 드라마는 재밌었다! 우선 이 문제는 사실 백준 11053 가장 긴 증가하는 부분 수열 문제와 매우 유사하다. 우선 처음에 난 전봇대의 제일 밑에서부터 시작해 겹치는 점의 개수를 2차원배열에 저장한 후 없앴을 때와 있을 때를 dp로 계산해보려 했지만 실패했다. 맞게 생각한 풀이는, 시작점과 도착점을 pair 로 vector에 다 저장한 후, 첫번째를 기준으로 오름차순으로 정렬을 하면..