Python/알고리즘 (12) 썸네일형 리스트형 동적 계획법(DP)과 분할 정복 마스터하기 1. 동적 계획법과 분할 정복의 기본 개념 2. 피보나치 수열을 통한 동적 계획법과 분할 정복의 차이점 이해 1. 동적 계획법과 분할 정복의 기본 개념 (1) 동적 계획법( Dynamic Programming ) 1) 정의 : 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘입니다. 2) 특징 - Memorization의 기법 활용 : Memorization 기법이란 이전에 풀었던 문제의 정답이나 결과 값을 저장하여, 이후의 문제를 풀 때 다시 계산하지 않고, 미리 계산된 값을 불러와서 문제를 해결하는 방법입니다. 가장 쉽게 설명하면 문제를 세부적으로 나누어서 해결할 때 이전에 계산했던 결과를 재활용.. 재귀함수의 완벽 이해 및 구현(Recursive Function) 1. 재귀함수의 기본 원리 2. 재귀함수의 기본 문제 연습 - 피보나치 수열 1. 재귀함수의 기본 원리 (1) 재귀함수의 정의 : 함수 안에 자신의 함수를 다시 호출하는 함수를 의미합니다. 이러한 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출합니다. (2) 재귀함수의 기본적인 구현 방법 2가지 일반적으로 재귀함수는 2가지 형태로 표현될 수 있습니다. 우선 기본적인 표현식을 익히고, 간단한 예시를 통해서 그 원리를 이해해보도록 하겠습니다. 1) 첫 번째 재귀함수 표현 방법 1 2 3 4 5 def function(입력): if 입력 > 일정값: # 입력이 일정 값 이상이면 return function(입력 - 1) # 입력보다 작은 값 else: ret.. 기본 정렬3. 선택 정렬(Selection Sort) 구현하기 1. 선택 정렬(Selection Sort)의 기본 개념 2. 선택 정렬의 예시와 원리 파악 3. 실제 코드 구현 및 예시를 통한 이해 1. 선택 정렬(Selection Sort)의 기본 개념 선택 정렬(Selection Sort)를 간단하게 정의하면, 주어진 데이터 중 최소값을 찾아서, 계속 맨앞으로 위치를 바꾸면서 순서를 바꾸는 방법입니다. 그림을 보면서 이해하면 더 쉽게 이해할 수 있습니다. (출처: en.wikipedia.org/wiki/Selection_sort) 위의 사진에서 보이는 것처럼 주어진 숫자 중 3이 가장 최소값이어서 자리를 바꾼다면 6과 자리를 바꾸게 되겠죠. 이런식으로 하나하나 계속 비교하면서 자리를 찾아가는 방법입니다. 기본 개념을 3단계로 요약하면 다음과 같습니다. 1단계. .. 기본 정렬2. 삽입 정렬(Insertion Sort) 1. 삽입 정렬(Insertion Sort)의 기본 개념 2. 삽입 정렬의 예시와 손 코드 구상 3. 삽입 정렬의 코드 구현 4. 삽입 정렬의 실제 활용 1. 삽입 정렬(Insertion Sort)의 기본 개념 삽입 정렬의 기본 원리를 3단계로 요약하면 다음과 같습니다. 첫 번째. 삽입 정렬은 두 번째 인덱스부터 시작합니다. 두 번째. 해당 인덱스(key 값) 앞에 있는 데이터부터 비교해서, key 값이 더 작으면 그 데이터 값을 뒤 인덱스로 복사한다 세 번째. 이를 key 값이 더 큰 데이터를 만날 때까지 반복하고 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 이를 시각화하여 표현하면 다음과 같다. (출처: commons.wikimedia.org/wiki/File:Insertion-sort.. 이전 1 2 다음
