검색 알고리즘 기타 개념 > 레코드record – 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 – e.g., 사람의 레코드 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰 번호, 최종 학력, 연소득, 가족 상황 등의 정보 포함 > 필드field – 레코드에서 각각의 정보를 나타내는 부분 – e.g., 위 사람의 레코드에서 각각의 정보를 나타내는 부분 > 검색키search key 또는 키key – 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 – 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다 > 검색트리search tree – 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다 – 이를 통해 해당 레코드가 저장된 위치를 알 수..

선택 정렬 수행시간 최악: (n-1)+(n-2)+···+2+1 = Θ(n2) 평균: (n-1)+(n-2)+···+2+1 = Θ(n2) • 각 루프마다 – 최대 원소를 찾는다 – 최대 원소와 맨 오른쪽 원소를 교환한다 – 맨 오른쪽 원소를 제외한다 • 하나의 원소만 남을 때까지 위의 루프를 반복 # 일반 selectionSort(A[], n) { # A[1 ... n]을 정렬한다 for last

점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다. 예시 an = an-1 + 2 f(n) = n f(n−1) f(n) = f(n−1) + f(n−2) f(n) = f(n/2) + n 점화식의 점근적 분석 방법 (반복 대치, 추정 후 증명, 마스터 정리) 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법이다. 기본 개념 T(n) = T(n−1) + c T(1) ≤ c T(n) = T(n−1) + c = (T(n−2) + c) + c = T(n−2) + c + c = (T(n−3) + c) + c + c = T(n−3) + c + c + c … = T(1) + (n −1)c ≤ c + (n −1)c = cn 예시1 T(n) = T(n−1) + n T(1) =..

알고리즘의 점근적 분석이란? 크기가 작은 문제에서는 알고리즘의 효율성이 중요하지 않다. 그래서 비효율적인 알고리즘을 사용해도 무방하다. (오히려 더 빠른 경우도 존재한다) 크기가 충분히 큰 문제에서는 알고리즘의 효율성이 매우 중요하다. 그래서 비효율적인 알고리즘은 치명적으로 작용한다. 이렇게 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라 한다. 표기법에는 Ο, Ω, Θ, ω, ο 가 존재한다. 점근적 상한 ( asymptotic upper bound ) 정의 (lim n->INF) f(n) / g(n) 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n) ≥ f(n) } f(n) ∈ O(g(n))을 관행적으로 f(n) = O(g(n))이라고 쓴다. 직관적 의미 f(n) = O(g(n)) ⇒ ..

알고리즘의 수행 시간을 좌우하는 기준은 다양하게 잡을 수 있습니다. 예를 들면 반복문의 반복 횟수, 특정한 행이 수행되는 횟수, 함수의 호출횟수 등이 있죠. 복잡도 분석 예시 Algorithm A Algorithm B Algorithm C sum

다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS 문제 설명 부분순서와 공통 부분순서의 예시는 다음과 같다. 는 문자열 의 부분순서. 는 문자열 와 의 공통 부분순서. 최장 공통 부분순서(Longest Common Subsequence)란 공통 부분순서들 중 가장 긴 것을 말한다. 예를 들어, 다음 두 문자열의 LCS를 구하면 다음과 같다. h e r o i c a l l y s c h o l a r l y 결과 문자열 : holly, LCS : 5 주어지는 두 문자열의 LCS를 구하라. 점화식 LCS(i, j) : 문자열 X[i] = "x1,x2, … ,xi" 과 Y[j] = "y1,y2, … ,yj" 의 LCS 길이 LCS(i, j) = { 0 ( if i = 0 or j = 0 ) L..