계산 기하 점, 선, 다각형, 원 등 각종 기하학적 도형을 다루는 알고리즘을 계산 기하 알고리즘이라고 한다. 알고리즘 문제들에서는 대부분 기초적인 수학 이론을 구현할 수 있는 능력을 평가한다. 2차원 기하학 벡터의 구현(vector) 방향과 거리를 모두 알고 있으면 두 점 사아의 상대적인 위치를 정확히 표시할 수 있다. 이런 방향과 거리의 쌍을 벡터라고 한다. 벡터는 수학, 물리학, 공학 전반에 걸쳐 널리 쓰이는 개념으로 가장 기초적인 도구이다. 벡터의 시작점을 바꿔도 벡터는 변하지 않기 때문에 항상 원점으로 정해두면 벡터를 끝점의 위치(x, y)로만 표현할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2..

소수(prime number) 소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다. 소수의 반대: 합성수(composite number): 세 개 이상의 양의 약수를 갖는 자연수 가장 단순한 소수판별: 2 부터 n -1 까지 모든 수를 순회, n의 약수가 있는지 확인 (합성수의 성질에 따라 sqrt(n)이하 까지 순회하도록 최적화 가능) (비트 수에 따라 수행시간이 증가 => 비트 수가 하나 증가 => 수행시간 두배 => 지수시간) (1, 2, 3 제외 한 모든 소수는 6k +- 1 형태임을 이용할 수 도 있다.) (2 를 제외하면 모든 짝수는 소수가 아니다.) 1 2 3 4 5 6 7 8 9 10 bool isPrime(int n) { if(n

1. 수치 해석 직접 풀기 힘든 수학 문제를 근사적으로 푸는 알고리즘 이들의 수치적 안정성, 오차의 범위 등을 연구하는 전산학의 한 분야로, 공학, 과학, 금융과학 등 다양한 범위에 널리 사용 2. 이분법(bisection method) [lo, hi] 내에서 어떤 함수 f(x)의 값이 0이 되는 지점을 수치적으로 찾아내는 기법. 답이 여러 개 있는 함수라도 연속이기만 하다면 이분법을 사용해 근을 찾을 수 있음. 이분법을 사용하기 위해서는 우선 함수의 그래프 상에서 x축 윗부분에 위치한 점 하나와 아랫부분에 위치한 점 하나르 찾아야한다. (lo, hi) 그래프가 연속인 경우 중간값 정리에 의해 두 점 사이에서 그래프가 x축을 만나는 지점이 반드시 존재한다. lo와 hi의 중간점에서 f(x)를 검사하고 만..

1. 결정 문제(decision problem) 결정 문제란 예 아니오 현태의 답만이 나오는 문제들을 가리킴. 최적화 문제의 반환 값은 답의 경우의 수가 무한한 데 반해, 결정 문제는 두가지 답만 있음. 그러므로 결정 문제가 최적화 문제보다 더 어렵거나 시간 복잡도가 더 클 일도 없다. 2. 결정 문제로 바꾸기 어떤 문제에서 최대가 되는 x를 구하자고 하자 이를 결정 문제로 바꾸는 것은 다음과 같다. y이상일때 문제가 해결되는지? 이 결정 문제를 이분법을 사용하여 10번 100번 반복하면 결국 원래 문제인 x를 구할 수 있다. 3. 이분법의 함정 답이 가질 수 있는 가지수가 유한일 때 이분법은 수치적 안정성을 잃어버리게 된다. 최적화 문제는 아주 미세한 차이가 나더라도 답과 가까운 값을 반환하지만 결정 ..

1. 조합 탐색 동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용 될 때는 매우 유용하나 모든 문제에 적용할 수 없다. 이럴 경우 결국 완전 탐색으로 풀어야 한다. 완전 탐색은 탐색 공간의 크기에 직접적으로 비례한다. 따라서 문제의 규모가 클 경우 사용하기 어렵다는 문제가 발생한다. 이런 완전 탐색을 포함해, 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘들을 알고리즘 문제해결 전략에서는 조합탐색이라고 부른다. 조합 탐색에는 다양한 최적화 기법이 있으며 모두 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다. 조합 탐색을 최적화하기 위해 어떤 방법을 사용해야 할지 찾아내는 것은 문제 자체에 대한 깊은 식견을..

1. 탐욕법 가장 직관적인 알고리즘 설계 패러다임 중 하나임 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 , 그중 전체 답이 가장 좋은 것을 찾는 두 방법과 다르게 각 단계마다 '지금' 당장 가장 좋은 방법만을 선택함 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음 탐욕적 알고리즘은 많은 경우 최적해를 찾지 못하고 다음과 같은 경우에만 쓸 수 있음. 1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동젹 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용 2. 시간이나 공간적 게약으로 인해 다른 방법으..