목록2025/02/04 (1)

wooing

[Softeer/DP] 징검다리

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