본문 바로가기

알고리즘4

[알고리즘]다이나믹 프로그래밍 Memoization & Tabulation 다이나믹 프로그래밍이란? 하나의 문제를 부분 문제로 나누어 해결 한 후 이를 이용해서 더 큰 문제를 푸는 프로그램이 방식을 말한다. 문제를 나누고 푸는 과정에서 Memoization(Top Down)과 Tabulation(Botton up)이 사용 된다. 두 가지 방식의 공통점을 중복되는 부분 문제의 비효율을 해결 해준다는 것이다. 아래 그림을 보면 피보나치 수열 6을 구하기 위해 여러 중복된 계산이 일어나는걸 볼 수 있다. f(6) = f(5) + f(4) f(5) = f(4) + f(3) f(4) = f(3) + f(2) ...... 차이점은 Memoization은 일반적으로 재귀함수를 사용하며 Tabulation은 반복문을 사용하여 처리한다. Memoization의 단점은 재귀함수로 이루어져 있어 .. 2021. 2. 24.
[알고리즘] 재귀함수 활용 피보나치 수열 재귀는 자기 자신을 재 참조하는 방법을 말한다. 재귀 호출(Recursive call)의 형태로 많이 사용 한다. 재귀함수란 함수안에서 자신을 다시 호출하여 작업을 수행하는 방식을 의미한다. 예시: def recursive_call(): print("Recursive call") recursive_call() recursive_call() 위의 코드를 보면 recursive_call 함수 안에서 다시 recursive_call 함수를 호출 하고 있는 걸 볼 수 있다. 실행을 하면 print문을 실행 후 아래 사진과 같은 에러가 발행하는데요, 왜냐하면 Python에서 maximum recursion depth 의 최대값이 1000으로 정해져 있어서 에러가 발생한 것이다. recursive_call함수를 호.. 2021. 2. 14.
[알고리즘] 삽입 정렬 정리 삽입 정렬(Insertion sort)은 List의 두번째 인덱스 부터 시작하여 Index - 1로 순회하여 정렬 하는 방식이다. 즉 두번째 인덱스와 첫번째 인덱스를 비교,교체하고, 세번째 인덱스와 두번째, 첫번째 인덱스 순으로 비교, 교체를 하게 된다. 시간복잡도는 최선의 경우 O(n) 최악의 경우O(n^2) 예시: [10, 68, 51, 81, 47] 정렬되지 않은 List 먼저 두번째 인덱스를 기준으로 해서 인덱스 - 1로 순회를 한다. 두번째 인덱스 값 68과 인덱스 - 1인 첫번째 인덱스 값 10과 비교, 10이 더 작으니 교체 없이 다음 과정으로 [10, 68, 51, 81, 47] 과정 1 [10, 68, 51, 81, 47] 세번째 인덱스 값 51과 두번째 인덱스 값 68과 비교, 51이 .. 2021. 2. 13.
[알고리즘] 선택 정렬 정리 선택 정렬(Selection Sort)은 주어진 List 맨 앞의 인덱스를 기준값으로 하여 최소값을 찾아 순회하며 비교, 교체를 하는 방식이다. 이 과정을 한번 실행 하면 맨 앞의 인덱스 값을 앞으로 옮겨 순회를 하면서 비교, 교체를 반복하게 된다. 시간복잡도는 O(n^2) 예시: [90,27,22,28,20,18] 정렬되지 않은 데이터가 있다. 선택 정렬을 하여 정렬을 하면 아래와 같다. 먼저 기준점이 되는 인덱스는 맨 앞의 0번째 인덱스로 하여 순회를 한다. 기준점의 값은 90이고 최소값 18과 자리를 교체 한다. [90, 27, 22, 28, 20, 18] 과정 1 [18, 27, 22, 28, 20, 90] 인덱스에 +1을 하여 1번째 인덱스로 하여 또 순회를 한다. 기준점의 값은 27이고 최소값.. 2021. 2. 13.

티스토리툴바