본문 바로가기
반응형

DP38

백준 16287번 Parcel - 스위프트(Swift) 풀이 + 그림 설명 아이디어가 생각이 안 나서 결국 검색으로 해결한 문제ㅠㅠ DP라는 것은 감이 왔는데 지금까지 풀었던 DP 방식은 시간 초과 때문에 적용할 수가 없었다. 처음에 떠올렸던 방식은 dp(count, index, targetWeight) = weights[index...] 에서 count개의 소포를 뽑아 targetWeight를 딱 맞출 수 있는지 여부로 두고, index번째 item을 뽑는 경우 & 뽑지 않는 경우를 모두 고려하여 아래와 같은 식으로 푸는 것이었다. 하지만 count는 4, index는 5000, targetWeight는 무려 799,994여서 4*5000*799,994로 시간 안에 풀어낼 수가 없다.. dp(count, index, targetWeight) = dp(count - 1, ind.. 2022. 1. 7.
백준 2533번 사회망 서비스(SNS) - C++(cpp) 풀이 DP 문제이다. dp(idx, isParentEarly) = 부모의 얼리어답터 여부가 isParentEarly일 때, idx번 노드를 루트로 하는 부분 트리를 완성하기 위한 얼리어답터의 수로 두고 풀었다. 부모의 얼리어답터 여부를 파라미터에 둔 이유는 이것이 자식인 idx번 노드의 얼리어답터 여부에 영향을 미치기 때문이다. 1. 부모가 얼리어답터인 경우 : idx는 얼리어답터여도 되고, 아니어도 된다. 둘 중 min값을 취하면 된다. 2. 부모가 얼리어답터가 아닌 경우 : idx번은 무조건 얼리어답터여야 한다. 부모의 인접한 노드는 모두 얼리어답터야 하기 때문에 자식인 idx는 선택권이 없다. 따라서 아래와 같은 로직을 세울 수 있다. 최종적으로는 dp(루트, true)를 출력하면 된다. 루트는 부모가 .. 2022. 1. 6.
백준 2533번 사회망 서비스(SNS) - 스위프트(Swift) 시간초과 해결 이번에도 또 알 수 없는 시간 초과가 발생해서 해결하는 데 애를 먹었다. 아무래도 Swift로는 PS는 하지 않는 게 정신 건강에 좋을 것 같다ㅠ 이번 범인은 고차함수였다. 아래 글을 발견했는데, map은 확실히 반복문으로 직접 구현하는 것보다 성능이 좋았고, filter는 비슷하고, reduce는 오히려 반복문으로 직접 구현하는 게 더 빨랐다고 한다. 다만 이건 전부 체이닝 하지 않고 고차 함수를 1번만 쓰는 경우에만! 여러 고차 함수를 체이닝 하면 오히려 직접 구현보다 심각하게 성능이 좋지 않다고 한다..;;; 문제에서 reduce랑 체이닝을 남발한 부분이 있었는데 for문으로 고쳐주었더니 시간 안에 통과가 됐다. https://www.skoumal.com/en/performance-of-built-.. 2022. 1. 6.
반응형

티스토리툴바