시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
"1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 세는 방법"문제는 사용자가지면에 서 있다는 것을 나타냅니다. 이제 계단 끝에 도달해야합니다. 1, 2, 3 단계 만 점프 할 수 있다면 끝까지 도달 할 수있는 방법은 얼마나 될까요?
차례
예
2
2
설명
지상에서 직접 2 단계에 도달하거나 먼저 2 층에 도달 한 후 앞으로 이동하기 때문에 두 가지 방법이 있습니다.
접근
문제는 우리가 지상에서 시작하도록 계단 끝에 도달하는 총 다른 수의 방법을 묻습니다. 따라서 계단에는 2 개의 계단이 있습니다. 그런 다음 두 가지 가능한 방법이 있습니다. 바로 2 단계로 이동하거나 2 단계에서 1 단계로 이동 한 다음 2 단계로 이동하는 것입니다. 마찬가지로, 1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 계산해야합니다.
순진한 접근 방식은 가능한 모든 방법을 생성 한 다음 계산하는 것입니다. 그러나이 접근 방식은 시간이 많이 걸립니다. 따라서 시간 복잡성을 줄이려면 몇 가지 다른 방법을 생각해야합니다. 순진한 접근 방식에서 논의한 방법은 재귀 0 단계부터 시작할 수있는 솔루션입니다. 그런 다음 각 재귀 호출에서 i + 1, i + 2 및 i + 3 단계로 이동합니다. n 번째 단계에 도달하면 카운터를 증가시킵니다. 이렇게하면 카운터는 n 번째 단계에 도달하는 방법의 수를 저장합니다. 그러나이 단계는 동일한 문제를 반복해서 재 계산합니다. 따라서이 솔루션을 최적화하기 위해 동적 프로그래밍.
동적 프로그래밍 솔루션에서 우리는 i 번째 단계에 있다고 생각합니다. 그러면 i 번째 단계에 도달하는 방법의 수는 i-1 단계, i-2 단계 또는 i-3 단계입니다. 그래서 공식적으로 말하면,이 재귀 공식을 사용하여 방법 [i] = 방법 [i-1] + 방법 [i-2] + 방법 [i-3]. 우리는 우리의 문제를 해결할 것입니다.
암호
1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 계산하는 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
int dp[n+1];
// base case
dp[0] = 1;
for(int i=1;i<=n;i++){
dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
((i-2)>=0 ? dp[i-2] : 0) +
((i-3)>=0 ? dp[i-3] : 0);
}
cout<<dp[n];
}
5
13
1, 2 또는 3 단계를 사용하여 n 번째 계단에 도달하는 방법을 계산하는 Java 코드
import java.util.*;
class Main{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int dp[] = new int[n+1];
// base case
dp[0] = 1;
for(int i=1;i<=n;i++){
dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
((i-2)>=0 ? dp[i-2] : 0) +
((i-3)>=0 ? dp[i-3] : 0);
}
System.out.print(dp[n]);
}
}
5
13
복잡성 분석
시간 복잡성
의 위에), n 번째 단계까지 루프를 실행해야하기 때문입니다. 따라서 동적 프로그래밍 측면에서 0에서 n까지의 단일 상태가 있었고 전환 비용은 O (1)입니다. 따라서 시간 복잡도는 선형입니다.
공간 복잡성
의 위에), 1D DP 배열을 만들어야하기 때문입니다. 솔루션의 공간 복잡성은 선형입니다.
