DFS

문제https://www.codetree.ai/trails/complete/curated-cards/test-puyo-puyo/description Code Tree | Learning to Code with ConfidenceA super-comprehensive, meticulously arranged Coding Learning Curriculum engineered by Algorithm Experts composed of former International Olympiad in Informatics (IOI) medalists.www.codetree.ai 해결방법해당 문제를 해결하려면 칸을 전체 순회하며 블럭의 수, 블럭의 크기를 구해야한다. 이때 전체 순회를 하며 블럭(상하좌우 인접한 칸들이..

문제https://softeer.ai/practice/7649 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 해결방법해당 문제는 DFS로 그래프 순환 및 LCS구현을 통해 해결할 수 있는 문제이다. DFS는 인접리스트를 순회하는 방법으로 쉽게 구현 가능하다. 그러나 LCS를 기본 LCS로 구현하면 O(N^3)의 시간복잡도를 가지기때문에 시간초과가 발생한다.우선 LCS의 일반적인 코드는 아래와 같다. for (int i = 1; i  위와같이 구현하게되면, 이미 구해진 LCS값을 매번 초기화하게되어 시간초과가 발생한다. 이를 해결하기위해 dp배열을 재활용하는 방식으로 LCS를 구한다. 재활용 하는 방법은 아래와 같다. 해당 방법으로 구현하면 O(N^2)로 시간초과를 해결할 수 있다..