인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

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

김란영님의 프로필 이미지
김란영

작성한 질문수

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

3. 이진트리순회(DFS: 깊이우선탐색)

코드 작성 중 궁금한 점이 있어 질문 남깁니다

해결된 질문

작성

·

231

0

function solution(n){
                let answer = '';
                let stack = [];

                if(n>7){
                    return;
                }else{
                    stack.push(n);
                    // console.log('>>>>>', stack);
                    solution(n * 2);
                    solution(n*2+1);
                }

                return stack;
            }

// output : [1]
// console.output : >>>>> [1]
// console.output : >>>>> [2]
// console.output : >>>>> [4]
// console.output : >>>>> [5]
// console.output : >>>>> [3]
// console.output : >>>>> [6]
// console.output : >>>>> [7]

저는 우선 function을 두번 사용하지 않고 한번에 사용하려고 하는데 저기서 콘솔을 찍으면 순서대로 출력은 되지만, stack에는 [1] 첫번째 값만 담기는데 혹시 왜 그런지 이유를 알 수 있을까요?

답변 2

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

재귀가 호출될때마다 stack자료구조를 새로 선언하면서 또 리턴까지 하면 안됩니다.  아래 코드처럼 재귀함수 밖에서 전역으로 한 번 선언하고 그 자료구조에 push를 해야합니다. 그리고 재귀함수가 끝나고 나면 solution 함수가 stack을 리턴을 하는 구조여야 합니다. 

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(n){
                let stack=[];
                function DFS(v){
                    if(v>7) return;
                    else{
                        stack.push(v);
                        DFS(v*2);
                        DFS(v*2+1);
                    }
                }
                DFS(n);
                return stack;
            }

            console.log(solution(1));
        </script>
    </body>
</html>

2. DFS를 inner 함수로 만드는 것은 제 스타일입니다. 또한 앞으로 복잡한 문제를 풀다보면 solution 함수안에서 재귀함수와 함께  다른  함수를 호출하는 복잡한 코드도 작성할 수 있기 때문에 저는 그렇게 합니다.

그리고 위에 코드도 DFS를 inner 함수로 하지 않아서 생기는 문제라고 볼 수도 있습니다.

김란영님의 프로필 이미지
김란영
질문자

감사합니다!! 그럼 제 코드는 stack을 재귀로 호출할 때마다 리셋이 되어서 담고 있었던거군요!! 

그점까지는 생각하지 못했는데! 이번에 확실히 알게된것 같습니다!

그리고 inner함수 쓰는 이유도 확실히 알게 된 것 같습니다! 어쩐지 문제를 풀수록 하나의 함수로 하기에는 벅차더라구요...ㅎㅎ 앞으로는 inner함수를 사용해서 재귀를 돌려야할 것 같네요 :)

답변감사합니다!!

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

제가 실행시켜보게 본인의 전체코드를 올려주시면 좋겠습니다.

김란영님의 프로필 이미지
김란영
질문자

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            // DFS 
            // 1~7까지
            
            //       1
            //    2      3
            //  4   5  6   7

            // 전위 : 1 2 4 5 3 6 7
            function solution(n){
                let answer = '';
                let stack = [];

                if(n>7){
                    return;
                }else{
                    stack.push(n);
                    console.log('>>>>>', stack, n);
                    solution(n * 2);
                    solution(n*2+1);
                }

                return stack;
            }
            
           
            console.log(solution(1));
        </script>
    </body>
</html>

아 네!! 이게 제 전체 코드입니다!

출력을 하면 stack에 담겨지지 않고 첫번째 값인 [1]만 출력이 되더라구요!

김란영님의 프로필 이미지
김란영
질문자

그리고 재귀함수를 할 때 function을 두개로 나누어야 하는 이유도 있을까요?

solution 함수 안에 DFS 함수를 만든 이유요!

이 질문도 답변해주시면 감사하겠습니다!!

김란영님의 프로필 이미지
김란영

작성한 질문수

질문하기