재귀 용법 (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..

대표적인 데이터 구조8: 힙 1.힙이란 -->데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 1.1 완전 이진 트리 -노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 -힙을 사용하는 이유 배열에 데이터를 넣고 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 2.힙 구조 -->힙은 최대값을 구하기 위한 구조(=최대 힙) 와 최소값을 구하기 위한 구조(=최소힙) -->힙은 두가지 조건을 갖고 있는 자료구조 - 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙 경우) 최소 힙의 경우..