Development/Algorithm (4) 썸네일형 리스트형 브루트 포스(Brute Force, 완전 탐색) 브루트 포스(Brute Force)는 거의 모든 문제에 사용할 수 있는 기법으로 완전 탐색이라고도 합니다. 이 기법은 이름처럼,"맹목적으로, 모든 경우의 수를 탐색하여 결과를 도출하는 기법" 입니다. 이 기법은 어쩔수없이 모든 경우의 수를 탐색해 봐야만 하는 경우나, 모든 경우의 수를 요구하는 문제에서 주로 사용됩니다. 예를들어, 1부터 100까지의 합을 구하는 문제가 있을 때 아래와 같이 모든 경우의 수( 1부터 100까지) 탐색하여 그 합을 구하는 방식이 브루트 포스가 될 수 있습니다. 123sum = 0for i in range(1, 101): sum += ics 이 뿐 아니라 가장 대표적인 예시로, 순열을 구하는 문제가 있습니다. 예를들어, 1부터 5까지의 수를 이용해 모든 수에 대한 순열을 구하.. 깊이우선 탐색(DFS), 넓이우선 탐색(BFS) 깊이우선 탐색(DFS, Depth-first Search)과 넓이우선 탐색(BFS, Breadth-first Search)은 그래프에서 사용되는 가장 대표적이며, 어쩌면 맹목적인 두 가지 탐색 기법입니다. (맹목적인이라는 말을 언급한 이유는 기본적으로, 원하는 결과를 도출하기 위한 방향이 없이 해당 노드에서 모든 경우에 대하여 탐색을 수행하기 때문입니다.) 두 가지 방식에 대한 차이는 탐색하는 모든 경우를 깊이에 우선하여 탐색을 수행할 것이냐, 넓이에 우선하여 탐색을 수행할 것이냐 라는 것입니다. 깊이에 우선한다는 것은 현재 노드에서 이동 가능한(연결된) 다음 레벨의 노드를 확인한 후, 곧바로 현재 노드 위치를 선택된 다음 레벨의 노드로 변경한다는 것입니다. 이때, 다음 레벨의 노드에서 원하는 결과를 찾.. 분할 정복(Divide and Conquer) 기법의 이름 그대로 큰 문제를 분할하여, 작은 문제들(Sub problems)로 나눈 뒤 그 결과들을 합쳐 기존의 큰 문제를 해결해나가는 기법입니다. 네이버 사전에 검색하면 아래와 같은 결과가 나옵니다. 분할정복의 경우 재귀적으로 해결하는 방식이 가장 많이 사용되곤 합니다. 위 사전에서 설명하듯 성질이 같은 여러 개의 부분 문제로 쪼개고, 쪼개진 문제(Sub problem)에서 동일한 방식으로 다시 쪼개고, 쪼개고 ... 쪼개다가 더이상 나눌 수 없을 경우 해당 Sub problem에서 해를 구하고 재귀적으로 돌아오면서 전체의 큰 문제를 해결합니다. 예를 들어 아래와 같은 [배열에서 1의 개수]를 구하는 문제가 있다고 합시다. (물론 2차원 배열이기 때문에, 2중 반복문을 통해 1의 개수를 찾는 것이 가.. 동적 프로그래밍(Dynamic Programming) 알고리즘을 공부하게 되면 보통 가장 먼저 접하게 되는 기법입니다. 그만큼 등장빈도도 굉장히 높고, 다양한 문제를 쉽게 접할 수 있습니다. 네이버 사전에 검색하면 아래와 같은 결과가 나옵니다.. 다단 배치 과정, 확률적 다단 결정 과정 등 어려운 말들이 많지만 추후에 천천히 공부해보기로 하고... 순차적으로 접근하는 문제에서 가장 많이 사용되는 기법으로, 동적 프로그래밍의 가장 중요한 개념은 다음과 같습니다. "이전에 사용한 결과값을 이용해, 다음의 결과값을 구한다." 동적 프로그래밍은 하나의 문제를 여러 개의 작은 부분 문제(Sub problem)으로 나누어 해결하는 문제 해결 기법입니다. 그래서 대부분의 문제들을 [이전에 해결한 문제에서 도출된 결과값] 들을 사용하여 [다음 문제의 결과값]을 구하기 위.. 이전 1 다음
