중위표기법 -> 후위표기법
- 입력받은 중위표기식에서 토큰을 읽음
- 토큰이 피연산자이면 토큰을 출력
- 토큰이 연산자(괄호포함)일 경우
1) 우선순위가 높으면 -> 스택에 push
2) 우선순위가 안 높으면 -> 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자를 push
3) 만약 top에 연산자가 없으면 -> push - 토큰이 오른쪽 괄호')'일 경우
1) 스택 top에 왼쪽 괄호'('가 올 때까지 스택에 pop 연산을 수행
2) pop한 연산자를 출력
3) 왼쪽 괄호를 만나면 pop만 하고 출력하지는 않음. - 중위표기식에 더 읽을 것이 없다면 중지, 더 읽을 것이 있다면 1부터 반복
- 스택에 남아있는 연산자를 모두 pop 하여 출력
- 스택 밖의 왼쪽 괄호는 우선 순위가 가장 높으며,
- 스택 안의 왼쪽 괄호는 우선 순위가 가장 낮음.
백트래킹
- 해를 찾는 도중에 '막히면', 되돌아가서 다시 해를 찾아가는 기법
- 미로, n-Queen, Map coloring 등이 있음.
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임. (깊이우선탐색(DFS)은 모든 경로를 추적함.)
- 가지치기(Prunning)
- 불필요한 경로의 조기 차단
- N! 가지의 경우의 수를 가진 문제에 대해 백트래킹에 가하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간을 요하므로 처리 불가능. (DFS는 N!가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 가하면 처리 불가능한 문제.)
- 모든 후보를 검사하지 않음 (DFS는 모든 후보를 검사)
- 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감.
- 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 함.
- 반대로 해답의 가능성이 있으면 유망하다고 함.
- 가지치기: 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않음.
분할정복
1) 분할
- 해결할 문제를 여러 개의 작은 부분으로 나눔
2) 정복
- 나눈 작은 문제를 각자 해결
3) 통합
- (필요하다면) 해결된 해답을 모음
microCT_applications