본문 바로가기

Study

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임을 다.. 더보기
Computer Animation (Basic) 더보기
[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) +.. 더보기
[C++] Header File 헤더파일에 들어갈 내용 1. 전역변수, extern keyword사용 2. 함수 프로토타입 3. define을 통한 식별자 및 매크로 4. 클래스 선언(함수 프로토타입 포함) 다른 C파일에 바디를 정의! 더보기
[Algorithm] Greedy Algorithm 욕심쟁이 기법 단계별로 연속된 선택을 함으로써 문제에 대한 해 백터(solution vector)를 구해나간다. 또한 각 단계별 선택은 전체적으로 최적인(Globally optimal) 선택을 하는 것이 아니라, 정해진 어떠한 선택 기준에 의해 그 단계에서 가장 최선인 선택, 즉 국지적으로 최적인(Locally optimal) 선택을 하는 것이다. 동전 교환 문제 단순 반복문 사용하여 동전의 개수를 최소화 하는 문제 가장 액수가 큰 동전을 차감하는 반복문을 사용한다. 테이프 장치 최적 공간 배정 문제 모든 프로그램에 대한 평균 검색 시간을 최소화하는 프로그램의 저장 순서를 결정하는 문제 가장 용량이 작은 프로그램을 순차적으로 할당한다. 분수 배낭 문제 각 물건의 무게를 Xi라고 할 때, Xi의 값이 0또.. 더보기
[Data Structure] Union-Find 유니온 파인드 그래프 알고리즘의 일종으로, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 이는 다른 말로 서로소 집합 혹은 Disjoint-Set이라 부른다. 즉, 유니온 파인드 연산은 그래프에서 특정 두 노드가 서로 연결되어 있는지 아니면 연결되지 않았는지 판별하기 위한 알고리즘이다. 유니온 알고리즘은 기본적으로 배열을 이용한다. 각각의 노드들은 배열에 자기 자신의 값을 가지고 있다. 이상태에서 노드는 단절된 상태이다. 만일, 123과 67을 연결하는 간선을 추가하고 싶다면, 2번 배열은 1번에 연결되므로 값을 1로 변경, 3번 배열은 값 2번 배열에 연결되므로 값을 2로 변경한다. 6과 7도 마찬가지로 이를 시행한다. 위 처럼 여러 노드를 연결하여 그래프를 구성하는 방법도 위와 동일하다. .. 더보기
[Algorithm] Divide & Conquer 분할정복 주어진 문제를 크기가 작은 여러개의 부분문제로 분할(Divide)하여 부분 문제를 정복(Conquer)한 후에 그 해들을 결합(Combine), 원래 문제에 대한 해를 구하는 재귀방식의 알고리즘 주로 재귀적인 특성을 갖춘 경우가 많다. 알고리즘이 재귀 호출에 의한 경우 그 알고리즘의 수행 시간은 순환 방정식에 의해 표현 가능하다. 가령, T(n)을 입력 크기가 n인 문제에 대한 시간 복잡도 함수라 가정하자. 만일, 문제 크기가 1일 때, 직접 해를 구할 수 있다면, 그때의 시간 복잡도 함수는 C(상수)로 표현이 가능할 것이다. 또한 어떤 문제가 크기 n/b인 a개의 부분문제들로 분할된다고 가정하자. 만약 문제를 분할하는데 d(n)의 시간이 걸리고, 부분 문제들의 해를 결합하여 원래의 문제의 해를.. 더보기

티스토리툴바