목록2025/02/07 (1)

wooing

[Softeer/DP, DFS] 효도 여행

문제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)로 시간초과를 해결할 수 있다..
알고리즘 2025. 2. 7. 17:11
이전 Prev 1 Next 다음