Computer Science/Algorithm (8) 썸네일형 리스트형 [Algorithm] 깊이 우선 탐색 (Depth First Search) 1. 개요깊이 우선 탐색 (Depth-First Search) 은 특정 노드에서 시작하여 인접 노드를 깊게 따라가며 탐색하고, 더 이상 갈 수 없을 때 다시 돌아와 다른 인접 노드를 탐색하는 방식을 의미한다.2. 의의깊이 우선 탐색 은 다음의 경우에 유용하게 사용될 수 있다.백트래킹(Backtracking)사이클 및 연결 요소 탐색강한 연결 요소(SCC) 탐색미로 탐색 및 경로 추적3. 조건깊이 우선 탐색의 조건비선형 자료 (그래프, 트리) 의 탐색재귀 호출 혹은 자료 구조 Stack 사용탐색 시작 지점 정의방문 여부 확인4. 구현깊이 우선 탐색 은 재귀 함수나 Stack 을 이용하여 구현할 수 있다.4.1. 재귀적 구현탐색 시작 노드를 설정한다.탐색 시작 노드를 매개변수로 하는 탐색 함수를 호출한다.[.. [Algorithm] 너비 우선 탐색 (Breadth First Search) 1. 개요너비 우선 탐색 (Breadth-First Search) 은 비선형 자료를 특정 노드에서 시작하여 하위 노드보다 인접 노드를 먼저 방문하며 탐색하는 방식을 의미한다.2. 의의너비 우선 탐색 은 다음의 경우에 유용하게 사용될 수 있다.너비 우선 탐색의 의의최단 경로 탐색층별 탐색최소 신장 트리 판단3. 조건너비 우선 탐색의 조건비선형 자료 (그래프, 트리) 의 탐색추가 메모리 공간 (자료 구조 Queue 사용)탐색 시작 지점 정의방문 여부 확인4. 구현너비 우선 탐색 은 반복문과 Queue 를 이용하여 구현할 수 있다.탐색 시작 노드를 설정하고 Queue 에 삽입한다.Queue 를 dequeue 하여 얻은 노드를 탐색한다.탐색을 완료한 노드를 기록한다.현재 탐색 노드의 인접 노드들을 Queue 에.. [Algorithm] 색인 순차 탐색 (Indexed Sequential Search) 1. 개요색인 순차 탐색 은 순차 탐색 의 발전 형태로, 색인 배열 (Indexed Array) 의 형태의 구조로 저장된 자료에 대해 탐색하는 방식을 의미한다. 해당 방식은 완전 탐색이 이루어지지 않으므로 브루트 포스 의 범주에서 벗어난다.2. 의의순차 탐색 을 개선한 방식으로 더 효율적인 탐색이 가능하다는 의의가 있다.3. 조건색인 순차 탐색의 조건정렬된 배열추가 메모리 공간 (색인 배열)4. 구현색인 순차 탐색 알고리즘은 반드시 배열이 정렬되어 있어야 하며, 색인 배열를 활용할 추가적인 메모리 공간이 있어야 한다.구현 절차는 다음을 따른다.색인 순차 탐색의 절차색인 배열 크기 설정색인 배열 값 설정색인 배열에서 확인된 범위에 따른 배열 일부 탐색먼저 다음을 정의한다.배열: $A$색인 배열: $I$배열.. [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 다음
