데이터 분석가 판교데싸

1. 탐욕 알고리즘 이란? - Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움- 최적의 해에 가까운 값을 구하기 위해 사용됨- 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식 1.2 탐욕알고리즘의 예 그리디 -> 두 번째 예제

1. 퀵 정렬 (quick sort) 이란? 1. 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함 2. 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함 3. 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함 Pivot을 기준으로 Pivot과 나머지를 비교 함 작은데이터 , pivot , 큰데이터 - > 이렇게 정렬 함

1. 재귀 용법 (recursive call, 재귀 호출) * 함수 안에서 동일한 함수를 호출하는 형태 * 여러 알고리즘 작성시 사용되므로, 익숙해져야 함 재귀는 대표적인 스택의 예시 대표적인 예시 -> 팩토리얼 재귀는 웬만하면 손으로 풀고 + 손으로 푼것을 코드로 바꾸기

1. 이진 탐색 (Binary Search) 이란? * 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 ### 다음 문제를 먼저 생각해보자 * 중간 값을 찍고 크면 오른 쪽 작으면 왼 쪽을 찍는 알고리즘 (계속 반복) -> 결국 반씩 제거하면서 마지막으로 가서 탐색을 완료 구현 코드는 이렇다

### 1. 순차 탐색 (Sequential Search) 이란? * 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 * 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 데이터 준비 ) 만들어 놓은 데이터 data_list를 통해서 [index]로 인덱스를 잡고 for문으로 하나씩 돌면서 index에 맞는 것 ( 같은 수)이나오면 index를 출력하고 같은 수가 없다면 -1 출력

* 단순히 표현하면 인접한 데이터를 비교해서 앞에있는 데이터가 뒤에있는 데이터 보다 크면, 자리를 바꾸는 정렬 알고리즘 for index in range(데이터길이-1): for index2 in range(데이터길이 -1): if 앞데이터 > 뒤데이터: swap(앞데이터 , 뒤데이터) for index in range(데이터길이-1): for index2 in range(데이터길이 -1): if 앞데이터 > 뒤데이터: swap(앞데이터 , 뒤데이터) -> 이 형태를 외우자

1. 주어진 데이터 중 최소 값을 찾는다.* 다음과 같은 순서를 반복하며 정렬하는 알고리즘 1. 주어진 데이터 중, 최소값을 찾음 2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 어떻게 코드로 만들까? * 데이터가 두 개 일때 - 예: dataList = [9, 1] - data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환 * 데이터가 세 개 일때 - 예: data_list = [9, 1, 7] - 처음 한번 실행하면, 1, 9, 7 이 됨 - 두 번째 실행하면, 1, 7, 9 가 됨 * 데이터가 네 개 일때 - 예: data_list = [9, 3, 2, 1] - ..

1. 힙 (Heap) 이란? 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛)O(logn) 이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 힙은 다음과 같이 두 가지 조건을..

1. 트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node): Child No..

1. 해쉬 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 2. 알아둘 용어 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터..