동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 1. 정의 - 동적계획법 (DP 라고 많이 부름) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 - 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 - Memoization 기법을 사용함 - Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 - 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 - 예: 피보나치 수열 ..

재귀 용법 (recursive call, 재귀 호출) 고급 정렬 알고리즘에서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익히기로 합니다. 1. 재귀 용법 (recursive call, 재귀 호출) - 함수 안에서 동일한 함수를 호출하는 형태 - 여러 알고리즘 작성시 사용되므로, 익숙해져야 함 2. 재귀 용법 이해 - 예제를 풀어보며, 재귀 용법을 이해해보기 예제 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기 예제 – 분석하기 간단한 경우부터 생각해보기 2! = 1 X 2 3! = 1 X 2 X 3 4! = 1 X 2 X 3 X 4 = 4 X 3! - 규칙이 보임: n! = n X (n - 1)! 1. 함수를 하나 만든다. 2. 함수..

대표적인 정렬2: 삽입 정렬 (insertion sort) 1. 삽입 정렬 (insertion sort) 란? -삽입 정렬은 두 번째 인덱스부터 시작 - 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 -이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 직접 눈으로 보면 더 이해가 쉽다 for index in range(10, 1, -1): print (index) - 출력:10 9 8 7 6 5 4 3 2 2. 어떻게 코드로 만들까? (결국 프로그래밍으로 일반화할 수 있도록 만드는 것) - 알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다. - 데이터가 두개 일 때 동작하는 삽입..

대표적인 정렬2: 삽입 정렬 (insertion sort) 1. 삽입 정렬 (insertion sort) 란? -삽입 정렬은 두 번째 인덱스부터 시작 - 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 -이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 직접 눈으로 보면 더 이해가 쉽다 for index in range(10, 1, -1): print (index) - 출력:10 9 8 7 6 5 4 3 2 2. 어떻게 코드로 만들까? (결국 프로그래밍으로 일반화할 수 있도록 만드는 것) - 알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다. - 데이터가 두개 일 때 동작하는 삽입..

대표적인 정렬1: 버블 정렬 A. 알고리즘 연습 방법 - 알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함 - 모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작 - 이번 챕터부터 알고리즘 시작입니다.! - 알고리즘 연습 방법 1. 연습장과 펜을 준비하자. 2. 알고리즘 문제를 읽고 분석한 후에, 3. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다 4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다. 5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고, 6. 각 문장을 코드 레벨로 적는다 7. 데이터..

4. 힙 구현 힙과 배열 -> 일반적으로 힙 구현 시 배열 자료구조를 활용 -> 배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 구현이 좀 더 수월함 - 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 //2 - 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2 - 오른쪽 자식 노드 인덱스 번호 = 부모 인덱스 번호 * 2 +1 #예1 – 10 노드의 부모 노드 인덱스 2//2 #예1 -15 노드의 왼쪽 자식 노드 인덱스 번호 1*2 #예1 – 15 노드의 오른쪽 자식 노드 인덱스 번호 2*2+1 힙에 데이터 삽입 구현 (Mas Heap 예) 힙 클래스 구현1 class Heap: def __init__(self, data): self.h..