본문 바로가기

전체 글

Game Engine Developing #3 #3 프로젝트 기본 파일의 생성, 파일 생성 시 중복되는 이름 방지 더보기
Game Engine Developing #2 #02 프로젝트 템플릿의 설정, 저장 경로를 시스템 로컬 폴더인 'Documents'로 설정 지난번 Open/Create의 기본적인 레이아웃을 구성하였고, 이번 시간에는 해당 레이아웃을 기반으로 저장위치의 기본 경로를 설정, 프로젝트를 제작할 때 Unity/Unreal과 마찬가지로 template을 두어 Create Project에 기본 셋팅하였다. 더보기
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또.. 더보기

티스토리툴바