이분탐색이란? 이분탐색은 정렬되어 있는 배열에서 사용 가능한 탐색 방법으로, 탐색 범위를 매번 반으로 쪼개 나가며 탐색하는 방법을 얘기합니다. 일반적인 탐색 방법과 비교하기 위해 다음과 같은 문제를 예시로 들어봅시다. 1~N 사이의 자연수로 이루어진 길이가 N인 수열이 있습니다. 이 수열에서 1 이상 N 이하의 정수 K는 몇 번째에 위치해 있는지 구하고자 합니다. 이를 완전탐색으로 해결하면 1번째 값부터 N번째 값까지 일일이 확인해보는 O(N)의 방법이 있습니다. 하지만 N이 100,000 이상 혹은 더욱 커지면 비효율적으로 동작하므로 더욱 빠르게 동작하는 알고리즘이 필요합니다. 만약 수열이 오름차순으로 정렬되어 있다면 이분탐색이라는 알고리즘을 적용할 수 있고, 이의 시간복잡도는 O(logN)입니다. 이..

1. 완전탐색이란? 완전탐색은 가능한 모든 경우에 대해서 일일이 수행해보는 알고리즘을 말합니다. 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법입니다. 예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해봅시다. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것입니다. (최대 10,000번의 시도로 해결 가능) 하지만, Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용합니다. 1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 ) 2. 효..

알고리즘이란? 어떤 문제를 해결하기 위한 방법과 절차 등의 집합체를 말합니다. 문제 해결을 위해서는 여러 알고리즘을 고안하고, 이들의 효율성을 평가한 후 최적의 알고리즘을 사용하는 것이 올바른 접근법입니다. 알고리즘은 아래의 5가지를 모두 만족해야 합니다. 0개 이상의 입력이 존재 1개 이상의 출력이 존재 각 명령어의 의미가 명확해야함(명백성) 한정된 수의 단계 후에는 반드시 종료(유한성) 각 멍령어가 실행 가능해야함(유효성) 알고리즘의 효율성 분석 좋은 알고리즘은 실행 시간이 빠르고, 메모리 사용량이 적은 알고리즘입니다. 하지만 일반적으로 실행시간이 빠르면 그만큼 많은 메모리 공간을 필요로 하고, 메모리 공간을 적게 사용할수록 실행시간이 느립니다. 따라서 우리는 실행 시간과 메모리 사용량 모두 적절하게..