Algorithm

재귀 함수란, 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀함수는 매 호출시마다 입력값이 변한다. 입력값의 변화가 없는 호출은 무한히 반복된다. 입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재

입력 : 리스트에 n개의 수와 1과 n 사이의 자연수 k가 주어진다출력 : k번째로 작은 수 를 찾아 리턴한다목적 : 비교횟수를 되도록 줄인다상한(upper bound) : 어떠한 값 x가 있고 집합 A의 모든 원소보다 크거나 같을 때, x를 상계라고 한다. 그리고 이

어떤 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고, 다시 합병하여 문제의 답을 얻는 알고리즘크기가 작아질 뿐 문제 자체는 변하지 않기 때문에, 분할은 재귀적 분할재귀적으로 나타낼 수 있기에 수행시간 $T(n)$은 점화식으로 표현될 수 있음Selection에서 배

리스트에 저장된 값들을 크기 순서에 따라 재배열하는 문제→ 되도록 비교 횟수와 자리바꿈 횟수를 최소로 하는 것이 목표크기가 같은 숫자인 경우, 원래 입력 순서를 정렬 후에도 유지 ⇒ Stable 출처 : https://en.wikipedia.org/wi

문제를 작은 문제로 분할하여 분할된 문제의 해답을 기록해 놓은 후 더 큰 문제의 해답을 계산할 때 재사용하는 방법을 의미문제의 해답의 성질을 분석해 적절하게 작은 문제로 분할분할된 문제의 해답이 표에 기록되어 있다면, 그 해답들을 조합해 더 큰 문제의 해답을 계산하여

미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식간단하고 빠르지만, 최적의 답이 보장되지 않음최적 부분 구조 (Optimal Structure)탐욕적 선택 속성 (Greedy Choice Property)각 단계에서의 탐욕스런 선택이 최종 답을 구하

모든 조합에서 나올 수 있는 해를 다 살펴본다 → 조건이 만족할 때만해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법DFS 등으로 모든 경우의 수를 탐색조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의그러한 상황일 경우에는 탐색을 중지그