programming/ALGORITHM

Brute-Force Algorithm

완전 탐색 알고리즘 Brute-Force Algorithm Brute + Force는 근성으로 노가다를 통해 답을 찾는다. 즉, 모든 가능성을 시도해보며 값을 찾는 방법이다. 예를 들면 4 digit 자물쇠가 있다고 할 때 자물쇠로 만들 수 있는 모든 경우의 수를 자물쇠가 풀릴 때까지 무식하게 하나하나 시도해보는 것과 같다. 모든 경우의 수를 다 확인하기 때문에, 시간 복잡도나 공간 복잡도를 신경 쓰지 않고, 최악의 시나리오가 오더라도 컴퓨터 성능에 의존해 '결과만 일단 찾아보자' 할 때 사용할 수 있는 방법을 의미한다. Brute-Force 알고리즘은 크게 다음의 2가지 상황에서 사용한다. 프로세스 속도를 향상 시키고자 하는 데 사용할 수 있는 다른 알고리즘이 존재하지 않는 경우 문제를 해결하는 여러 ..

[TBC] Search Algorithm

추가할 것: Hash search / Trie / Heaptree 선형 탐색 Linear Search Algorithm - O(n) 배열의 0번째 인덱스부터, 찾으려는 값과 인덱스의 값을 하나씩 비교 (처음부터 끝까지 하나씩 확인) 값을 찾으면 해당 인덱스를 반환하고, 찾는 값이 없으면 -1을 반환 선형 탐색은 배열의 정렬 여부와 관계없이 시행할 수 있고 다른 탐색 알고리즘에 비해 정말 단순하고 간단한 구조이지만, 배열의 모든 요소를 하나씩 찾기 때문에 시간이 오래 걸려서 그다지 효율적인 편은 아니다. 이진 탐색 Binary Search Algorithm - O(log n) 데이터가 정렬된 상태에서 절반씩 범위를 줄여가며 특정 값을 찾는다 숫자 Up&Down 게임을 생각하면 쉽다. 탐색을 할 때마다 탐색..

Greedy Algorithm

탐욕 알고리즘, 욕심쟁이 알고리즘 등으로도 불리지만 가능하면 영문명인 그리디 알고리즘이라고 하자. Greedy 알고리즘은 위의 '탐욕'이라는 키워드 대로 선택의 순간이 주어질 때마다 당장 눈앞에 보이는 최적의 상황만을 따라가서 최종적인 답에 도달하는 방법을 말한다. Greedy 알고리즘으로 문제를 해결하기 위해서는 대략 3 단계별로 구분할 수 있다. 선택 절차(Selection Procedure) - 현재 상태에서의 최적의 해답을 선택한다 적절성 검사(Feasibility Check) - 선택된 답이 문제의 조건을 충족하는지 검사한다. 해답 검사(Solution Check) - 문제가 해결되었는지 검사하고, 해결되지 않았다면 다시 1번인 선택 절차로 돌아가 과정을 반복한다. 말로만 보면 모든 상황에서 가..

Time Complexity

시간 복잡도 시간 복잡도 (Time Complexity)는 프로그램의 입력값와 연산 수행 시간의 상관관계를 나타내는 척도를 말한다. 수치가 낮으면 낮을수록 더 효율적인 알고리즘을 뜻한다. 일반적으로 알고리즘에서 효율성을 따질때는 프로그램이 돌아가는 하나하나의 단계를 따지는 게 아닌, 시간 복잡도를 사용하게 된다. 하나하나 단계별로 효율성을 결정하기는 매우 어렵기 때문이다. 시간 복잡도는 크게 3가지 표기법으로 나타낼 수 있다. Big-O - 최악의 경우 (해당 알고리즘은 Big-O보다 더 오래 걸릴 수 없다) Big-Ω - 최선의 경우 (해당 알고리즘은 Big-Omega보다 더 빠를 수 없다) Big-θ - 평균의 경우 (Big-O + Big-Omega를 합쳐 표현한 것과 같음) 이 중에서 최악의 상황을..