Computer Science/Algorithm4 [알고리즘] 완전 탐색 (Exhaustive Search) • 완전 탐색 (Exhaustive Search) 이란? 컴퓨터의 빠른 연산 능력을 활용하여 가능한 모든 경우의 수를 일일히 대입하여 해를 찾는 방법. 무차별 대입하여 탐색한다는 의미로써 Brute force search 로 명칭하기도 한다. 이는 효율을 중시하기보단 정확성을 중시하는 문제 해결 기법으로써 입력의 수에 따라 시간복잡도가 기하급수적으로 증가하기 때문에 그 수가 적은 문제에 활용하기 적합하다. • 완전 탐색의 종류 1. Brute Force 단순히 반복문이나 조건문을 다중으로 사용하여 처음부터 끝까지 모든 경우의 수를 구하는 기법. 이는 주로 기초적인 문제나 전체 문제 풀이의 일부분에 활용된다. 예시로 배열의 요소의 수 만큼의 중첩 for 문을 사용하여 요소의 모든 순열을 찾을 수 있다. i.. 2022. 5. 23. [알고리즘] 그래프 순회 (Graph Traversal) • 그래프 순회 (Graph Traversal) 란? 정점(node) 과 그 정점을 연결하는 간선(edge) 으로 이루어진 자료구조를 그래프(graph) 라 한다. 그래프의 하나의 정점으로부터 시작하여 모든 정점을 한 번씩 방문하거나, 그에 따라 특정한 목표 정점을 찾아가는 방법을 그래프 순회, 또는 그래프 탐색이라 하며 이러한 그래프 순회의 대표적인 탐색 방법이 DFS, BFS 라 할 수 있다. • 깊이 우선 탐색 (Depth-first search) 루트 노트, 혹은 임의의 노드에서 시작하여 특정 분기를 최대한 깊숙히 탐색한 후, 다시 돌아와 다음 분기를 탐색하는 방식. 주로 모든 노드를 방문하여 탐색하고자 할 때 이 방법을 선택한다. 일반적으로 재귀 함수 호출을 사용하여 구현하거나 Stack 자료구.. 2022. 5. 16. [알고리즘] 동적 계획법 (Dynamic Programming) • 동적 계획법이란? 복잡한 문제를 풀기 위해서 여러 개의 하위 문제로 분해하여 결과를 저장한 후, 그것을 결합하여 최종적인 목적에 도달하는 알고리즘 최적화 기법이다. Dynamic Programming 이라는 다소 과하다 싶은 명칭의 어원은 1950년대 수학자 Richard Bellman에 의해 고안되었다. 당시 ”Programming”이라는 말은 실제로 컴퓨터의 코딩처럼 프로그래밍을 의미하는 것은 아니었다. 이때 프로그래밍이 의미하는 것은 "계획"과 "결정"이었다. ”Dynamic” 이라는 단어는 벨먼이 문제의 시가변적이며 다단계적인 특성을 포착하기 위함으로써 선택했고, ”Programming” 은 훈련이나 군수 물자 운송을 위한 최적의 프로그램을 찾기 위해 특정 방법을 사용하는 것을 가리키는 용어였.. 2022. 5. 6. [알고리즘] 탐욕법 (Greedy Algorithm) • 그리디 알고리즘이란? 각각의 수행시점에서 가능한 해 중 가장 최적해를 찾아 나가는 알고리즘. 즉 근시안적인 최적해를 찾는다고 할 수 있으며 이러한 근시안적 최적해들을 모아서 최종적으로 문제의 최적해를 구한다. 그러나 경우에 따라 수행시점마다의 선택이 해당 시점에 대해서는 부분적으론 최적이지만, 그 선택들을 수집해 최종으로 도출한 해답이 전체적으로 최적이라는 보장은 없다. 위의 예시에서 해당 트리를 그리디로 접근 시 가장 큰 수는 6이라는 결과가 나오지만 실제로 가장 큰 수는 99이므로 그리디 알고리즘이 최적해를 구하지 못하게 된다. • 그리디로 접근하여 최적해를 구하기 위해 2가지 조건 1) 탐욕적 선택 속성 (Greedy Choice Property) : 이전의 선택이 이후에 영향을 주지 않음. 2.. 2022. 5. 3. 이전 1 다음
