Budding Hacker

1. 기본 정렬 알고리즘 정렬 알고리즘 - 대부분 O(n²)과 O(nlogn) 사이 - input이 특수한 성질을 만족하는 경우 O(n) 정렬(sorting)도 가능 원시적 정렬 알고리즘의 재조명 알고리즘을 보는 시간 - flow 중심 : 단계별 구조 - 관계 중심 : 재귀 구조 기초적인 정렬 알고리즘 : 평균적으로 Θ(n²)의 시간이 소요되는 정렬 알고리즘 1) 선택정렬 : - 각 루프마다 ( 최대 원소를 찾기 -> 최대 원소와 맨 오른쪽 원소 교환 -> 맨 오른쪽 원소 제외 ) -> 하나의 원소만 남을 때까지 위의 루프를 반복 - best case와 Worst case가 같음 2) 버블정렬 : 선택 정렬과 비교 연산의 횟수는 같음 (결국 같은 알고리즘) - best case와 Worst case가 같..

1. 점화식의 이해 1) 점화식 : 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 2) 병합 정렬의 수행시간 수행 시간의 점화식 : T(n) = 2T(n/2) + 오버헤드 => 크기가 n인 병합 정렬 시간은 크기가 n/2인 병합 정렬을 두 번하는 시간과 나머지 오버헤드를 더한 시간이다. 2. 점화식의 점근적 분석 방법 1) 반복 대치 (병합 정렬) : 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법 T(n) = T(n-1) + c, T(1) ≦ c - n=2ᴷ라고 가정했을 경우 주어진 T(n의 식을 계속 쪼개서 일반식을 만든다 -> 시간복잡도 구하기) - n≠2ᴷ라고 가정했을 경우 임의의 n에 대해 n과 2n 사이에 2ᴷ인 수가 존재, n ≦ 2ᴷ ≦2n T(n) = O(..

5. 점근적 표기법 1) O(Big -Oh) - 표기 정의 : 모든 n≧n₀에 대하여 f(n) ≦ cg(n)이 성립하는 양의 상수 c와 n₀가 존재하면 , f(n) = O(g(n))이다. 의미 : n₀와 같거나 큰 모든 n (즉, n₀ 이후의 모든 n)에 대하여 f(n)이 cg(n)보다 크지 않다는 것 f(n) = O(g(n)) : n₀보다 큰 모든 n에 대해서 f(n)이 양의 상수를 곱한 g(n)에 미치지 못한다는 뜻 n이 증가함에 따라 O(g(n))이 점근적 상한이라는 것 ex. f(n) = 2n² - 8n + 3일 때, f(n)의 O-표기는 O(n²) ex. 5n² = O(n²)임을 증명하라 n≧n₀ 일 때, 5n² < c · n²를 만족시키는 c가 존재 할 경우 5n² = O(n²)라고 표현할 수..

1. 알고리즘 표현 방법의 이해 1) 알고리즘의 일반적 특성 - 정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 출력 동일 입력 -> 동일 출력 (인공지능에서는 정확도의 의미가 다르기는 하나 고려사항 아님) - 수행성 : 알고리즘의 각 단계는 컴퓨터에서 구현 가능해야 한다. - 유한성 : 알고리즘은 일정한 시간(목적에 따라 만족시킬 시간) 내에 종료되어야 한다. - 효율성 : 알고리즘은 효율적(시간, 메모리)일수록 그 가치가 높아진다. 2) 최초의 알고리즘 - 유클리드의 최대공약수 알고리즘 ; 기원전 300년경에 만들어진 가장 오래된 알고리즘 최대공약수는 2개 이상의 자연수의 공약수들중에서 가장 큰 수 유클리드는 2개의 자연수의 최대 공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 ..

0. 알고리즘이란 ? 알고리즘 : 문제 해결을 위한 단계적인 절차를 의미 효율적인 알고리즘을 고안하는 것이 중요 효율적인 알고리즘 : 실행시간, 최적의 메모리 1. 다양한 형태의 알고리즘 - 순차탐색 : 하나씩 차례대로 확인하는 알고리즘 - 이진탐색 : 오름/내림차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고 이 과정을 반복하여 원하는 데이터를 찾은 탐색 알고리즘 - 그리디 알고리즘 : 남은 돈 액수를 넘지 않은 한도에서 가장 큰 액면의 동전을 계속하여 선택하는 것 2. 알고리즘 해결 방법 1) 문제 단순화 시키기 : 입력의 크기가 아주 작을 때에 문제의 답을 찾아서 힌트를 얻는다. 2) 문제의 크기를 키우면서 경우의 수 확인 3) 해답 일반화 시키기 : 수를 늘려보면서 일반적..