728x90 Quality control (Univ. Study)/Algorithm Design40 Lecture5,6 - 정렬알고리즘(1) Selection Sort 선택정렬(Selection Sort)은 배열(array)을 정렬할 때 가장 간단한 방법 중 하나이다. 이 알고리즘은 배열을 처음부터 끝까지 반복하면서 가장 작은 값을 찾아서 배열의 맨 앞에 위치시키는 과정을 반복하는 방식으로 동작한다. 이전에 다루었었기 때문에 정렬알고리즘은 간단하게 그림으로 설명하고 넘어간다. SelectionSort Psuedo code SelectionSort(A) // A는 배열 n = A.length // 배열의 길이를 구합니다. for i = 0 to n-1 do // 첫 번째 인덱스부터 끝까지 반복합니다. minIndex = i // 가장 작은 값의 인덱스를 저장할 변수를 초기화합니다. for j = i+1 to n do // i 다음 인덱스부터 끝.. 2023. 3. 20. Lecture4 - 점화식과 점근적 복잡도 분석 점화식의 이해 점화식이란 어떤 함수(보통 입력 변수를 n등의 미지수로 표현)를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 식이다. 병합 정렬 알고리즘을 통해 살펴보자 mergeSort(A[],p,r){ if(p 2023. 3. 8. Lecture3 - 알고리즘 설계와 분석의 기초(2) Big O relation d>c>1인 경우 b>1, c,d>0인 경우 b>1, d>0인 경우 c>b>1인 경우 합성 함수에서의 Big O relation Big Omega notation Ω(g(n))과 같이 표기하고 적어도 g(n)의 비율로 증가하는 함수라는 뜻으로 O(g(n))과 대칭적이라고 볼 수 있다. Formal definition은 Ω(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0 , cg(n)≤f(n) }과 같은 방식으로 정의된다. 직관적으로 생각해보면 "f(n) = Ω(g(n)) ⇒ f는 g보다 느리게 증가하지 않는다"라고 생각할 수 있다. Big Theta notation Θ(g(n))과 같이 표기하고 정확히 g(n)의 비율로 증가하는 함수를 뜻한다. F.. 2023. 3. 6. Lecture1,2 - 알고리즘 설계와 분석의 기초(1) 알고리즘이란? 알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 체계적 으로 기술한 것을 말한다. 다음은 문제, 입출력 및 알고리즘에 대한 간단한 예시이다. ▪ 문제: 100명의 학생들의 시험점수 중 최대값을 찾으라 ▪ 입력: 100명의 학생들의 시험점수 ▪ 출력: 위 100개의 시험점수들 중 최대값 ▪ 알고리즘: Algorithm maxScore(x[], n) { x[1...n]의 값을 차례대로 보면서 최대값을 계산 위에서 찾은 최대값을 반환 } 또한 현존하는 어떤 알고리즘으로도 polynomial시간 내에 최적의 해를 구할 수 없는 "Travelling Salesman Problem"도 있다. ▪ 입력: 어떤 영업사원이 방문해야 할 고객 n명의 위치 ▪ 출력: 모든 .. 2023. 3. 5. 이전 1 2 3 4 5 다음 728x90
