데이터과학 삼학년

기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요 ■ 정렬 방식 1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다. 2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저 1의 자리 숫자부터 시도를 합니다. 데이터 순..

삽입 정렬각 숫자를 적절한 위치에 삽입하는 정렬 기법들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번??? → O(N^2)의 시간 복잡도

선택 정렬가장 작은 것을 선택하여 앞으로 보내는 정렬 기법선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산 → O(N^2)의 시간 복잡도1회전: 첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다. 2회전: 두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다. 3회전: 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다. 4회전: 네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

스택 LIFO(Last In First Out) 나중에 들어온 녀석이 먼저 나가는 구조 OS에서 함수내에 잠깐 쓰이는 변수(휘발성)는 스택으로 처리됨 파이썬으로 stack 구현 class Stack: def __init__(self): self.stack = [] def pop(self): pop_value = self.stack[-1] self.stack = self.stack[:-1] return pop_value def push(self,value): self.stack.append(value) def is_empty(self): if len(self.stack) ==0: return True else : return False def check(self): return self.stack 큐 FI..

연결리스트 연결 리스트의 필요성 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음 이때 연결 리스트를 사용하여 메모리 낭비 현상 방지 가능 배열 기반 리스트의 특징 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있음 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점 원하는 위치로의 삽입이나 삭제가 비효율적 연결 리스트 구조체와 포인터를 함께 사용하여 구현 중간지점에 노드를 추가하거나 삭제할 수 있어야 함 필요할 때마다 메모리 공간을 할당받음 단일 연결 리스트 일반적으로 연결리스트의 시작노드를 Head라고 함 끝 노드의 next에는 null이 들어갈 수 있도록 연결 리스트 삽입 연결 리스트 삭제 연결 리스트의 특징 삽입과 삭제가 배열에 비해서 간단하다는 장점이..

자료구조 - 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지가 있다! - 기본적인 자료구조들 선형구조 배열 연결 리스트 스택 큐 비선형 구조 트리 그래프 - 시간복잡도 알고리즘에 사용되는 연산 횟수 - 공간복잡도 알고리즘에 사용되는 메모리의 양 - 일반적으로 시간복잡도, 공간복잡도는 반비례 관계 시간복잡도를 표기할 때는 Big-O 표기법을 사용 공간복잡도를 표기할 때는 일반적으로 MB단위로 표기