[알고리즘 강의]JS 알고리즘 - DFS 팩토리얼

최근 회사에서 메신저 프로그램을 열심히 개발하고 난 후, 다시 코딩 강의를 복습하기로 결정했습니다. 하지만 오랜만에 알고리즘 문제를 풀어보니, 생각보다 잘 풀리지 않는 것 같더군요.

 

처음엔 혼자서 문제를 풀지 못하고, 시작조차 못하는 문제들이 많아져서 자존심이 상했었습니다.

하지만, 그러한 자괴감을 느끼기보다는 여러 번 복습을 통해 익숙해지는 것도 좋은 학습 방법이라는 조언을 들었습니다.

그래서 안심하고 이 방식을 따르기로 했습니다. 공부에 정답은 없으니까요.

 

천재도 아니고, 안 풀리는 문제가 갑자기 풀리지 않습니다.

무엇이든 시도해보는 것이 중요하죠.

이 방법으로 알고리즘을 공부하는 것이 얼마나 효과적인지에 대한 후기는 나중에 한 번 포스팅해보고 싶습니다.

 

그래서 다시 기본을 다질 겸 풀어본 문제는 기본적인 팩토리얼 문제였습니다.

DFS(깊이 우선 탐색)를 사용해서 해결하면 되는 문제입니다.

 

 

문제 설명

 

[문제]
자연수 N을 입력하면 N!값을 구하세요.
N! = n*(n-1)*(n-2)*.....*2*1입니다.
만약 N=5라면 5!=5*4*3*2*1=120입니다.

 

 

코드 구현과 이해

 

어쨌든, 저의 문제 해결 방법은 다음과 같습니다.

function solution(n){         
    let answer;
    function DFS(n){
        if(n===1) return 1;
        else return n*DFS(n-1); 
    }
    answer=DFS(n);
    return answer;
}

 console.log(solution(5));

 

 

이 코드는 팩토리얼을 계산하는 재귀 함수를 이용한 예시입니다. "팩토리얼"이란 1부터 어떤 수(n)까지의 모든 정수의 곱을 의미합니다. 예를 들어, 5의 팩토리얼은 5 * 4 * 3 * 2 * 1입니다.

이전에 DFS에 대한 개념을 먼저 알아야 할 필요가 있습니다.

 

 

DFS 개념 

 

- DFS, 즉 깊이 우선 탐색은 그래프 이론에서 매우 중요한 개념입니다. 이 방법은 한 노드에서 시작하여 가능한 멀리 있는 노드를 우선적으로 탐색하는 전략을 사용합니다. 이는 미로 탐색이나 트리 구조에서의 깊이 탐색과 같은 문제에 효과적입니다.

DFS의 기본 원리는 다음과 같습니다:

• 노드를 방문하고, 방문한 노드를 기록합니다.
• 현재 노드에 인접한 방문하지 않은 노드로 이동합니다.
• 더 이상 방문할 노드가 없을 때까지 이 과정을 반복합니다.
• 더 이상 방문할 노드가 없으면 이전 노드로 돌아가 새로운 경로를 탐색합니다.

이러한 방식으로 DFS는 모든 노드를 체계적으로 탐색할 수 있으며, 특히 순환 구조나 연결된 경로를 찾는 데 유용합니다. 또한, 재귀적 구현이 가능하여 코드 작성이 상대적으로 간단할 수 있습니다.

하지만, DFS는 탐색 과정에서 사용하는 메모리 양이 클 수 있으며, 최단 경로를 보장하지 않는다는 단점이 있습니다.

 

 

알고리즘 설계

 

여기서 DFS 함수는 팩토리얼을 계산합니다. DFS(n)은 n이 1이 될 때까지 자신을 호출하며, 각 단계에서 n을 곱합니다.

이 과정을 도식화해 보겠습니다:

1. solution(5)가 호출됩니다.
2. DFS(5)가 호출됩니다
3. 5 * DFS(4)가 되고, DFS(4)를 호출합니다.
4. 4 * DFS(3)가 되고, DFS(3)를 호출합니다.
5. 3 * DFS(2)가 되고, DFS(2)를 호출합니다.
6. 2 * DFS(1)가 되고, DFS(1)를 호출합니다.
7. DFS(1)은 1을 반환합니다.
8. 이제 모든 호출이 마무리되며, 각 단계의 반환 값들이 곱해집니다.

2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
5 * 24 = 120

    9. 최종적으로 solution(5)는 120을 반환합니다.

 

이 과정은 팩토리얼 계산의 핵심 원리인 "각 숫자를 차례대로 곱해나가는 것"을 잘 보여줍니다.

 

 

 

 

DFS는 깊이 우선 탐색으로, 문제를 해결하기 위해 가장 깊은 부분까지 탐색하는 방법입니다. 이 방법은 문제를 더 작은 단위로 쪼개어 해결하고, 그 해결책을 결합하여 최종 결과를 도출하는 데 매우 효율적입니다. 팩토리얼 문제에서 DFS를 사용하면 간결하고 명확한 해결책을 제시할 수 있습니다.

 

이렇게 DFS에 대해 좀 더 깊이 이해하고, 문제 해결에 적용해보는 것은 코딩 능력을 향상시키는 데 중요한 단계입니다. 오늘 다룬 팩토리얼 문제와 같은 간단한 예제부터 시작하여, 점차 더 복잡한 문제에 DFS를 적용해보시길 추천합니다.