[알고리즘 기초] 05_Stack 2 / Python

[알고리즘 기초] 05_Stack 2 / Python

[알고리즘 기초] 05_Stack 2 / Python

1. 계산기

• 문자열로 된 계산식이 주어질 때, 스택이 이용하여 이 계산식의 값을 계산할 수 있다.
• 문자열 수식 계산의 일반적 방법
  • step1. 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용)
  • step2. 후위 표기법의 수식을 스택을 이용하여 계산한다.

 

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

1. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2. 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다.
3. 괄호를 제거한다.

< A * B - C / D >
1. ( ( A * B ) - ( C / D ))
2. ( ( A B ) * ( C D ) / ) -
3. AB * CD / -

 

 

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

1. 입력받은 중위 표기식에서 토큰( '(', ')', 연산자 )'을 읽는다.
2. 토큰이 피 연산자이면 토큰을 출력한다.
3. 토큰이 연산자일때, top에 저장되어있는 연산자보다 우선수위가 높으면 스택에 push, 그렇지 않다면 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자를 push한다.
4. 토큰이 오른쪽 괄호이면 스택 top에 왼쪽 괄호가 올 때까지 스택에 pop연산을 수행하고, pop한 연산자를 출력한다. 왼쪽 괄호를 만나면 pop만 하고 출력하지는 않는다.
5. 중위표기식에 더 읽을것이 없다면 중지하고, 있다면 1부터 반복한다.
6. 스택에 남아 있는 연산자를 보두 pop하여 출력한다.
   • 스택 밖의 왼쪽 괄호는 우선순위가 가장 높으며, 스택안의 왼쪽 괄호는 우선순위가 가장 낮다.

 

 

2. 백트래킹

• 백트래킹 기법은 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다.
• 백트래킹 기법은 최적화 문제와 결정 문제를 해결할 수 있다.
• 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no' 답하는 문제
  • 미로찾기
  • n-Queen 문제
  • Map coloring
  • 부분 집합의 합(Subset Sum) 문제 등
• 백트래킹과 깊은우선탐색과의 차이
  • 어떤 노드에서 출발하는 결로가 해결책으로 이어질 것 같지 않으면 더 이상 그 결로를 따라가지 않음으로써 시도의 횟수를 줄임. - Prunning : 가지치기
  • 깊이우선탐색의 모든 경로를 추적하는데 비해 백트래킹을 불필요한 경로를 조기에 차단.
  • 깊이우선탐색을 가하기에는 경우의 수가 너무나 많음. 즉, N! 가지의 경우의 수를 가진문제에 대해 깊이우선탐색을 가하면 당연히 처리 불가능한 문제.
  • 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간(Exponential Time)을 요하므로 처리 불가능
• 백트래킹 기법
  • 어떤 노드의 유망성을 점검한 후에 유망(promising) 하지 않다고 결정되면 그 노드의 부모로 되돌아가 (backtracking) 다음 자식 노드로 감
  • 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
  • 가지치기(pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

 

 

3. 부분집합 구하기

• 어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합을 powerset이라고 하며 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n이 나온다.
• 백트래킹 기법으로 powerset을 구해보자.
  • 앞에서 설명한 일반적인 백트래킹 접근 방법을 이용한다.
  • n개의 원소가 들어있는 집합의 2^n개의 부분집합을 만들 때는, true 또는 false값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용.
  • 여기서 배열의 i번째 항목은 i번째 원소가 부분집합의 값인지 아닌지를 나타내는 값이다.

 

 

4. 분할 정복 알고리즘

• 설계 전략
  • 분할(Dvice) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
  • 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
  • 통합(Combine) : (필요하다면) 해결된 해답을 모은다.

 

 

5. 퀵 정렬

• 주어진 배열을 두개로 분할하고, 각각을 정렬한다.
• 분할할 때, 기준 아이템을 중심으로, 작은것은 왼편 큰것은 오른편에 위치시킨다.
• 퀵 정렬의 최악의 시간 복잡도는 O(n^2)로, 합병정렬에 비해 좋지 못하다.
• 하지만 평균 복잡도는 nlogn 이기에 더 빠른 정렬이다.