david의 CS Blog

BackTracking  Bruteforce는 탐색 공간을 모두 탐색하며 가능한 해를 구하는 알고리즘이었다. 우리는 이전에 연산 횟수(탐색량)를 줄이기 위해 탐색 공간을 재정의하는 등의 과정을 통해 Bruteforce의 시간복잡도를 개선하는 방법을 익혔다.BackTracking은 Bruteforce에 첨가되는 기법과 같은 느낌으로, 탐색 공간을 조정하는 것 뿐만 아니라 탐색하지 않아도 되는 탐색 공간의 부분집합을 배제하는 과정을 통해 연산량을 줄이는 방법이다. 즉, 문제의 해가 만족하는 조건이 존재할 때, 그 조건을 만족하지 못하는 해는 미리 탐색에서 제외시킴으로써 연산량을 줄인다. 이러한 기법은 시간복잡도 개선에 유의미한 의미를 줄 수도 있고 그렇지 않을 수 있지만, 실제 프로그램의 동작이 훨씬 개선될..

Binary Search 데이터를 효율적으로 탐색하기 위해서는 탐색 공간이 효율적으로 구성되었는지와, 탐색 알고리즘이 잘 설계되어 있는지를 고려해야 한다. 탐색 알고리즘이 잘 설계되었다는 것은 해가 될 가능성이 높은 데이터를 위주로 탐색한다는 것으로, 해를 찾기 위한 연산 횟수의 상한(upper bound)이 작을수록 좋다. 이분탐색은 그러한 탐색 횟수의 상한을 $ log N $으로 보장하는 탐색 알고리즘이다. Binary Search는 매 시행마다 탐색 구간을 절반씩 줄여나가면서 탐색을 진행하는 알고리즘이다. 일반적인 탐색 방법과 비교하기 위해 다음과 같은 문제를 해결해보자.   [1,N]">$[1, N]$ 수열에서 정수 $K$는 어느 인덱스 값을 가지는가?( $K$ ∈ $[1, N]$ )   이를 B..

BruteForce        - 모든 데이터, 경우의 수를 일일이 확인하여 해를 구하는 알고리즘   알고리즘의 기본적인 목표는 주어진 데이터를 탐색하여 해를 구하는 것이다. 알고리즘 설계는 데이터를 어떻게 탐색할 것인가에 대해 초점이 맞추어져 있는데, 이 때 데이터를 탐색하는 가장 기본적인 방법이 바로 Bruteforce이다.Bruteforce는 주어진 탐색 공간의 원소들을 일일이 탐색하며 해가 될 수 있는지 확인하는 기법이다. 데이터를 모두 탐색하기 때문에, 설정된 탐색 공간(데이터가 표현되는 공간)의 크기에 따라 알고리즘의 효율성이 결정된다고 볼 수 있다. Bruteforce 알고리즘은 크게 2가지 과정으로 동작하며, 해를 구하기 위해 반드시 필요한 기본 과정들이다.  탐색 공간의 원소를 하나씩 ..