SW 문제해결 기본 - Stack 2 (계산기, 백트래킹, 분할 정복)

하루입니다.

 

1차시: 계산기
2차시: 백트래킹 기법의 정의
3차시: 분할 정복

 

---

 

1차시: 계산기

• 중위표기식 : 1 + 2
• 후위표기식 : 12 +

 

 

중위표기법을 후위표기법으로 변경하기 (Stack)

• 피연산자는 스택에 쌓이지 않는다.
• 연산자는 우선순위에 따라 스택에 쌓인다.
• '('는 스택 밖에서는 최우선순위, 스택 안에서는 마지막순위이다.
• ')'는 여는 괄호를 만날 때까지 모두 pop 시킨다.
• stack이 비면 종료된다. 

 

 

 

후위표기법 수식을 stack으로 계산하기

이번엔 피연산자가 stack에 들어간다!

 

 

 

 

 

---

 

 

2차시: 백트래킹 기법의 정의

• 해가 아니면 되돌아가서 다시 해를 찾는 기법이다.
• 최적화 문제와 결정 문제를 해결할 수 있다.
• 최적화 문제와 결정 문제란?

 

• 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가(백트래킹) 다음 자식 노드로 간다.
• 어떤 노드를 방문했을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 한다.
• 해답의 가능성이 있다면 유망하다고 한다.
• 가지치기 : 유망하지 않은 노드가 포함되는 경로는 더이상 고려하지 않는다.

 

 

 

백트래킹 활용 예 : 미로 찾기

• 입구와 출구가 주어진 미로에서 입구에서 출구까지의 경로를 찾는 문제
• 이동이 불가능할 때까지 진행하며 진행상황을 stack에 push한다.
• 이동이 불가능할 경우, 진행 가능한 상태로 이동하기 위해 stack을 pop한다.

 

 

 

 

 

백트래킹 VS 깊이 우선 탐색

 

 

 

 

 

nqueen 문제를 백트래킹 사용하여 해결하기 (동영상을 보자 ... )

 

 

Power Set

 

 

 

• 재귀함수 사용
• 백트랙하기 위한 후보군을 구하는 함수 따로 구현했다. 

 

 

순열을 구하는 백트래킹 알고리즘 (모르겠어요)

 

 

---

 

3차시: 분할 정복

분할(devide) : 해결할 문제를 여러개의 작은 부분으로 나눈다.

정복(conquer) : 나눈 작은 문제를 각각 해결

통합(combine) : (필요하다면) 해결된 해답을 모음

 

거듭제곱 알고리즘

 

 

분할정복 기반의 알고리즘

 

 

퀵 정렬과 합병 정렬의 비교

 

 

 

퀵 정렬

L은 피벗과 같거나 큰 수를, R은 피벗보다 작은 수를 찾는다.