중위 표기식의 후위 표기식 변환 방법
- 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
- 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
- 괄호를 제거한다.
재귀 호출
- 자기 자신을 호출하여 순환 수행되는 것
- 함수 호출은 메모리 구조에서 스택을 사용한다.(이름만 같은 다른 메서드)
- 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능저하가 발생한다.
- 일반적으로 기본 부분(Base case), 재귀 부분(Recursive case)로 구성된다.
- Base case : 재귀 호출에서 빠져 나가기 위한 조건
- Recursive case : 자신을 호출하는 부분 (Base case로 유도한다.)
- 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.
package test01;
public class Test1 {
public static void main(String[] args) {
// 반복문 <=> 재귀
// for(int i=0; i<5; i++) {
// System.out.println(i);
// }
// 재귀함수로 만들려면?
// 일반화 => n에 대한 문제 : 전체 문제 : f(n)
// 부분 문제: f(n-1), f(n-2), ... f(1), f(0)
// n : 숫자, 크기, 인덱스, 순서, ... 다양한 의미..
// 재귀함수는 두 가지 부분으로 나뉜다.
// - base case : 기저파트, 기저조건
// - recursive case : 유도파트, 유도조건...
rf(0, 5);
}
// recursive for
// i번째 인덱스 출력하고, 그 다음으로 넘어가는 메서드
// i 이후의 인덱스를 출력하는 메서드
static void rf(int idx, int end) {
// 기저 파트
if (idx == end) {
return;
}
// 유도 파트
// - 자기 단계에서 처리할 일을 처리하고
// - 나머지 일은 다음 부분 문제에게 위임한다.
System.out.println(idx);
rf(idx+1, end);
}
}
//
0
1
2
3
4
팩토리얼
package test01;
public class Test2 {
public static void main(String[] args) {
System.out.println(factorial(5));
}
public static int factorial(int n) {
if(n == 0) {
return 1;
}
// 기저 파트
// - 언제 끝날지?
if(n == 1) {
return 1;
}
// 유도 파트
return n * factorial(n-1);
}
}
//
120
피보나치 수열
package test01;
public class Test3 {
public static void main(String[] args) {
int n = 30;
long start = System.nanoTime();
System.out.println(fibo(n));
long end = System.nanoTime();
System.out.println(end - start);
//일반 재귀 피보나치 메소드
start = System.nanoTime();
System.out.println(mFibo(n));
end = System.nanoTime();
System.out.println(end - start);
}
// fibo(n) : 피보나치 수열에서 n번째 수
// 시간복잡도 O(2^n)
public static int fibo(int n) {
// 기저조건
if(n <= 1) {
return n;
} else {
// 유도조건
return fibo(n-1) + fibo(n-2);
}
}
static int[] memo = new int[100];
// 스태틱 블록
// - 클래스가 로딩될 때 클래스를 변수가 준비되고 난 후 자동으로 실행되는 블록
// - 한 클래스 안에 여러 개의 스태틱 블록을 넣을 수 있음
// - 주로 클래스 변수(static 변수)를 초기화할 때 사용
static {
memo[0]= 0;
memo[1] =1;
}
// memorization을 이용한 fibo : n번째의 피보나치 수를 구하는 메서드
// O(n)
public static int mFibo(int n) {
if(n >=2 && memo[n] == 0) {
// 아직 계산한 적이 없는 경우
// ->한번만 계산해서 배열에 넣는다
memo[n] = mFibo(n-1) + mFibo(n-2);
}
// 계산한 적이 있는 경우
return memo[n];
}
}
//
832040
3656100
832040
15900
