석박사 (63) 썸네일형 리스트형 Leetcode Dynamic Programming 정복 커리큘럼 좋은 솔루션을 접하지 않은 채로 여러 문제를 풀어보다보면 논리가 계속 꼬이고 코드가 복잡해지는것을 느낄 수 있을 것이다. 아래 영상은 Dynamic programming 문제들을 5가지 패턴으로 유형화하여 제시한다. 생각의 논리 전개는 다음과 같이 진행하는게 좋다. Step1. 간단한 예시를 이용해 Brute-force decision tree 그려보기 -- 이때 주로 time complexity 가 O(n). 그 후 타임아웃이 뜰 것을 염두에 두면서 recursive function을 구현해보기. Step2. 그린 Decision tree 예시를 보면서 겹치는 연산을 찾아내기. 이를 memoization 할 방법을 고민해보기. 1-d array 일수도, 2-d array 일 수도 있다. 인덱싱에서 꼬이.. strategyproofness 란? Strategic dominance 란? 게임이론에서, 어떤 전략이 dominance(우세) 하다고 하면 다른 참여자들의 선택에 무관하게 어떤 참여자에게 한 전략이 다른 전략보다 항상 좋은 결과를 가져다주는 경우를 일컫는다. In game theory, strategic dominance (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The opposite, intransitivity, o.. VRP state-of-the-art solver - LKH, HGS 대부분의 전문가들의 LKH (링컨핸휴리스틱)는 popular 한 적당히 좋은 솔버라 생각함. http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3_REPORT.pdf http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3 (Keld Helsgaun)LKH-3 is an extension of LKH-2 for solving constrained traveling salesman and vehicle routing problems. The extension has been desribed in the report Extensive testing on benchmark instances from the literature has sho.. INFORMS 2022 세션에서 배운 것 정리 Optimizing Lane Reversal Using a Global Optimization Approach piecewise affline approximation 을 이용해서 convex optimization 으로 변환한게 인상깊었다. 이 발표자가 여러 접근법중에 왜 convex approximation 이 가장 흥미롭다고 말했는지 살펴볼 예정. 워낙 결과 표나 그래프가 좋아서 어떻게 서술했는지 살펴보는것도 도움이 될 것 같았다. https://www.sciencedirect.com/science/article/pii/S0968090X22002595 Optimizing lane reversals in transportation networks to reduce traffic congestion: .. 이전 1 2 3 4 5 6 ··· 16 다음