ML&DL&AI/자료구조
-
그래프(Graph)ML&DL&AI/자료구조 2024. 6. 18. 16:13
그래프(graph)사물을 정점(vertex)과 간선(edge)으로 나타내는 위한 도구 - 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식- 인접 리스트(adjacency list) : 연결 리스트를 이용하는 방식 인접 행렬(adjacency matrix)그래프를 2차원 배열로 표현03730무한7무한0 인접 행렬 - 무방향 무가중치 그래프모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.0110101011010010 인접 행렬 - 방향 가중치 그래프모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.모든 ..
-
우선순위 큐ML&DL&AI/자료구조 2024. 6. 18. 15:27
우선순위 큐(Priority Queue)우선순위 큐는 우선순위에 따라서 데이터를 추출하는 자료구조컴퓨터 운영체체, 온라인 게임 매칭 등에 활용 된다.우선순위 큐는 일반적으로 힙(heap)을 이용해 구현지료구조추출되는 데이터스택(stack)가장 나중에 삽입된 데이터큐(queue)가장 먼저 삽입된 데이터우선순위 큐(priority queue)가장 우선순위가 높은 데이터 데이터의 개수가 N개 일때, 구현 방식에 따라 시간 복잡도우선순위 큐 구현 방식삽입시간삭제시간리스트 자료형O(1)O(1)힙(Heap)O(logN)O(logN) 일반적인 형태의 큐는 선형적 구조가지며, 우선순위 큐는 이진트리의 구조를 사용하는 것이 일반적이다. 힙(Heap)원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조완전 이진트..
-
이진 탐색 트리ML&DL&AI/자료구조 2024. 6. 17. 15:41
트리(Tree)가계도와 같이 계층적인 구조를 표현할 때 사용 할 수 있는 자료구조 루트 노드(root node) : 부모가 없는 최상위 노드단말 노드(leaf node) : 자식이 없는 노드 트리 용어 정리트리 부모와 자식 관계 성립형제 관계 : 트리의 같은 레벨선상에 있는 노드들이 서로 형제 깊이(depth) : 루트 노드에서의 길이(length)길이(length) : 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수높이(height) : 루트 노드에서 가장 깊은 노드 까지의 길이를 의미 이진 트리(Binary Tree)최대 2개의 자식을 가질 수 있는 트리 이진 탐색 트리(Binary Search Tree)다수의 데이터를 관리(조회, 저장, 삭제)하기 위한 가장 기본적인 자료구조왼쪽 자식 노드 ..
-
덱(Deque)ML&DL&AI/자료구조 2024. 6. 17. 13:55
덱(Deque)스택과 큐의 기능을 모두 가지고 있다.포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요하다.Python에서 큐(queue)의 기능이 필요할 때, 간단히 덱(deque)을 사용한다.데이터 삭제와 삽입 모두에서 0(1)의 시간 복잡도가 소요된다. 덱의 동작 예시좌측 삽입4 좌측 삽입3 좌측 삽입2 좌측 삽임1우측 삽입5 우측 삽입6 우측 삽입7 우측 삽입8우측 삭제 좌측 삭제 우측 삭제 좌측 삭제최종 : 3 4 5 6 덱의 시간 복잡도 연산수행 시간설명1좌측 삽입(Append Left)O(1)덱의 가장 왼쪽에 새 데이터 삽입2좌측 삭제(Pop Left)O(1)덱의 가장 왼쪽에서 데이터 추출3우측 삽입(Append Right)O(1)덱의 가장 오른쪽에 새 데이터 삽입4우..
-
큐(queue)ML&DL&AI/자료구조 2024. 6. 17. 13:30
큐(queue)먼저 삽입된 데이터가 먼저 추출되는 자료 구조ex) 게임에서 대기 큐에서 먼저 대기한 유저가 먼저 매칭이 됩니다. 큐의 동작 원리삽입3 삽입5삭제(3번 삭제)삽입7삭제(5번 삭제)삽입8삭제(7번 삭제)삽입2 삽입9최종(8 2 9) 연결 리스트로 큐 구현큐를 연결 리스트로 구현하면, 삽입과 삭제가 있어서 O(1)를 보장할 수 있다.연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다. 머리(head) 남아 있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터꼬리(tail) 남아 있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터 연결 리스트 삽입 연산삽입할 떄는 꼬리(tail) 위치에 더이터를 넣는다. 연결리스트 삭제 연산삭제할 때는 머리(h..
-
스택ML&DL&AI/자료구조 2024. 6. 14. 17:21
스택(Stack)스택은 먼저 들어온 데이터가 나중에 나가는(FILO, 선입후출) 자료 구조입니다.흔히 박스가 쌓인 형태를 스택(Stack)이라고 비유합니다. 스택 자료 구조의 중요성스택은 가장 기본적인 자료 구조 중 하나입니다.기계 학습 분야뿐만 아니라 다양한 프로그램을 개발할 때도 필수적으로 사용됩니다. 스택 자료의 시간 복잡도 연산시간 복잡도설명1삽입(Push)O(1)스택에 원소를 삽입하는 연산2추출(Pop)O(1)스택에서 원소를 추출하는 연산3최상위 원소(Top)O(1)스택의 최상위 원소(마지막에 들어온 원소)를 확인하는 연산4EmptyO(1)스택이 비어 있는지 확인하는 연산 연결 리스트로 스택 구현스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장 할 수 있다.연결 리스트로 구..
-
파이썬 리스트 자료형 함수ML&DL&AI/자료구조 2024. 6. 14. 16:46
연산시간 복잡도사용 예제설명1 Indexing O(1) arr[i] 리스트의 특정 인덱스의 값 얻기 2 Storing O(1) arr[i] = x 리스트의 특정 인덱스에 값 저장하기 3 Append O(1) arr.append(5) 리스트의 가장 뒤에 데이터 넣기 4 Pop O(1) arr.pop() 리스트의 가장 뒤에서 원소 꺼내기 5 Length O(1) len(arr) 리스트의 길이 얻기 6 Clear O(1) arr.clear() 리스트 내 모든 원소 제거하기 7 Slicing O(b-a) arr[a:b] 리스트에서 인덱스 a부터 b-1까지의 원소만 꺼내 새 list 만들기 8 Extend O(len(other)) arr.extend(other) 기존 리..
-
연결 리스트ML&DL&AI/자료구조 2024. 6. 14. 16:09
연결리스트(Linked List)각 노드가 한 줄로 연결되어 있는 자료 구조각 노드는 (데이터,포인터) 형태를 가진다.포인터 : 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.연결성 : 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다. 연결 리스트 vs 배열배열(Array) - 특정 위치 데이터 삭제배열에서는 특정 위치의 데이터를 삭제할 때 O(n) 시간이 소요됩니다. 이는 삭제 후 나머지 요소들을 한 칸씩 이동시켜야 하기 때문입니다.- 데이터 삽입배열에서 특정 위치에 데이터를 삽입할 때도 O(n) 시간이 소요됩니다. 이는 삽입할 위치 이후의 요소들을 한 칸씩 이동시켜야 하기 때문입니다. 연결 리스트(Linked List)- 특정 위치 데이터 삭제연결 리스트에서는 특정 위치의 데이터를 삭제..