📖 Stack 2

📌 계산기

✅ 계산기

• 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.
  ex> 5 + 8 * 2 - (3 - 2 ^ 2)

1. 중위 표기법의 수식을 후위 표기법으로 변경 (스택 활용)

2. 후위 표기법의 수식을 스택을 이용하여 계산한다.

중위표기법 (infix notation) : 연산자를 피연산자의 가운데 표기하는 방법
ex> A + B

후위표기법 (postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법
ex> AB+

ex> (중위 표기법) A + B C => (후위 표기법) ABC+
(우선순위가 높은 연산자부터 후위에 붙인다.)

• 둘의 차이점 : 연산자의 순서가 정렬됨. ( + => + )

✅ 변환 방법 1

1. 중위 표기식의 후위 표기식 변환 방법 1

• 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현

  • 동일한 연산 우선순위일 경우 왼쪽에 있는 연산이 더 우선

• 각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동시킴

• 괄호 제거

ex> A*B-C/D

1단계 : ((A*B) - (C/D))

2단계 : ((A B) * (C D)/)-

3단계 : AB*CD/-

✅ 변환 방법 2

• 스택을 활용한 변환법

1. 입력 받은 중위 표기식에서 토큰을 읽음

2. 토큰이 피연산자라면 토큰 출력

3. 토큰이 연산자(괄호 포함)일 때 토큰이 스택의 top에 저장되어 있는 연산자보다 우선 순위가 높다면 스택에 push
   그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때 까지 스택에서 pop한 후 토큰의 연산자를 push
   만약 top에 연산자가 없다면 push

4. 토큰이 오른쪽 괄호 ) 이면 스택 top에 처음으로 왼쪽 괄호(가 올 때까지 스택에 pop 연산을 수행하고 pop한 연산자 출력
   왼쪽 괄호를 만나면 pop만 하고 출력 X

5. 중위 표기식에 더 읽을 것이 없으면 중지.
   더 읽을 것이 있으면 1부터 재반복

6. 스택에 남아있는 모든 연산자 pop 및 출력

스택 밖 왼쪽 괄호 (는 우선 순위가 가장 높고, 스택 안 왼쪽 괄호는 우선 순위가 가장 낮다.

✅ 후위 표기법의 수식을 스택을 이용하여 계산

1. 피연산자를 만나면 스택에 push

2. 연산자를 만나면 필요한 만큼 피연산자를 스택에서 pop하고(대부분 2개) 연산하고,
   연산 결과를 다시 스택에 push한다

3. 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

중위 -> 후위 : 연산자의 스택
후위표기법 계산 : 피연산자의 스택

📌 재귀호출

✅ 재귀 호출

• 자기 자신을 호출하여 순환 수행되는 것

• 함수 호출은 메모리 구조에서 스택을 사용한다.

  • 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능 저하 발생

• 일반적으로 기본 부분(Base case), 재귀 부분(Recursive case)로 구성된다.

  • Base case : 재귀 호출에서 빠져 나가기 위한 조건
  • Recursive case : 자신을 호출하는 부분 (Base case로 유도)

• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 좋음.

✅ 예시 - 팩토리얼

• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성 가능

ex> factorial

n! = n * (n-1)!

✅ 예시 - 피보나치 수열

• 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열

• F0 = 0, F1 = 1

• Fi = Fi-1 | Fi-2 for i>=2

public static int fibo(int n) {
	if(n <= 1)
    	return n;
    else
    	return fibo(n-1) + fibo(n-2);
}

✅ Memoization

• 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

• Dynamic Programming (DP)의 핵심 기술

• 엄청난 중복 호출이 존재 할 수 있다.

• 앞의 피보나치 에서 fibo(n)의 값을 계산하자마자 저장하면 (memoize), 실행시간을 O(N)으로 줄일 수 있다.

memo를 위한 배열을 할당하고, 모두 0으로 초기화
memo[0]을 0으로 memo[1]은 1로 초기화

public static int mFibo(int n) {
	if(n>=2 && memo[n] == 0)
    	memo[n] = mFibo(n-1) + mFibo(n-2);
        
    return memo[n];
}