Algorithm🐤/알고리즘

이번 시간에는 간단하게 점화식에 대한 내용을 학습해보도록 하겠습니다. 이것은 어떠한 알고리즘이 얼마나 효율적인지 분석하기 위해서 사용하는 것들입니다. 기본적으로 점화식이란 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미합니다. 예를 들면 f(n) = n * f(n - 1) f(n) = f(n - 1) + f(n - 2) 등을 이야기할 수 있습니다. 먼저 병합 정렬을 한 번 살펴보도록 하겠습니다. mergeSort(A[], p, r) { if(p < r) { q = (p + r) / 2; mergeSort(A, p, q); mergeSort(A, p + 1, r); merge(A, p, q, r); } } merge(A[], p, q, r) { 정렬되어 있는 두 배열 A[p ...

동적 계획법 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작다. 여러 개의 소문제로 분할하여...??? 응?? DP를 처음 공부하신다면 이게 무슨 말이지? 이해가 잘 안 가실 수 있으실 텐데요. 그래서 하나의 좋은 예시가 있습니다 ㅎㅎ 바로 피보나치 수열인데요. 피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있습니다. 이제 이런 피보나치 수열을 다음과 같이 분해해서 트리 형태로 나타내 보면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 볼 수 있습니다. 이 말이 즉, 위에서 설명한 "..

1. 아래 문제에 대한 recursive algorithm 을 설계하고 시간복잡도를 분석하세요 (반복문 사용 금지 , 재귀호출만 사용하기) • 배열에서 최솟값 찾기 • 배열의 원소의 총합 계산하기 • Selection Sort 2. Pancake Sorting • 교재 Exercise 9(a),(b) in Chapter 1 of [E] (page 49) • (c) 는 옵션 Homework #1 (3/26까지) • 아래 문제에 대한 recursive algorithm을 설계하고 시간복잡도를 분석하세요 (반복문 사용 금지, 재귀호출만 사용하기) • 배열에서 최솟값 찾기 • 배열의 원소의 총합 계산하기 • Selection Sort • Pancake Sorting • Exercis..