8장은 DFS를 활용한 문제이다. DFS는 스택의 원리를 사용해서 풀 수 있는 알고리즘이다. 재귀함수가 스택 자료구조 원리를 사용하기 때문에, 주로 DFS에서는 스택을 따로 생성하지 않고 재귀함수로 문제를 해결한다.
문제
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.
[입력설명]
첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.
[출력설명]
첫째 줄에 출력한다.
입력예제 1
3
출력예제 1
123
문제 풀이
예습이론
재귀함수는 '스택' 자료구조 원리를 사용한다. 따라서, 스택의 원리를 사용해서 풀 수 있는 DFS는 따로 스택을 구현하지 않고, 재귀함수를 사용해서 풀 수 있다.
재귀함수는 아래와 같은 형태이다.
function DFS(L){
DFS(L-1); //DFS를 호출(무한반복)
}하지만 위와 같은 형태는 무한반복되는 형태이기 때문에, 함수 종료구문도 있어야한다. 주로 if문에는 종료의 조건(return), else문은 재귀의 조건이다.
function DFS(L){
if(종료조건) return; //return은 함수종료의 의미
else DFS(L-1); //DFS를 호출(재귀함수 호출)
}재귀의 원리를 스택에 표현하면 아래와 같다.(코드와 함께 보기)
코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n){
//DFS(깊이 우선탐색 함수) 만듦, L(level) (이름 상관 없음)
function DFS(L){
if(L===0) return; //무한반복 막음 (DFS(0)이 되었을 때 종료 )
else{
DFS(L-1); //재귀함수(자기 자신 호출)
console.log(L);
//DFS(L-1) 이 위치에 들어가면 3, 2, 1
}
}
DFS(n)
}
solution(3);
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/15