개발스토리

N(> 0)개의 계단을 한 번에 하나 혹은 둘씩 올라갈 수 있다. N개의 계단을 올라가는 방법의 수를 구하려고 한다. 1. 1개의 계단을 올라가는 방법은 몇 가지인가? - 1가지 2. 2개의 계단을 올라가는 방법은 몇 가지인가? - 2가지 3. 3개의 계단을 올라가는 방법은 몇 가지인가? - 3가지 4. N(> 0)개의 계단을 올라가는 방법의 수에 대한 점화식을 작성하라. - N이 1일 때, F(N) = 1 - N이 2일 때, F(N) = 2 - Otherwise, F(N) = F(N-1) + F(N-2) //피보나치 5. 4번의 점화식을 사용하여 N(> 0)개의 계단을 올라가는 방법의 수를 구하는 재귀 알고리즘을 작성하라. - 알고리즘 countStair(N) // 입력값 : N(0보다 큰 자연수) /..

빠른 정렬(Quicksort) 분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 수행 속도를 자랑한다. - 평균 시간복잡도: θ(n log⁡n) - 최악 시간복잡도: θ(n^2) 빠른 정렬의 진행 과정 아래의 배열이 있다. 여기서 pivot이라 불리는 기준 값을 하나 정한다. 보통 맨 앞이나 중앙을 선택한다. 나는 중앙을 pivot으로 두겠다. 그 다음, pivot을 제외한 나머지에서 가장 왼쪽은 left, 가장 오른쪽은 right로 둔다. left와 right는 pivot과 비교한다. left는 pivot보다 큰 수를 만나면, right는 pivot보다 작은 수를 만나면 대기한 뒤 서로 교환한다. 이렇게 left와 right가 움직이다가 left가 right 오른쪽에 위치하면 그만둔다. 단, piv..

분할 정복 문제를 나눌 수 없을 때까지 나눈 뒤, 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘. 분할 정복 설계 전략 1. 분할(Divide) 단계 - 문제를 같은 유형의 여러 개의 더 작은 부분 문제들로 나눈다. - 부분 문제는 풀기 쉬울 때까지 계속 나눈다. 2. 정복(Conquer) 단계 - 부분 문제들을 보통 재귀적으로 해결하여 해를 구한다. 3. 합병(Merge) 단계 - 문제에 대한 해를 구하기 위해 부분 문제들의 해를 합친다. -> 문제를 제대로 나눈다면 정복 단계는 쉬워지므로 분할 단계를 제대로 해야한다. 문제 : 최댓값 최솟값 찾기 문제: 크기가 n인 배열내의 요소들 중 최댓값과 최솟값을 찾는다. 1.최댓값을 찾는다. -- 비교 횟수: n – 1 2.남은 배열 요소들의 최솟값을..

순차 탐색(Sequential Search) 순차 탐색은 말 그대로 순차적으로 비교해가면서 찾는 것이다. data = {28, 40, 56, 63, 74, 87, 95}라는 배열이 있다. 74가 어디에 있는 지 알고 싶다. data[0]부터 값을 살펴봐서 74인지 아닌지 하나하나 확인하는 것이다. data[0], data[1] ... 탐색하다가 data[4] == 74이므로 여기서 탐색을 멈추게 되는 것이다. 복잡도(Time Complexity) 만약 data 배열에서 28을 탐색하면 1번만에 찾아낼 것이다. 40을 탐색하고자 한다면 2번만에 찾아낼 것이고, 56을 탐색하고자 한다면 3번만에 찾아낼 것이고, … 95를 탐색하고자 한다면 7번만에 찾아낼 것이다. 그럼 탐색하는게 걸리는 평균 연산 횟수는 (..