차쟁이파이썬

# 1. 병합정렬(merge sort)* 재귀 용법을 활용한 정렬 알고리즘* 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔* 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬* 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병#2. 알고리즘 이해하기'''data_list = [1, 9, 3, 2]'''1. [1,9] 로 나눔2. 앞부분은 [1], [9]로 나누고 뒷부분은 [3],[2]로 나눔3. 정렬해서 합침 [1,9] , [2, 3]4. [1,9] , [2, 3] 을 합침(단, 아래와 같은 조건으로) * 1 2 이므로 리스트에 2를 추가 [1,2] * 9 > 3 이므로 리스트에 3을 추가 [1,2,3] * 9 밖에 없으니 리스트에 9를 추가 [1,2,3,9] #3. 알고리즘..

1. 분할 정복(Divide and Conquer)* 문제를 여러 개의 독립적인 하위 문제로 나눠서 각각 해결한 후, 그 결과를 합쳐서 원래 문제를 해결하는 방식* 재귀적으로 하위 문제를 풀고, 합병 과정을 거치는 게 특징2. 분할 정복을 사용하는 대표적인 정렬: 퀵 정렬* 정렬 알고리즘의 꽃* 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성* 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함2-1. 퀵 정렬 알고리즘 구현하기* 만약 리스트 갯수가 한 개이면 해당 리스트를 반환* 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 설정* left, right 리스트 변수를 만듦* 맨 앞의 데이터를 뺀 나머지..

1. 동적 프로그래밍(Dynamic Programming)* 복잡한 문제를 작은 하위 문제들로 나누고 그 결과를 재사용하여 효율적으로 문제를 해결하는 알고리즘 기법* 주어진 문제를 풀 때,같은 하위 문제를 여러 번 푸는 대신,그 결과를 저장해 두고 필요할 때 다시 사용하는 방식1-1. 동적 프로그래밍의 접근 방식* 메모이제이션(Bottom-Down): 큰 문제를 풀기 위해 재귀적으로 하위 문제들을 풀면서, 이미 계산된 하위 문제는 저장된 값을 재사용하는 방식* 테이블 방식(Bottom-Up): 작은 하위 문제부터 시작해 차례대로 계산해가며, 최종적으로 큰 문제를 해결하는 방식1-2. 동적 프로그래밍 알고리즘* 피보나치 수열 n을 입력받아서 계산* [피보나치](https://namu.wiki/w/%ED%9..

1-1. 알고리즘 복잡도 계산이 필요한 이유* 정수의 절대값을 구하는 방법 * 방법1: 정수값을 제곱한 값에 루트 씌우기 * 방법2: 값이 음수인지 확인하고 음수일때 -1을 구하기> 다양한 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함1-2. 알고리즘 복잡도 계산 항목* 시간 복잡도: 알고리즘 실행 속도* 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈### 1-3. 알고리즘 오메가 성능 표기법* 오메가 표기법: 알고리즘 최상의 결과를 표기* 세타 표기법 : 알고리즘 평균 결과를 표기* 빅오 표기법 : 최악의 실행 결과를 표기(가장 많이 사용함, 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미)# **2.시간 복잡도*** 알고리즘이 수행되는 시간이 입력 크기에 따라 어떻게 변하..

#1.재귀함수(recursive call)* 함수 안에서 동일한 함수를 호출하는 형태* 여러 알고리즘, 고급 정렬 알고리즘 작성시 자주 사용됨### 1-1. 재귀 함수 호출 분석* 2! = 1 * 2* 3! = 1 * 2 * 3### 1-2. 규칙'''n! = n (n-1)!'''* 함수로 만들기 = def factorial(num)* factorial(num)은 num > 1 이라면 return n * factorial(n-1)* factorial(num)은 num = 1 이라면 return n### 1-3. 검증* 2! * factorial(2)이면 2 > 1 이므로 2 * factoral(1) * factorial(1)은 1이므로 return 2 * 1 * 결과는 2 * 3! * factor..

1. 기본정렬# 1.버블 정렬(Bubble sort)* 정렬(sorting) : 어떤 데이터들이 주어졌을떄 이를 정해진 순서대로 나열하는것* 정렬은 프로그램 작성시 빈번하게 필요로 함* 다양한 알고리즘이 고안되었으며, 알고리즘 학습은 필수* 다양한 정렬 알고리즘 이해를 총해서 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석에 대해서도 이해할 수 있음* 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에있는 데이터보다 자리를 바꾸는 정렬 알고리즘# 1-1. 버블 정렬 알고리즘 구현하기* 데이터가 네개일때(예: data_list=[1,9,3,2])* 1차 로직 적용 * 1과 9 비교, 자리바꿈없음 [1,9,3,2] * 9..

# 1. 힙(heap) 이란?* 데이터에서 최댓값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(complt Binary Tree)* 완전 이진 트리 : 노드를 삽입할때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리# 2. 힙의 구조*** 힙은 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류할수 있음* 각 노드릐 값은 해당 노드의 자식 노드가 가진값보다 크거나 같다.(최대 힙의 경우)* 완전 이진 트리 형태를 가짐# 3. 힙과 이진 탐색 트리의 공통점과 차이점* 공통점 : 힙과 이진 탐색 트리는 이진트리임* 차이점 * 1. 힙은 각 노드의 값이 자식 노드보다 크거나 같음(max heap의 경우) * 2. 이진 탐색 트리는 왼쪽 자..

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

#1. 해시 테이블(Hash Table)* 키(key)에 데이터(value)를 저장하는 데이터 구조* 파이썬에서는 해시를 별도 구현할 필요가 없음* 파이썬 딕셔너리(Dictionary) 타입이 해시 테이블의 예* key를 통해 데이터를 바로 찾을 수 있으므로 검색 속도가 빨라짐* 보통 배열로 미리 hash table 사이즈 만큼 생성 후에 사용#2. 알아둘 용어* 해시(Hash): 임의 값을 고정 길이로 변환하는 것* 해시 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조* 해시 함수(Hashing Function): key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수* 해시 값(Hash Value) 또는 해시 주소(Hash Address): key를 해..

1. 더블 링크드 리스트- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능class Node: def __init__(self, data, prev=None, next=None): self.prev = prev self.data = data self.next = nextclass NodeMgmt: def __init__(self, data): self.head = Node(data) self.tail = self.head def insert(self, data): if self.head == None: self.head = Node(data) self.tail = self.head else: node = self.head ..