Computer Science/Algorithm (8) 썸네일형 리스트형 [Algorithm] 깊이 우선 탐색 (Depth First Search) 15723번 - n단 논법1. 문제모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.지무근은 중앙대 컴퓨터공학부 학생이다.그러므로 지무근은 미인이다.위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, $n$ 개의 전제가 있을 때 $m$ 개의 결론을 도출할 수 있을 것이다. 이때의 $n$과 $m$은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.Input첫째 줄에 정수 $n(2 \le n \le 26)$ 이 주어진다.둘째 줄부터 $n$개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지.. [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 다음
