본문 바로가기

Study/Algorithm

Backtracking 백트래킹 어떠한 문제가 모든 가능성을 조사하지 않고는 해를 구할 수 없는 경우, 모든 가능성을 조직적이고 효율적으로 조사하는 방법 '조사하지 않아도 되는 부분은 조사 대상에서 제외, 해를 빨리 찾는다.' 이러한 백트래킹의 해는 어떠한 제한조건을 만족하는 n개의 원소로 구성된 벡터인 (x1, x2, x3, ..., xn)의 형태로 나타낼 수 있다. 이러한 이유는, 해의 표현을 어떻게 정하느냐 하는 것은 알고리즘의 설계 방향 및 시간복잡도를 결정하기 때문에 위와 같이 단순한 형태로 나타낸다. 따라서, 해를 결정하는 과정에서 아니다 싶은 것은 사전에 제거하는데, 이때 DFS의 변형을 통해 가지치기하여 결정한다. 분기한정 백트래킹과 유사하나, 해를 찾기 위해 백트래킹과 같이 어느 특정한 운행 방법뿐만 아니라 깊.. 더보기
P/NP & Approximation Algorithm 1. 해결 가능한 문제/해결 불가능한 문제 P-완비 문제들은 현실적인 시간내에 풀 수 없는 문제들 (지수시간)이다. 다항식 시간, 현실적인 시간 -> 입력의 크기 n의 다항식으로 표시되는 시간 비다항식 시간, 비현실적인 시간 -> 지수시간, 계승시간 등 2. 결정적 문제 / 최적화 문제 결정적 문제: Yes/No 문제, 존재의 여부 파악 최적화 문제: 문제의 최적값을 찾는 문제 3. NP 완전문제 결정적 문제에만 국한되는 문제이지만, 최적화 문제와 밀접환 관계를 가진다. 결정문제가 풀린다면 최적화 문제도 풀리고 결정문제가 안풀린다면 최적화 문제도 안풀린다. 4. P/NP P: 다항식 시간 내에 결정 문제 해결 가능 NP: P를 포함, 아직 P라고 해결되지 않은 문제, 해를 제공, 해당 해가 Yes임을 다.. 더보기
[Algorithm] Dynamic Programming 동적계획법 Divide & Conquer방식과 유사하나, 차이점은 다음과 같다. [DC] 분할 -> 정복 -> 결합: 공유되는 문제도 다시 해결 [DP] 분할 -> 정복 -> 테이블에 해당 값 저장 -> 분할 된 문제에 적용 저장된 결과를 사용하여 문제해결, 공유되는 문제는 다시 해결하지 않는다. DP는 상향식 접근 방법으로 1. 문제의 해를 구할 수 있는 재귀적인 성질을 설정 2. 작은문제 해결 후 큰 문제의 해를 table에 저장 3. 크기가 작은 문제의 해를 table에 저장, 크기가 큰 문제를 효율적으로 해결한다. 이항계수 구하기 sol.1 recursion int bio1(int n, int k) { if(k == 0 || k ==n) return 1; return (bio(n-1, k-1) +.. 더보기
[Algorithm] Greedy Algorithm 욕심쟁이 기법 단계별로 연속된 선택을 함으로써 문제에 대한 해 백터(solution vector)를 구해나간다. 또한 각 단계별 선택은 전체적으로 최적인(Globally optimal) 선택을 하는 것이 아니라, 정해진 어떠한 선택 기준에 의해 그 단계에서 가장 최선인 선택, 즉 국지적으로 최적인(Locally optimal) 선택을 하는 것이다. 동전 교환 문제 단순 반복문 사용하여 동전의 개수를 최소화 하는 문제 가장 액수가 큰 동전을 차감하는 반복문을 사용한다. 테이프 장치 최적 공간 배정 문제 모든 프로그램에 대한 평균 검색 시간을 최소화하는 프로그램의 저장 순서를 결정하는 문제 가장 용량이 작은 프로그램을 순차적으로 할당한다. 분수 배낭 문제 각 물건의 무게를 Xi라고 할 때, Xi의 값이 0또.. 더보기
[Algorithm] Divide & Conquer 분할정복 주어진 문제를 크기가 작은 여러개의 부분문제로 분할(Divide)하여 부분 문제를 정복(Conquer)한 후에 그 해들을 결합(Combine), 원래 문제에 대한 해를 구하는 재귀방식의 알고리즘 주로 재귀적인 특성을 갖춘 경우가 많다. 알고리즘이 재귀 호출에 의한 경우 그 알고리즘의 수행 시간은 순환 방정식에 의해 표현 가능하다. 가령, T(n)을 입력 크기가 n인 문제에 대한 시간 복잡도 함수라 가정하자. 만일, 문제 크기가 1일 때, 직접 해를 구할 수 있다면, 그때의 시간 복잡도 함수는 C(상수)로 표현이 가능할 것이다. 또한 어떤 문제가 크기 n/b인 a개의 부분문제들로 분할된다고 가정하자. 만약 문제를 분할하는데 d(n)의 시간이 걸리고, 부분 문제들의 해를 결합하여 원래의 문제의 해를.. 더보기
[Algorithm] BFS 탐색 시, 너비를 우선으로 탐색하는 기법으로 시작점과 가까운 것 위주로 탐색한다. 이러한 BFS의 특징은 맹목적 탐색 과 최단길이 보장이다. 0. Queue에 start 노드를 넣는다. 1. Queue에서 하나의 노드를 꺼낸다. 2. 해당 노드에 연결된 노드중 방분하지 않은 노드를 방문하여 차례대로 큐에 삽입한다. 3. 1-2 과정을 Queue에 요소가 남지 않을 때 까지 반복한다. #include #include #include #define MAX_NODE INT_MAX using namespace std; bool visited[MAX_NODE];// Queue의 요소에 접근하였다는 것을 알려주는 배열 vector array[MAX_NODE + 1];// 요소가 들어있는 vector graph vo.. 더보기
Sort 종류 특징 시간복잡도 선택정렬 가장 작은 값을 앞으로 버블정렬 앞부분 두개씩 비교 삽입정렬 필요할 때만 위치 변경 퀵정렬 분할정복 Pivot을 기준으로 Divide low와 high가 엇가리면 위치를 변경 Pivot에 따라 편향 가능성이 존재 C++의 sort가 이 방법을 사용, sort의 경우 시간복잡도가 최악의 경우가 되는 경우를 방지 최선 최악 병합정렬 분할정복 나누고 합치기 합칠때는 2의 배수씩 합친다 nlogn의 시간복잡도를 보장 힙정렬 Heap Tree Node 구조 힙정렬 -> 힙구조 반복 maxHeap - parentNode > child Node - minHeap - child Node > parentNode - 계수정렬 (Counting Sort) 범위조건이 존재할 때만 사용 중복되는 .. 더보기

티스토리툴바