Park Jinseok - Game Developer

점근적 표기(Asymptotic notation) 알고리즘의 복잡도 함수 T(n)는 입력의 크기 n에 대한 수식으로 보통 여러개의 항을 가진 다항식 형태가 된다. ex)n^2 + 3n - 5 만약 n이 무한대에 가까워진다면 복잡도 함수는 최고차항만으로도 실행시간의 대부분이 반영될 수 있다 점근적 표기는 입력의 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 방법으로 복잡도 함수를 최고차항만을 꼐수없이 취해 단순화 시킴. ex)3n^2-100n+10000는 n^2으로, 2n!+ 100^n은 n!로 나타냄 효율성 분석에서 중요한 것은 n에 대해 "연산이 정확히 몇번 필요한가?"가 아니라 n이 증가함에 따라 "무엇에 비례하는 수의 연산이 필요한가?"이다 점근적 표기는 함수에 상한(Uppe..

알고리즘 효율성 분석 시간 효율성 가장 중요한 평가 요소 실제 실행 시간을 측정할 수도 있지만, 대부분은 이론적으로 복잡도를 분석하는 방법을 사용함 공간 효율성 컴퓨터 메모리를 얼마나 사용하는지를 측정 알고리즘의 효율성 평가를 하려면 직접 구현하고, 동일한 조건의 하드웨어에서 동일한 OS, 소프트웨어를 사용하는 등의 조건이 많이 따른다 따라서, 일반적으로 이론적으로 알고리즘의 복잡도를 분석하는 방법이 주로 사용된다. 알고리즘의 복잡도를 분석하기 위해 반드시 확인해야하는 사항들 알고리즘의 입력의 크기? 복잡도에 영향을 미치는 가장 핵심적인 기본 연산은 무엇인가? ex)다중 루프의 경우 가장 안쪽의 연산 입력의 크기가 증가함에 따라 처리시간은 어떤 형태로 증가하는가? 입력의 특성에 따라 알고리즘 효율성에는 ..

자료구조(Data Structure) 단순 자료구조 ex) Integer, Float, Char 등등... 복합 자료구조 Stack,Queue,List,Graph 등등... 복합 자료구조 배열 구조와 연결된 구조 배열 구조 인접한 메모리 공간에 나열하는 구조 직접 접근(Direct Access)를 지원 연결된 구조 메모리 공간에 흩어진 자료들을 연결고리(Link)를 이용해 연결한 구조 순서 접근(Sequential Access) 방법을 지원 용량의 변경이나 항목의 추가 및 삭제가 쉬움 선형 구조와 비선형 구조 데이터들을 순서적으로 나열하여 저장하는 형태 데이터에 접근하는 방법에 따라 스택,큐,덱 등과 리스트로 나누어짐. 선형 자료구조(Linear Data Structure) 리스트(List) 또는 선형 ..

정렬(Sorting) 데이터를 순서대로 재배열하는 문제 데이터의 순서는 오름차순(Ascending Order)와 내림차순(Descending Order)가 있음. 정렬할 대상을 레코드(Record)라고 부르고, 레코드는 여러개의 필드(Field)로 이루어짐. 정렬의 기준이 되는 필드를 키(Key) 또는 정렬 키(Sort Key)라고 함. 정렬은 레코드를 키 순서대로 재배열하는 것. 비교 기반과 분배 기반 정렬 대부분의 알고리즘은 Key Value를 서로 비교하여 정렬하지만, 기수 정렬과 같이 Key Value의 분배를 이용하는 방법들도 있다. n개의 레코드를 정렬할 때 비교기반 기법들이 최소한 nlogn에 비례하는 연산이 필요한데 비해, 분배기반 정렬은 이보다 빠른 정렬도 가능함. 적용할 수 있는 Key..

1. 문제의 이해 입력의 범위를 정확히 해야 함. 올바른 알고리즘은 대부분의 입력이 아니라 모든 유효한 입력에 대해 정확한 해답을 구할 수 있어야 함. 2. 개발 방향 결정과 알고리즘의 설계 계산 장치의 특성 순서적 알고리즘 (일반적으로 많이 사용 됨.) 병렬적 알고리즘 최적해와 근사해 정확한 값을 구하는 최적해 근사(Approximation)값을 구하는 근사해 알고리즘 설계 기법 억지(Brute-force) 기법과 완전 탐색(Exhaustive Search) 문제의 정의를 가장 직접 사용하는 방법 원하는 답을 구할 때까지 모든 가능한 경우를 테스트한다. 축소 정복(Decrease and Conqier) 주어진 문제를 하나의 좀 더 작은 문제로 축소하여 해결하는 방법 분할 정복(Divide and Con..

알고리즘이란? 해결해야 할 어떤 문제가 주어졌을 때, 이 문제의 해답을 구하기 위한 절차를 순서대로 명확하게 나타낸 것. 동일한 문제에 대해서 다른 전략을 사용하는 다양한 알고리즘이 가능하며, 효율성 또한 차이가 클 수 있음. 컴퓨터에서의 알고리즘은 특정한 일을 수행하는 명령어들의 집합. 알고리즘의 조건 입력(Well-defined inputs) 0개 이상의 입력을 가지며, 모호하지 않고 잘 정의된 입력이어야 한다. 출력(Well-defined outputs) 명확하게 정의되어야 하며, 1개 이상의 출력을 반드시 가져야 한다. 명확성(Clear and unambiguous) 각 명령어의 의미는 모호하지 않고 명확해야 함. 유한성(Finite-ness) 한정된 수의 단계 후에는 반드시 종료되어야 함. (무..