Computer Science/Algorithm (6) 썸네일형 리스트형 [Algorithm] 색인 순차 탐색 (Indexed Sequential Search) 1. 개요 색인 순차 탐색 은 순차 탐색 의 발전 형태로, 색인 배열 (Indexed Array) 의 형태의 구조로 저장된 자료에 대해 탐색하는 방식을 의미한다. 해당 방식은 완전 탐색이 이루어지지 않으므로 브루트 포스 의 범주에서 벗어난다. 2. 의의 순차 탐색 을 개선한 방식으로 더 효율적인 탐색이 가능하다는 의의가 있다. 3. 조건 색인 순차 탐색의 조건 정렬된 배열 추가 메모리 공간 (색인 배열) 4. 구현 색인 순차 탐색 알고리즘은 반드시 배열이 정렬되어 있어야 하며, 색인 배열를 활용할 추가적인 메모리 공간이 있어야 한다. 구현 절차는 다음을 따른다. 색인 순차 탐색의 절차 색인 배열 크기 설정 색인 배열 값 설정 색인 배열에서 확인된 범위에 따른 배열 일부 탐색 먼저 다음을 정의한다. 배열:.. [Algorithm] 순차 탐색 (Sequential Search) 1. 개요 순차 탐색 (Sequential Search) 은 선형 탐색 (Linear Search) 그 자체이며, 배열과 같은 선형 구조에 대해 탐색하는 방식을 의미한다. 자료 구조 전체에 대한 탐색이 이루어지므로 완전 탐색 (Brute Force) 의 한 종류라고 할 수 있다. 2. 의의 순차 탐색 알고리즘은 구현이 용이하다. 항상 효율적이라고는 할 수 없지만, 쉽게 구현할 수 있다는 점에서 의의가 있다. 또한, 선형 구조의 정렬 여부와 관계 없이 사용 가능하다는 장점이 있다. 3. 조건 순차 탐색 역시 완전 탐색 이므로 완전 탐색의 조건을 따른다. 4. 구현 순차 탐색 알고리즘은 선형 자료 구조를 그 길이 만큼 모두 탐색하기 때문에 보통 반복문을 사용하여 구현된다. 다음의 예시를 보자. 5. 예시) .. [Algorithm] 탐색 (Search) 1. 개요 탐색 (Search) 알고리즘은 한 개 이상의 자료들 사이에서 특정 자료를 색출하는데 사용하는 방식을 의미한다. 자료가 저장된 형식에 따라 쓰이는 탐색 알고리즘 은 달라진다. 이 포스팅에서는 탐색 알고리즘 의 종류와, 각각의 알고리즘이 어떠한 상황에서 사용되는지에 대해 살펴보고자 한다. 2. 종류 다음 모두 탐색 알고리즘 이라고 할 수 있다. 위 탐색 알고리즘을 선택하여 해당 포스팅으로 이동할 수 있다. [Algorithm] 그리디, 탐욕 (Greedy) 1. 개요 그리디 (Greedy), 탐욕 알고리즘 (이하 그리디) 은 어떠한 것을 선택할 상황이 발생하면 항상 그 시점의 최선의 선택을 해나가는 방식을 의미한다. 근사적인 최적해 (이하 근사해) 를 구할 수 있다는 특징이 있다. 근사해가 최적해 만큼 의미있게 취급될 경우 주로 사용한다. * 근사해라고 표현되는 이유는 그리디가 항상 최적해를 구할 수 있는 것은 아니기 때문이다. 따라서 최적해를 구하기 위한 근사적인 방법 이라는 것만 이해하면 충분하다. 그리디를 적용하기 전, 다음의 경우를 만족하는가를 파악할 필요가 있다. 현재 선택이 미래의 선택에 독립적인가? 하위 문제를 통해 전체 문제를 해결할 수 있는가? 2. 의의 그리디는 DP를 사용하는 경우 중, 특정 경우에 대해 속도를 향상 시키기 위해 사용한다.. [Algorithm] 완전 탐색, 브루트 포스 (Brute Force) 1. 개요 브루트 포스 (Brute Force) 는 모든 경우에 대해서 탐색하며 조건을 충족하는 경우에 한해 결과를 도출하는 방식으로, 탐색 알고리즘의 한 종류이다. 완전 탐색 알고리즘이라고도 한다. 2. 의의 브루트 포스는 모든 경우에 대한 탐색으로 결과의 100%의 정확성을 추구한다. 3. 조건 브루트 포스를 사용하기 위해서는 다음의 조건을 만족하여야 한다. 브루트 포스의 적용 조건 문제 해결 방법 정의 문제 수의 제한 3.1. 문제 해결 방법 정의 해결할 문제의 정확한 정의를 바탕으로 조건이 충족되는 경우를 찾아나가야 한다. 3.2. 문제 수의 제한 해결할 문제의 수가 적당해야 한다. 너무 많은 양의 문제를 해결해야 할 경우, 많은 시간을 소요하는 등의 성능 저하가 발생한다. 4. 종류 4.1. 선.. [Algorithm] 동적 계획법 (Dynamic Programming) 1. 개요 동적 계획법 (Dynamic Programming) (이하 DP) 은 문제를 여러 작은 문제들로 쪼개어 해당 문제를 해결하는 방식을 의미한다. DP를 적용하기 전, 다음의 경우를 만족하는가를 파악할 필요가 있다. 문제를 더 작은 문제로 쪼갤 수 있는가 이전에 구한 해를 재사용 할 수 있는가 2. 의의 DP는 기본적으로 알고리즘을 최적화하기 위해 사용한다. 3. 조건 DP를 사용하기 위해서는 다음의 조건을 만족하여야 한다. DP 의 적용 조건 Overlapping Subproblems (중복 하위 문제) Optimal Substructure (최적 하위 구조) 3.1. Overlapping Subproblems (중복 하위 문제) DP는 하위 문제 (Subproblems) 에서 중복 (Overl.. 이전 1 다음
