계단오르기

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

1. 계단오르기

작성

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int cnt = 0;

    public static void dfs(int sum, int n) {
        int[] arr = {1, 2};
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum == n) {
                cnt++;
                sum -= arr[i];
            } else {
                if (sum < n) dfs(sum, n);
                sum -= arr[i];
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine());
        dfs(0, n);
        System.out.println(cnt);
    }
}

dp를 잘 몰라서 자력으로 dfs 방식으로 풀었는데 그닥 좋지 않은 접근일까요...?

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

거의 모든 출제자가 dp 문제를 DFS 풀면 100% 타임리밋 나도록 문제와 테스트케이스를 설계합니다.

dp 문제는 다이나믹으로 푸는 습관을 들여야 합니다. DFS로 푸는 습관을 들였다가는

dp 문제를 봐도 DFS로 밖에 생각나지 않습니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

계단 오르기 문제를 DFS(Depth First Search)로 풀이하는 것은 가능합니다. 그러나, 이 방법은 계산량이 많아질 수 있는 문제를 가지고 있습니다. DFS 방식으로 모든 가능한 경로를 탐색하려다 보니, 계단 수가 커질수록 시간 복잡도가 기하급수적으로 증가할 수 있습니다. 따라서, DFS는 작은 입력에 대해선 잘 작동하지만, 큰 입력에서는 비효율적일 수 있습니다.

계단 오르기 문제는 일반적으로 동적 프로그래밍(DP) 기법을 사용하여 해결하는 것이 효율적입니다. DP를 사용하면 이전 계산된 결과를 활용하여 중복 계산을 줄일 수 있습니다. 이를 통해 시간 복잡도를 많이 개선할 수 있습니다.

관련 질문 URL:
- 계단오르기 질문
- 이 질문에서는 DFS로 문제를 해결했을 때의 한계점에 대해 논의하고 있으며, 계단의 수가 많아질수록 시간초과 문제가 발생할 수 있음을 다루고 있습니다.

지속적으로 동적 프로그래밍 기법을 연구해보는 것도 좋은 접근입니다. 필요시 DP에 대한 기초와 응용을 다룬 자료를 학습하시면 문제를 해결하는 데 많은 도움이 될 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

계단오르기