Java 코딩테스트 공부/Java 알고리즘 공부

Recursive, Tree, Graph(DFS, BFS 기초) 1 - 재귀

2022. 11. 9. 16:54

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84#

 

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성

www.inflearn.com

 

재귀함수

-> 자기 자신을 호출하는 함수

 

스택 프레임에 대한 개념 :

스택프레임을 이용한 백트래킹

예전에 C++로 스택프레임에 대해 공부하며 그렸던 그림인데 다시 보도록 하자.

(위 그림은 대략 이런 구조로 돌아간다는 거지 개념을 정확히 설명한 것은 아니다.)

이렇게하면 1 2 3 순서로 출력된다.

recur(x-1); 를 출력 뒤로 두면 3, 2, 1 순서로 출력된다.

 

스택 프레임에 대한 보다 정확한 개념은 위 그림을 참고하자

 

 

 

문제 1 :

자연수 N이 입력되면 재귀함수 이용해 1부터 N까지 출력하라 (3<=N<=10)

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	public void recur(int n) {
		if (n == 0) return;
		else {
			recur(n-1);
			System.out.print(n+" ");
		}
	}
	public static void main(String[] args) throws IOException {
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		br.close();
		T.recur(n);
	}
}

 

 

문제 2 :

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하시오.

단, 재귀함수를 이용해 출력하여야 한다.

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	public void recur(int n) {
		if (n == 0) return;
		else {
			recur(n / 2);
			System.out.print((n%2));
		}
	}
	public static void main(String[] args) throws IOException {
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		br.close();
		T.recur(n);
	}
}

 

 

문제 3 :

팩토리얼 문제

자연수 N이 입력되면 N!을 구하는 프로그램을 작성하시오.

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	public int recur(int n) {
		if(n == 1) return 1;
		else return n*recur(n-1);
	}
	public static void main(String[] args) throws IOException {
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		br.close();
		bw.write(String.valueOf(T.recur(n)));
		bw.flush();
		bw.close();
	}
}

 

풀이 :

1을 리턴받을때 스택에 있던 것들이 pop() 된다.

D(1)부터 pop() 된다.

 

문제 4 : 

피보나치 재귀 (+ memoization)

N은 피보나치 수열의 총 항의 수이다.

N이 입력되면 해당 수 만큼 피보나치 수열을 출력하는 프로그램을 작성하여라.

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	static int[] fibo;
	public int recur(int n) {
		if (fibo[n] > 0) return fibo[n];
		if (n == 1) return fibo[n] = 1;
		else if (n == 2) return fibo[n] = 1;
		else return fibo[n] = recur(n-2) + recur(n-1);
	}
	public static void main(String[] args) throws IOException {
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		br.close();
		fibo = new int[n+1];
		T.recur(n);
		for(int i=1; i<=n; i++) bw.write(String.valueOf(fibo[i]+" "));
		bw.flush();
		bw.close();
	}
}

 

풀이 :

if (fibo[n] > 0) return fibo[n];

코드로 인해 cut dege가 일어나 복잡도가 많이 개선된다.

 

 

 

+ 23년 2월 7일 추가

 

자바 코드

import java.util.*;
import java.io.*;
public class Main {
	// 재귀 + memoization 이용한 풀이 (cut edge)
	static int[] fibo;
	public int recur(int n) {
		if (fibo[n] > 0) return fibo[n];
		if (n == 1) return fibo[n] = 1;
		else if (n == 2) return fibo[n] = 1;
		else return fibo[n] = recur(n-2) + recur(n-1);
	}
	public static void main(String[] args) throws IOException {
	    Main T = new Main();
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		br.close();
		fibo = new int[n+1];
		T.recur(n);
		bw.write(String.valueOf(fibo[n]));
		bw.flush();
		bw.close();
	}
}

 

파이썬 코드

import sys
# 재귀 + memoization 이용한 풀이 (cut edge)
def recur(n):
  if fibo[n] > 0 : return fibo[n]
  if n == 1 :
    fibo[n] = 1
    return fibo[n]
  elif n == 2 :
    fibo[n] = 1
    return fibo[n]
  else :
    fibo[n] = recur(n-2) + recur(n-1)
    return fibo[n]

n = int(sys.stdin.readline())
fibo = [0 for i in range(n+1)]

recur(n)
print(fibo[n])

 

자바코드를 파이썬으로 작성할 시

if (n == 1) : return fibo[n] = 1 와 같이 코드를 작성하게 되면 오류가 발생하므로

if n == 1 :
    fibo[n] = 1
    return fibo[n]

와 같이 작성해주어야 한다.

 

'Java 코딩테스트 공부 > Java 알고리즘 공부' 카테고리의 다른 글

Recursive, Tree, Graph(DFS, BFS 기초) 3 - 이진트리, 상태트리 BFS  (0) 2023.03.15
Recursive, Tree, Graph(DFS, BFS 기초) 2 - 이진트리, 부분집합 DFS  (0) 2022.11.12
Java 정렬, 이분검색과 결정알고리즘 3  (0) 2022.11.04
Java 정렬, 이분검색과 결정알고리즘 2  (0) 2022.09.03
Java 정렬, 이분검색과 결정알고리즘 1  (0) 2022.09.02
'Java 코딩테스트 공부/Java 알고리즘 공부' 카테고리의 다른 글
  • Recursive, Tree, Graph(DFS, BFS 기초) 3 - 이진트리, 상태트리 BFS
  • Recursive, Tree, Graph(DFS, BFS 기초) 2 - 이진트리, 부분집합 DFS
  • Java 정렬, 이분검색과 결정알고리즘 3
  • Java 정렬, 이분검색과 결정알고리즘 2
daramG
daramG
dotori Java
daramG
다람쥐의 개발 블로그
daramG
전체
오늘
어제
  • 분류 전체보기 (193)
    • Java 코딩테스트 공부 (67)
      • Java 알고리즘 공부 (37)
      • Java 백준 문제풀이 (27)
      • Java 코테 나만의 팁 (3)
    • SQL Study (0)
      • Programmers SQL 문제풀이 (0)
      • SQLP 준비 (0)
    • 웹 개발 지식 정리 (0)
      • Servlet (0)
      • Java 정리 (0)
    • 자바 스프링 (45)
      • 스프링 공부 (4)
      • 스프링 게시판 프로젝트 (6)
      • 부트 블로그 JPA 프로젝트 (30)
      • react & springboot (5)
      • 스프링 오류창고 (0)
      • 리액트 + 스프링 프로젝트 (0)
      • pf (0)
      • pfError (0)
    • React (6)
      • React 정리 (3)
      • React 오류 창고 (3)
    • C++ 코딩테스트 공부 (중단) (20)
      • c++ 백준 문제풀이 (15)
      • c++ 알고리즘 공부 (5)
    • Unity (3)
      • Unity 공부 (3)
    • WebRTC (2)
      • WebRTC 강의학습 정리 (0)
      • WebRTC 프로젝트 (1)
    • 김영한님의 스프링 강의 학습 (10)
      • 스프링 강의 목차 (1)
      • 인텔리제이 & 스프링 기초 (1)
      • 스프링 핵심 원리 (8)
    • 전공 지식 정리 (40)
      • interview (0)
      • Java (0)
      • 운영체제 (4)
      • 데이터베이스 설계 (10)
      • 소프트웨어 공학 (3)
      • 유닉스 (14)
      • 디지털 논리회로 (0)
      • 인공지능 (7)
      • js (0)
      • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 김영한 스프링 강의
  • C++ 알고리즘
  • 백준 c++
  • 스프링 공부
  • 유닉스
  • java 알고리즘
  • 인공지능
  • 스프링부트 블로그 프로젝트
  • 데이터베이스 설계
  • Java 코테 나만의 팁
  • 김영한 스프링 입문
  • 코테 알고리즘
  • 디지털 논리회로
  • Java 백준 문제풀이
  • 스프링부트 프로젝트
  • 김영한의 스프링 핵심 원리
  • Unity 공부
  • 노마드코더의 zoom클론코딩
  • 무서운 이야기
  • 스프링 프로젝트
  • 운영체제
  • React&Spring 강의수강
  • java
  • 부트 jpa 게시판 프로젝트

최근 댓글

최근 글

hELLO · Designed By 정상우.
daramG
Recursive, Tree, Graph(DFS, BFS 기초) 1 - 재귀
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.