# [알고리즘] Stack ## 목차 [🧮계산기1 - 중위 표기법을 후위 표기법으로!](#🧮-계산기1) [🧮계산기2 - 후위 표기법을 계산해보자!](#🧮-계산기2) [🚀백트래킹(Backtracking)기법 - 해결할 수 없다면 되돌아가자! ](#🚀-백트래킹-(Backtracking)-기법) [🎯부분집합 - 부분집합 출력 코드를 구현하는 여러 방법을 알아보자! ](#🎯-부분집합-(Powerset)) [🙄순열 - 순열 생성을 구현하는 여러 방법을 알아보자! ](#🙄-순열) [💀분할 정복 알고리즘 - 분할 정복을 알아보자! ](#💀-분할-정복-알고리즘) [📑(연습문제) - 이제 연습문제를 풀어보자! ](#📑-(연습문제)-수식문자열을-후위식으로-변환) ---

## 🧮 계산기1

🗨️ 계산기1 내용 보기

계산식이 문자열로 주어질 때, 스택(Stack)을 이용해 결과 값을 계산 > 📢 **문자열 수식 계산의 일반적 방법** > > > > 1. 중위 표기법의 수식 → 후위 표기법으로 변경하여 **스택(stack)을 이용하여 계산** > >
### ✔ 중위표기법 → 후위표기법 변환 방법 1 1. 괄호를 사용하여 우선순위에 따라 수식의 연산자를 다시 표현함 2. 각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동시킴 3. 괄호를 제거함
### ✔ 중위표기법 → 후위표기법 변환 방법 2 (Stack 이용) 1. 입력 받은 중위 표기식에서 토큰을 읽음 - 토큰 : 퀵 정렬에서의 pivot과 같이, 주어진 입력에서 문자 하나하나를 '대상으로 함'을 의미하는 별칭(?)) 2. 토큰이 피연산자이면 토큰을 출력함 3. 토큰이 연산자(괄호 포함)일 때, 이 토큰이 스택의 **`top`** 에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 **`push()`** 하고, 그렇지 않다면 스택 **`top`** 의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 **`pop()`** 한 후 토큰의 연산자를 **`push()`** 함 (만약, **`top`** 에 연산자가 없다면 **`push()`** 함) 4. 토큰이 오른쪽 괄호’)’이면 스택 **`top`** 에 왼쪽 괄호 ‘**(**’가 올 때까지 스택에 **`pop()`** 연산을 수행하고 **`pop()`** 한 연산자를 출력함 (단, 왼쪽 괄호를 만나면 **`pop()`** 만 하고 출력하지는 않음) 5. 중위 표기식에 더 읽을 것이 없다면 중지하고, 더 읽을 것이 있다면 a번부터 다시 반복함 6. 스택에 남아 있는 연산자를 모두 **`pop()`** 하여 출력함 *(스택 밖의 왼쪽 괄호는 우선 순위가 가장 높으며, 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮음)* | 토큰 | isp(in-stack priority) | icp(in-coming priority) | | --- | --- | --- | | ) | - | - | | *, / | 2 | 2 | | +, - | 1 | 1 | | ( | 0 | 3 | ```python if (icp > isp) push() else pop() ```

## 🧮 계산기2

🗨️ 계산기2 내용 보기

후위 표기법의 수식을 스택을 이용하여 계산 1. 피연산자를 만나면 스택에 **`push()`** 함 2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 **`pop()`** 하여 연산하고, 연산 결과를 다시 스택에 **`push()`** 함 3. 수식이 끝나면, 마지막으로 스택을 **`pop()`** 하여 출력함 > 영상 넣기 > ![Untitled](https://github.com/user-attachments/assets/4dfe49b1-0a2a-4f12-b4ba-bb5e1a0b32bf)

## 🚀 백트래킹 (Backtracking) 기법

🗨️ 백트래킹 내용 보기

어떤 노드의 유망성(promising)을 점검한 후에 유망하지 않다고 판단되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드를 탐색하는 기법 -> *해를 찾는 도중에 막히면 (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법* - 백트래킹 기법은 최적화(optimization) 문제와 **결정(decision) 문제**를 해결할 수 있음 - **결정 문제** 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes/no로 답하는 문제 - 미로 찾기 - n-Queen 문제 - Map coloring - 부분 집합의 합(Subset Sum) 문제 등
### 🧷 백트래킹을 이용한 알고리즘 1. **상태 공간 트리의 깊이 우선 검색**을 실시 2. 각 노드의 **유망성**을 점검 3. 만일 해당 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속함
### 🗺 미로 찾기 (with Stack) 입구와 출구가 주어진 미로에서 4방향으로 이동하며 입구부터 출구까지의 경로를 찾는 문제 ![image](https://github.com/user-attachments/assets/aa06b0a1-2f77-4a1e-b9fe-14b7bd4b05b3)![image](https://github.com/user-attachments/assets/a5caba46-9931-4b9b-a6b6-df841d0c740d)![image](https://github.com/user-attachments/assets/26b77194-45d1-41d0-8d4c-1d9371de1117)![image](https://github.com/user-attachments/assets/364b93cd-6e67-4f8f-b2b8-6453b633c448)![image](https://github.com/user-attachments/assets/bceabea5-a799-4275-86e7-a22d0aff007b) *↑ 이 그림 이해 안 감*
```python # 일반 백트래킹 알고리즘 def checknode (v): # node if promising(v): if there is a solution at v: write the solution else: for u in each child of v: checknode(u) ```
#### ✔ 상태 공간 트리로 표현한 미로 찾기 ![image](https://github.com/user-attachments/assets/14d0734f-7079-45c7-bf17-cc16ff57c80d)

> **가지치기(Prunning)** > 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않음

## 🎯 부분집합 (Powerset)

🗨️ 부분집합 내용 보기

어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합을 powerset이라고 하며, 구하고자 하는 어떤 집합의 원소 개수가 n인 경우 부분집합의 개수는 $2^n$개이다. ### ✔ 비트맵을 활용한 부분집합 생성 및 부분집합의 합 구하기 ![image](https://github.com/user-attachments/assets/4579c6df-395d-4e82-bf71-bf11095552ae) ```python # 1. 다중 for문으로 구현하는 방법 bit = [0, 0, 0, 0] for i in range(2): bit[0] = i # 0번째 원소 for j in range(2): bit[1] = k # 1번째 원소 for k in range(2): bit[2] = k # 2번째 원소 for l in range(2): bit[3] = l # 3번째 원소 print(bit) # 생성된 부분집합 출력 # 2. 재귀함수로 구현하는 방법 def powerset(bit_arr, idx): if idx == N: print(bit_arr) return for i in range(2): bit_arr[idx] = i powerset(bit_arr, idx + 1) arr = [1, 2, 3, 4, 5] N = len(arr) powerset([None] * N ,0) ``` ![image](https://github.com/user-attachments/assets/69adff8e-e7a9-4211-aec4-abf64b5f7207)![image](https://github.com/user-attachments/assets/bb193c8d-eee6-48ea-b9d5-f90cd818682c)![image](https://github.com/user-attachments/assets/bd9e3527-5b0e-49a9-a510-e6ce464b7e4c)![image](https://github.com/user-attachments/assets/ea366cc3-1477-4be3-b8c4-f414c6bf31fc)
### ✔ 부분집합을 구하는 백트래킹(backtracking) 알고리즘 ![image](https://github.com/user-attachments/assets/55a27d0c-403c-4101-9072-90dda08bcbc8) ```python # a: 주어진 배열, k: 결정할 원소, n: 원소 개수 def backtrack(a, k, n): c = [0] * MAXCANDIDATES if k == n: process_solution(a, k) # 답이면 원하는 작업을 실행 for i in range(k): if a[i]: print(num[i], end = ' ') print() else: ncandidates = construct_candidates(a, k, n, c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k + 1, n) MAXCANDIDATES = 2 NMAX = 4 a = [0] * NMAX num = [1, 2, 3, 4] backtrack(a, 0, 3) ```

## 🙄 순열

🗨️ 순열 내용 보기

집합 {1, 2, 3}의 모든 순열을 생성해보자 ### ✔ 간단하게 순열 생성 ```python # 동일한 숫자가 포함되지 않았을 떄, 각 자리 수별로 loop문을 이용하여 구현 for i1 in range(1, 4): for i2 in range(1, 4): if i2 ! = i1: for i3 in range(1, 4): if i3 ! = i1 and i3 ! = i2: print(i1, i2, i3) ```
### ✔ 백트래킹(Backtracking)을 이용하여 {1, 2, 3, ..., NMAX}에 대한 순열 생성 ```python def backtrack(a, k, n): c = [0] * MAXCANDIDATES if k = = n: for i in range(0, k): print(a[i], end = " ") else: ncandidates = construct_candidates(a, k, n, c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k + 1, n) def construct_candidates(a, k, n, c): in_perm = [False] * (NMAX + 1) for i in range(k): in_perm[a[i]] = True ncandidates = 0 for i in range(1, NMAX + 1): if in_perm[i] = = False: c[ncandidates] = i ncandidates += 1 return ncandidates NMAXCANDIDATES = 3 NMAX = 3 a = [0] * NMAX backtrack(a, 0, 3) ``` ![image](https://github.com/user-attachments/assets/946cfbf3-e4d3-4620-b373-56b9ce590845)

## 💀 분할 정복 알고리즘

🗨️ 분할 정복 알고리즘 내용 보기

### ✔ 거듭 제곱(Exponentiation) ```python def Power(Base, Exponent): if Base == 0: return 1 result = 1 # Base^0 = 1 for i in range(Exponent): result *= Base return result ``` ![image](https://github.com/user-attachments/assets/2e5836b1-693f-4ccb-8455-2144468cb732) ```python def Power(Base, Exponent): if Exponent == 0 or Base == 0: return 1 if Exponent % 2 == 0: NewBase = Power(Base, Exponent / 2) return NewBase * NewBase else: NewBase = Power(Base, (Exponent - 1) / 2) return (NewBase * NewBase) * Base ```

## 📑 (연습문제)

🗨️ 연습문제 풀어 보기

- **수식문자열을 후위식으로 변환하시오.** - 2 + 3 * 4 / 5 - 내 답안: 2 3 4 * 5 / + - 2 + 3 * 4 + 5 - 내 답안: 2 3 4 * + 5 + - **{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}의 powerset 중 원소의 합이 10인 부분집합을 구하시오.** * 내 답안: - **순열 문제에서의 가지치기** - [SWEA] 4881. 배열 최소 합 *(순열 생성 과정을 그려보시오)*