1.Stack
목차
- 계산기에서의 Stack 활용
- 백트래킹
- 분할정복
1.1 계산기
- 중위표기법의 수식을 후위표기법으로 변경
- 스택 이용
- 중위표기법 : 연산자를 가운데로 표기하는 방법
- 후위표기법의 수식을 스택을 이용하여 계산
- 후위표기법 : 연산자를 피연산자 뒤에 표기하는 방법
1.2 중위표기식을 후위표기식을 변환하는 방법
중위 표기식을 후위표기식으로 변환 알고리즘
- 입력 받은 중위표기식에서 토큰을 읽음
- 토큰이 피연산자이면 토큰을 출력
- 토큰이 연산자(괄호 포함)일 경우
- 우선순위가 높으면 -> 스택에 push
- 우선순위가 안 높으면 -> 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자를 push
- 만약 top에 연산자가 없으면 push
예시 중위표기법으로 표현된 수식
이 과정을 동영상을 보면 이해가 간다.
후위표기법을 수식의 스택을 이용하여 계산
- 피연산자를 만나면 스택에 Push함
- 연산자를 만나면 필요한만큼 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push함
- 수식이 끝나면, 마지막으로 스택을 pop하여 출력
계산 시 주의사항 ! : 후위표기식을 계산 시, 피연산자를 스택에 쌓아 계산!
이 때, 연산자의 순서에 주의해야 한다.
처음에 pop한 값을 연산자 오른쪽으로,
그 다음에 pop한 값을 연산자의 왼쪽에 넣고 계산을 수행해야 한다.
문자열로 된 수식을 계산 시
스택을 두 번 사용해서 처리했던 연산을 파이썬에서 제공되는 eval() 내장 함수로 계산할 수 있다.
eva(수식)
- 문자열로된 수식을 계산함
- Evaluation = “값을 구함:이란 뜻
- 올바른 수식이 아닌 경우 SyntaxError 예외가 발생함
- eval(“6+5*(2-8)/2”)는 문자열로된 수식의 결과를 반환함
2. 백트래킹
해를 찾는 도중아 ‘막히면’, (즉, 해가 아니면) 되돌가서 다시 해를 찾아가는 기법 -> 최적화 문제와 결정 문제를 해결할 수 있다.
결정문제 : 문제의 조건을 만족하는 해가 존재하는 지의 여부를 ‘yes’ 또는 ‘no’로 답하는 문제
- 미로 찾기 문제
- n-Queen 문제
- Map coloring
- 부분 집합의 합(Subset Sum)문제 등
2.1 백트레킹 기법 활용 - 미로 찾기
- 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제
- 이동할 수 있는 방향은 4방향으로 제한
백트래킹 기법 활용 - 미로 찾기 알고리즘 1
- 처음 위치에서 오른쪽으로 이동한 후 이동 상황을 스택에 푸시. 여기서 이동 방향은 시계 방향 혹은 반시계 방향으로 우선순위를 정할 수 있다.
- 그림처럼 1,3처럼 다시 이동할 수 없을 때, 스택에 있던 이동상황을 pop하면서 뒤로 돌아간다.
- 1,1에서 아래쪽으로 이동이 가능하므로 스택에 이동경로를 저장하면서 다시 이동
2.2 백트래킹과 깊이 우선 탐색의 차이
백트래킹
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄임
- 가지치기(Prunning)
- 불필요한 경로의 조기 차단
- N! 가지의 경우의 수를 가진 문제에 대해서 백트래킹을 가하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간(Exponential Time)을 요하므로 처리 불가능
- 모든 후보를 검사하지 않음
깊이 우선 탐색
- 모든 경로를 추적
- N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 가하면 처리 불가능한 문제
- 모든 후보를 검사
2.3 백트래킹 기법
- 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가(Backtracking) 다음 자식 노드로 감
- 여기서 유망성이란, 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 함
- 반대로 해답의 가능성이 있으면 유망하다고 함
- 가지치기(Pruning): 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않음
2.4 백트래킹을 이용한 알고리즘의 절차
- 상태 공간 Tree의 깊이 우선 검색을 실시
- 각 노드가 유망한지를 점검
- 만익 그 노드가 유망하지 않으면, 그 부모의 부모 노드로 돌아가서 검색을 계속
2.5 일반 백트래킹 알고리즘 - n-Queen문제
n*n의 정사각형 안에 n개의 queen을 배치하는 문제로, 모든 queen은 자신의 일직선 상 및 대각선상에 아무것도 놓이지 않아야 함
이를 상태공간 트리로 표시하면 다음과 같다.
깊이 우선 탐색보다 노드 수가 적다.
2.6 깊이 우선 검색 vs 백트래킹
순수한 깊이 우선 탐색 : 155노드 백트래킹 : 27노드 ㅈ
2.7 Power Set
- 어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합
- 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n이 나옴
백트래킹 기법으로 Power Set 구하기
- 일반적인 백트래킹 접근방법 이용
- n개의 원소가 들어있는 집합의 2^n개의 부분집합을 만들 때, True 또는 False값을 가지는 항목들로 구성된 n개의 리스트를 만드는 방법을 이용
- 리스트의 i번째 항목은 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값
2.8 Power Set을 구하는 백트래킹 알고리즘
원하는 작업 도달이면 수행, 아니면 재귀호출
이 때, 백트래킹 하기 위한 후보군을 구하는 함수를 따로 구현.
후보군 구하는 함수에서는 해당 호출상태에서 추가로 구할 수 있는 후보군을 선정하여 반환한다.
영상에서 이부분 오래 설명함.
2.9 순열을 구하는 백트래킹 알고리즘
후보군을 만드는 방법이 부분집합과 다르다.
3 분할정복
3.1 설계전략
나폴레옹 -> 아우스터리츠 전투에서 연합군을 공격하기 위해 엽한군을 둘로 나누고 둘로 나뉜 연합군을 한 부분씩 격파
- 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눔
- 정복 : 나눈 작은 문제를 각각 해결
- 통합 : (필요하다면) 해결된 해답을 모음
3.2 거듭 제곱 알고리즘 O(n)
** 분할 정복 기반의 알고리즘 : O(log2n) **
3.3 퀵 정렬과 합병 정렬의 비교
합병정렬과 퀵 정렬의 공통점 : 주어진 리스트를 두 개로 분할하고, 각각을 정렬
차이점
- 합병정렬 : 분할할 때, 단순하게 두 부분으로 나눔. 각 부분 정렬이 끝난 후 ‘합병’이란 후처리 작업이 필요함
- 퀵정렬 : 분할할 때, 기준 아이템(Pivot Item)을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킴. 각 부분 정렬이 끝난 후, 후처리 작업이 필요하지 않음
3.4 퀵 정렬 알고리즘
3.5 퀵 정렬 수행 과정
이해안가면 영상 다시 보면서 이해하기
퀵 정렬의 최악의 시간 복잡도는 O(n^2) 그런데 왜 ? 퀵 정렬 ?
퀵 정렬의 평균 복잡도는 nlogn이기 때문이다. 평균적으로는 가장 빠르다.
참고자료 [SWE]https://swexpertacademy.com