[Python] 스택 2

계산기

 - 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.

 - 문자열 수식 계산의 일반적 방법

  ㄱ. 중위 표기법 수식 > 후외 표기법으로 변경

  ㄴ. 후위 표기법 수식을 스택을 이용 계산

 

여기서,

 중위 표기법이란? [ A+B 와 같이 일반적으로 우리가 사용하는 식 ]

 후위 표기법이란? [ AB+ 연산자를 뒤로 보내 표기하는 방식 ]

일반식           : A*B-C/D

변환하는 방법 :   1. 수식의 각 연산자에 대해 우선순위에 따라 괄호 표현실시  ( (A*B)-(C/D) )  2. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로이동  ( (AB) *(CD) / )-  3. 괄호 제거  AB*CD/-

저의 방법 1. 일단 수식을 전부 적어줍니다.  ABCD 2. 식의 우선순위에 따라 연산자를 해당 식의 뒤로 이동  - AB* - CD/  - AB*CD/-

 

알고리즘

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

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

 3. 토큰이 연산자(괄호포함)일 때, 이 토큰이 스택의 top에 저장되어 있는 연산자보다 우선순위 높으면 스택 push

 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 pop 한 후 연산자를 push

만약 top에 연산자 없으면 push

 4. 토큰이 오른쪽 괄호 ')' 이면 스택 top에 왼쪽 괄호 '(' 가 올 때까지 스택에 pop 연산을 수행

 pop 한 연산자를 출력한다. 왼쪽 괄호 만나면 pop 하고 출력 안함

 5. 중위 표기식에 더 읽을게 없으면 중지, 있으면 1 부터 다시 반복

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

 

 

 

 

 

백트래킹

 - 백트래킹(Backtracking) 기법은 해를 찾는 도중에 '막히면'(즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법

 - 최적화(optimiation) 문제와 결정(decision) 문제를 해결할수있다.

 - 결정 문제란 조건을 만족하는 해가 존재하는지 여부를 말한다 (yes or no)

   (미로 찾기, n-Queen, Map coloring, 부분 집합의 합 문제 등)

예 ) 미로 찾기

 우리가 미로에 있을 때 문이 2개가 있다고 생각하자. 한쪽히 막혔다면 문이 2개가 있는 곳으로 다시 와서 다른 문을 선택하는 것을 말한다. 

 1. 미로 이동 ( 이동가능한 길은  - push)

 2. 2개의 문 ( 먼저 1번째 문으로 길을 나선다 - push)

 3. 막다른길 도착 ( 현재까지 걸어온 길은 push가 돼있었다. 이제 다시 되돌아간다. -pop 변경)

 4. 2개의 문 ( 현재 stack 의 상태는 2번의 상태로 돌아간다.)

 5. 2번째 문으로 길을나선다. ( push) 

....

백트래킹, 깊이 우선탐색의 차이

백트래킹	깊이 우선탐색
어떤 노드에서 출발할때 경로가 해결책이 아니다? 그럼  그 경로를 가지 않고 끊어버림 ( 가지치기 )	나는 다 간다...

 다만, 백트래킹 알고리즘을 적용시 '일반적으로 경우의 수는 줄어든다'

하지만 최악의 경우에는 여전히 Exponential Time을 요하므로 처리 불가능

 

기법

 - 노드를 점검하고 이 녀석이 필요 없다? 판단되면 부모 노드로 되돌아가 다른 자식 노드로간다.

 - 노드를 필요한 노드, 불필요한 노드로 판단한다.

 - 즉, 가지치기를 통해 좀더 효율적으로 한다는 말 ( pruning )

 

 

알고리즘

 1. 상태 공간 트리의 깊이 우선 검색 실시

 2. 각 노드 판단 ( 필요? 불필요? - 유망성)

 3. 유망하지 않다면 부모로 돌아가 다른 노드를 통해 검색

def checknode(v) : #node
if promising(v):
if 해결 방안이있다 (v) :
해결 ㄱㄱ
else: # 해결방안 없을떄
for 부모노드로 가서 다른 자식 노드 가봄
cjecknode(u)

def checknode(v) : #node
    if promising(v):
        if 해결 방안이있다 (v) :
            해결 ㄱㄱ
        else: # 해결방안 없을떄
            for 부모노드로 가서 다른 자식 노드 가봄
                cjecknode(u)

 

 

 

분할정복

유래 

 - 나폴레옹 전략

 - 부분 격파

설계

 분할, 정복, 통합

 거듭 제곱 O(n) 

def Power(Base,Exponent) :

 if Base == 0: return 1

 result = 1 # Base^0은 1이므로

 for i in range(Exponent) :

   result *= Base

 return result

 

분할 정복 기반 알고리즘 O(log n)

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

 

 

 

 

 

퀵 정렬

- 퀵정렬의 최악의 시간 복잡도는 O(n^2)로, 합병정렬에 비해 좋지 못함

- 다만 평균 복잡도가 nlogn 이라 퀵정렬..

 

알고리즘

def quickSort(a, begin, end):

 if begin < end :

  p = partiton ( a, begin, end)

  quickSort(a, begin, p-1)

  quickSort(a, p+1, end)

 

알고리즘

def partition ( a, begin, end) :

 pivot = (begin + end) // 2

 L = begin

 R = end

 while L < R :

  while(a[L] < a[pivot] and L<R) : L += 1

  while(a[R] >= a[pivot] and L<R) : R -= 1

  if L < R :

   if L==pivot : pivot = R

   a[L],a[R] = a[R], a[L]

 a[pivot], a[R] = a[R], a[pivot]

 return R