본문 바로가기

Algorism10

피보나치(Fibonacci) 피보나치 알고리즘 피보나치 수열은 앞 두개 항의 값을 더한 것이 뒤 항의 값이 되는 수열이다. [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...] 이런 형태의 피보나치 수열에서 n번째 항의 값을 찾는 알고리즘을 만들어보자. 재귀 알고리즘 사용 피보나치 문제는 재귀 알고리즘을 이용하여 간략한 형태의 코드를 짤 수 있다. 재귀 알고리즘을 사용하기 위해서는 두 가지가 정의되어야 한다. 문제 정의, 탈출 요건이다. 피보나치 수열은 'n번째 항의 값은 n - 1항과 n - 2 항의 값과 같다' 로 정의할 수 있다. 즉, f(n) = f(n-1) + f(n -2)로 정의할 수 있다. 다만 첫째항, 두번째항의 경우 n - 1항과 n - 2항이 없어 조건이 충족되지 않는다. 따라서 더이상 위 식.. 2022. 7. 28.
퀵 정렬(Quick sort) 퀵정렬 시간복잡도 공간복잡도 모든 값을 비교해야하므로 N 반복을 거듭할 때마다 반씩 줄어듦으로 log N O(N log N) 배열을 병합할 때 병합 결과를 담아놓을 배열이 필요함 O(N) 일반적으로 pivot이라고 부르는 임의의 기준값을 정하고 pivot보다 큰 값, 작은 값을 정렬하는 알고리즘. 분할 정복과 재귀용법을 사용. [6, 3, 1, 4, 5, 2, 7] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 먼저 기준이 될 pivot을 결정한다. 간단하게 첫번째 요소를 pivot으로 결정해보자. ☝퀵정렬은 어떤 값이 pivot으로 설정되냐에 따라 성능이 큰 영향을 받는다. 최악의 경우 시간 복잡도가 O(N²)이 될 수도 있다. 그래서 보통 pivot 값은 배열의 첫 값, 중간 값, 마지막 값 중.. 2022. 7. 14.
병합 정렬(Merge sort) 병합정렬 시간복잡도 공간복잡도 모든 값을 비교해야하므로 N 반복을 거듭할 때마다 반씩 줄어듦으로 log N O(N log N) 배열을 병합할 때 병합 결과를 담아놓을 배열이 필요함 O(N) 주어진 요소가 각 1개가 될 때까지 분할한 후 각 요소들을 병합하는 과정에서 비교하여 정렬하는 방식. 분할 정복과 재귀 용법을 이용하는 알고리즘. [7, 4, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 먼저 모든 요소가 1개가 될 때까지 반으로 쪼갠다. 전체 배열의 길이를 2로 나눈 후 소숫점과 나머지는 버리고 몫만 얻어서 배열을 반으로 나눈다. len(input_array) // 2 => [7, 4] [5, 1, 3] => [7] [4] [5] [1, 3] => [7] [4] [5] [1] .. 2022. 7. 13.
삽입 정렬(Insertion sort) 삽입정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 검색 범위를 넓혀가며 전체 요소까지 비교하기 위해 N N x N = O(N²) 비교 후 배열 내 스왑을 하기 위해 O(1) 정렬 범위를 한칸씩 확장하여 새로 비교할 값을 이미 정렬된 값과 비교하여 정렬하는 알고리즘 [7, 4/, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 5개의 요소를 가지고 있다. 이 중 맨 앞의 2개 요소만 두고 첫번째 비교를 시작한다. 7과 4중 4가 더 작기 때문에 둘의 위치를 바꿔준다. [4, 7/, 5, 1, 3] 첫번째 순회가 끝났다. 두번째 순회를 시작한다. 이제 검색범위를 넓혀 3번째 요소, 2번 인덱스에 있는 요소를 추가하여 뒤에서부터 비교한다. 7과 5중 5가 더 작기 때문.. 2022. 7. 12.

티스토리툴바