[AlgoDat-a] 03 Backtracking, Greedy Algorithmen, Queues ,Stacks und PriorityQueue
Quellen für das Schreiben oder den Inhalt befinden sich normalerweise ganz unten.
"공부하면서 더 오래 상기시키기 위해 여기에 짧은 요약을 씁니다."
글이나 내용의 출처는 보통 하단에 있습니다.
OS : Window Editor: IntelliJ IDEA
01 Backtracking
Backtracking은 문제의 해를 찾기 위해 모든 가능한 경우의 수를 탐색하면서 최적의 해를 찾는 알고리즘이다. 일반적으로 재귀적인 방식으로 구현되며, 주어진 문제에 대한 모든 가능한 선택지를 시도하고, 각 선택마다 다음 단계로 진행하며 해를 찾는 과정을 거친다.
Backtracking은 다음과 같은 단계로 이루어진다:
- 선택(Choice): 주어진 문제에 대해 가능한 선택지 중 하나를 선택한다.
- 조건 충족(Feasibility): 선택한 선택지가 주어진 조건을 충족하는지 확인한다.
- 해 검증(Solution Check): 선택한 선택지가 문제의 해를 이루는지 검증한다. 만약 해를 찾았다면 알고리즘을 종료한다.
- 다음 단계로 진행(Move to Next Step): 선택한 선택지를 적용하고 다음 단계로 진행합니다. 이 단계에서는 재귀 호출을 사용하여 다음 선택을 수행한다.
- 선택의 취소(Rollback): 현재 선택지에 대한 결과가 해를 이루지 못하거나 모든 선택지를 시도한 경우, 이전 선택지로 돌아가 선택을 변경한다. 이를 통해 다른 선택지를 시도하며 해를 탐색한다.
Backtracking은 조합 최적화, 순열 생성, 그래프 탐색, 상태 공간 탐색 등 다양한 문제에 적용될 수 있다. 하지만 경우의 수가 많고 가능한 조합이 많은 경우에는 시간 복잡도가 지수적으로 증가할 수 있으므로 효율적인 알고리즘 설계가 필요하다.
Backtracking의 장점은 모든 가능한 경우의 수를 탐색하기 때문에 해를 보장한다는 점이다. 하지만 단점으로는 경우의 수가 많을 경우 시간이 오래 걸리는 것이고, 최적의 해를 찾지 못하는 경우도 있을 수 있다. 따라서 Backtracking을 사용할 때는 문제의 특성과 제약 조건을 고려하여 적절한 종료 조건과 가지치기(Pruning)를 적용하여 성능을 향상시킬 수 있다.
가지치기(Pruning)는 Backtracking 알고리즘에서 불필요한 탐색을 제거하여 실행 시간을 단축하는 기법을 말한다.
가지치기는 다음과 같은 방법으로 구현될 수 있다:
유망성 검사(Promising Check):현재 상태에서 해를 찾기 위한 가능성이 있는지를 검사한다. 만약 현재 상태에서 해를 찾을 수 없다고 판단되면 해당 분기를 가지치기하여 더 이상 탐색을 진행하지 않도록 한다.
제약 조건 확인(Constraint Check): 문제에 주어진 제약 조건을 고려하여 현재 상태에서 유효한 해를 찾을 수 있는지를 확인한다. 제약 조건을 만족하지 않는 경우 해당 분기를 가지치기하여 더 이상 탐색을 진행하지 않도록 한다.
최적해 도출(Optimal Solution Check): 찾은 해의 값이 현재까지의 최적해보다 좋지 않은 경우 해당 분기를 가지치기하여 더 이상 탐색을 진행하지 않도록 한다. 최적화 문제의 경우 최적해를 구하는 것이 목표이므로, 현재까지 구한 해의 값이 최적해보다 나쁜 경우에는 해당 분기를 가지치기한다.
02 Greedy Algorithmen
Greedy Algorithm(탐욕 알고리즘)은 최적해를 구하는 데 사용되는 간단하고 직관적인 알고리즘 설계 기법이다. 이 알고리즘은 각 단계에서 가장 최적인 선택을 하는 방식으로 동작하며, 각 선택이 지역적으로 최적인 경우를 전체적으로 최적인 해를 구하는 것을 목표로 한다. Greedy Algorithm은 현재 상태에서 가장 좋은 선택을 하기 때문에 지역 최적해를 구할 수 있지만, 이 선택이 전역 최적해를 보장하지는 않는다.
Greedy Algorithm의 작동 방식은 다음과 같다:
- 문제를 작은 부분 문제로 분할.
- 각 단계에서 가장 최적인 선택을 함.
- 이 선택을 현재 솔루션에 추가하고, 다음 단계로 이동.
- 단계를 반복하여 최종 솔루션을 완성.
거스름돈 문제: 가장 적은 동전의 개수로 거스름돈을 주는 방법을 찾는 문제.
최소 신장 트리(Minimum Spanning Tree) 문제: 그래프에서 모든 노드를 연결하는 최소 비용의 트리를 찾는 문제.
탐욕적 스케줄링 문제: 작업의 시간과 마감 기한이 주어졌을 때, 최대한 많은 작업을 수행하는 문제.
최적의 길 찾기 문제: 출발점에서 도착점까지 가는 최단 경로를 찾는 문제.
Greedy Algorithm은 간단하고 효율적인 구현이 가능한 경우가 많지만, 항상 최적해를 보장하지는 않는다. 때로는 Greedy 접근 방식이 지역 최적해에 갇힐 수 있고, 전역 최적해를 구할 수 없을 수도 있다. 따라서 Greedy Algorithm을 사용할 때에는 문제의 특성을 고려하고, 최적해를 보장하는지 확인해야 한다.
지역 최적해(Local Optimum): 지역 최적해는 주어진 문제의 일부 영역에서의 최적해를 의미한다. 즉, 주어진 조건 내에서 가장 좋은 해를 찾는 것이지만, 전체적으로는 최적해가 아닐 수 있다. 또한 지역 최적해는 주변 해들과 비교하여 더 이상 개선할 수 없는 해로 간주된다. 따라서 지역 최적해는 그 문제에 대한 부분적인 최적화를 나타내지만, 전체적인 최적화를 보장하지 않는 것이다.
전역 최적해(Global Optimum): 전역 최적해는 주어진 문제의 전체 영역에서의 최적해를 의미한다. 즉, 주어진 조건 내에서 가장 좋은 해를 찾는 것이며, 모든 가능한 해 중에서 최적인 해이다. 전역 최적해는 문제의 목표에 따라 달라지며, 주어진 문제에 대한 최고의 해를 말한다.
02-1 Greedy Algorithmen beispiel
Q) 만약 아이폰에 1GB(1000MB)의 저장공간이 남아있는 상태에서 6개의 서로다른 용량의 App을 설치하려고 한다. Greedy 알고리즘을 사용하면 어떤 순서로 설치할까?
6개의 App의 크기는 다음과 같다:
App1: 400MB
App2: 200MB
App3: 140MB
App4: 160MB
App5: 100MB
App6: 110MB
Q) 이후 저장용량에 맞게 최적화를 하는 경우에는 어떻게 될까?
- 마지막에 설치한 App2 대신 App1을 설치한다. 대신 90MB가 여전히 남는다.
- 용량에 가장 적절하게 App6을 삭제하고 App1을 설치한다.
03 Queues ,Stacks und PriorityQueue???
Queues, Stacks, 그리고 PriorityQueue는 세 가지 다른 데이터 구조로, 임의의 요소들을 저장하고 관리하는 방법이다.
03-1 Queue (큐)
큐는 선입선출(FIFO, First-In-First-Out) 원칙을 따르는 데이터 구조다.
요소들이 큐에 추가되는 순서대로 저장되며, 가장 먼저 추가된 요소가 가장 먼저 제거된다.
(큐는 일상 생활에서 줄을 서는 상황과 유사한 동작을 수행한다.)
03-2 Stack (스택)
스택은 후입선출(LIFO, Last-In-First-Out) 원칙을 따르는 데이터 구조다.
요소들이 스택에 추가되는 순서대로 저장되며, 가장 최근에 추가된 요소가 가장 먼저 제거된다.
(스택은 쌓여져 있는 상자나 책을 생각할 수 있으며, 가장 위에 쌓인 요소(마지막에 추가된 요소)에 접근할 수 있다.)
03-3 PriorityQueue (우선순위 큐)
우선순위 큐는 각 요소에 우선순위를 할당하고, 우선순위가 높은 요소가 먼저 제거되는 데이터 구조다. 요소들은 우선순위에 따라 정렬되어 저장되며, 가장 높은 우선순위를 가진 요소가 먼저 제거된다. (우선순위 큐는 일상 생활에서 우선순위가 높은 작업을 먼저 처리하는 상황과 유사하다.)
03-4 Queues ,Stacks und PriorityQueue과 알고리즘
큐(Queues), 스택(Stacks), 우선순위 큐(PriorityQueue)는 다양한 알고리즘과 데이터 구조에서 사용될 수 있다.
03-4-1 큐(Queues):
- 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘:
그래프의 노드를 탐색할 때, 각 노드를 방문한 순서대로 큐에 저장하여 다음에 방문할 노드를 선택.
- 작업 큐(Job Queue):
여러 작업들이 도착한 순서대로 처리되어야 할 때 사용. (예를 들어, 작업을 받는 서버에서 동시에 여러 요청이 들어올 경우, 큐를 사용하여 순차적으로 처리할 수 있다.)
- 프로세스 스케줄링에서 사용:
여러 프로세스가 동시에 실행되어야 할 때, 큐를 사용하여 각 프로세스의 우선순위와 순서를 관리한다.
03-4-2 스택(Stacks):
- 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘:
그래프의 노드를 탐색할 때, 현재 노드와 연결된 노드들을 스택에 저장하여 깊이 방향으로 탐색한다.
- 함수 호출 스택(Call Stack)으로 사용:
함수 호출 시 스택에 현재 실행 중인 함수의 정보를 저장하고, 함수가 반환되면 해당 정보를 스택에서 제거하여 함수 호출 순서를 관리한다.
- 수식 평가에서 사용:
중위 표기법의 수식을 후위 표기법으로 변환하고, 후위 표기법을 계산할 때 스택을 사용하여 연산자와 피연산자를 처리한다.
03-4-3 우선순위 큐(PriorityQueue):
- 다익스트라 알고리즘(Dijkstra’s Algorithm)에서 사용:
최단 경로를 찾는 알고리즘으로, 우선순위 큐를 사용하여 현재까지 최단 경로로 판단된 노드를 선택한다.
- 작업 스케줄링에서 사용:
우선순위를 기준으로 작업들을 처리하는 스케줄러에서 우선순위 큐를 사용하여 작업의 우선순위를 관리한다.
- 이벤트 처리(Event Handling)에서 사용:
이벤트의 우선순위에 따라 처리 순서를 결정하고, 우선순위 큐를 사용하여 이벤트를 처리한다.
Quelle(text): vorlesung, nomadcoders
Quelle(image):
Leave a comment