wooing

문제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)로 시간초과를 해결할 수 있다..

문제https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai해결방법해당 문제는 DP문제로 점화식을 세우는것이 중요한 문제이다. 내가 생각한 점화식은 다음과 같다.현재 높이보다 낮은 칸들의 최대값 + 1문제를 풀고 다른 사람들의 풀이법을 보니 나와 조금 달랐다. 다른 사람들은 이 문제를 최장증가부분수열 해결 방법으로, dp[]에 해당 칸을 밟았을때와 안 밟았을때의 max값을 저장하는 방식으로 dp를 구현하였다. 그리고 내 해결방법의 오류나 단점을 생각해보면 다음과 같다.메모리 문제실제로 입력조건에 맞춰 int[100000001]로 배열을 선언하였더니 메모리초과가 발생하여 Map으로 변경하였다.시간복잡도다른 사람들의 풀이는 O(N)이지만..