본문 바로가기

Study/Data Structure8

[Data Structure] Python의 주요 자료형과 시간 복잡도 정리 파이썬에서 각 자료형의 동작 속도는 내부 구조가 어떻게 되어 있는지, 어떤 작업을 수행할 것인지에 따라 달라집니다.따라서 각 자료형의 시간 복잡도를 이해하면 상황에 따라 최적의 자료형을 선택하는데 도움이 되겠죠! 이번 포스팅에서는 파이썬의 주요 자료형과 그 시간 복잡도를 살펴보겠습니다.리스트(List)★ 주요 특징 : 가변성(Mutable)이 있어 요소 추가/삭제 가능접근 : O(1) 특정 인덱스에 접근하는 데 상수 시간이 걸립니다.삽입 : O(n) (중간에 삽입할 경우), O(1) (끝에 추가할 경우) 리스트 중간에 값을 삽입하면 그 뒤의 요소들을 이동시켜야 합니다.삭제 : O(n) (중간에 삭제할 경우), O(1) (끝에 삭제할 경우) 끝에서 요소를 삭제할 때는 빠르지만 중간에서 삭제하면 삽입과 마찬.. 2024. 11. 10.
[Data Structure] 그래프(Graph) 본 포스트는 데이터 구조 그래프(Graph)에 대해 공부한 내용을 정리한 것입니다. 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 데이터 구조로,아이템들과 이들 사이의 연결 관계를 표현하는 구조입니다. 그래프는 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현할 때 유용합니다! 그럼 본격적으로 그래프에 대해 알아보도록 하겠습니다.그래프의 유형무향 그래프 (Undirected Graph)두 정점(노드) 사이의 간선(엣지)이 방향성을 가지지 않는 그래프간선이 정점 A에서 B로 가는 것이 아니라, 정점 A와 정점 B가 단순히 연결만 되어 있는 것ex) 친구 관계를 나타내는 그래프 (A와 B가 친구라면  B와 A도 친구) 유향 그래프.. 2024. 9. 10.
[Data Structure] 이진 트리(Binary Tree) 본 포스트는 데이터 구조 이진 트리(Binary Tree)에 대해 공부한 내용을 정리한 것입니다. 이진 트리는 '트리' 구조의 특수한 형태로,모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리입니다. 트리에 대해 더 자세한 내용을 알고 싶으시다면, 아래 포스트를 참고하세요![Data Structure] 트리(Tree) [Data Structure] 트리(Tree)본 포스트에서는 트리(Tree)에 대해 이야기해보려 합니다.  트리(Tree)는 컴퓨터 과학에서 매우 중요한 데이터 구조 중 하나로, 데이터의 저장 및 검색 효율성을 높이기 위해 다양한 응용 프로그램joungnx123.tistory.com 그럼 본격적으로 이진 트리에 대해 알아보도록 하겠습니다.이진 트리의 특징각 노드가 자식 노드를 최대 2.. 2024. 8. 31.
[Data Structure] 힙(Heap) 본 포스트는 힙(Heap)에 대해 공부한 내용을 정리한 것입니다. 힙(Heap)은 이진 트리(Binary Tree) 기반의 자료구조로, 최대값 또는 최소값을 빠르게 찾는 연산에 유리합니다. 이진 트리에 대해 더 자세한 내용을 알고 싶으시다면, 아래 포스트를 참고해주세요~[Data Structure] 이진 트리 (Binary Tree) [Data Structure] 이진 트리 (Binary Tree)본 포스트는 데이터 구조 이진 트리(Binary Tree)에 대해 공부한 내용을 정리한 것입니다. 이진 트리는 '트리' 구조의 특수한 형태로,모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리입니joungnx123.tistory.com 그럼 본격적으로 힙에 대해 알아보도록 하겠습니다.힙의 장단점장점효율적인.. 2024. 8. 29.
[Data Structure] 이진 탐색 트리(Binary Search Tree, BST) 본 포스트는 이진 탐색 트리(Binary Search Tree)에 대해 공부한 내용을 정리한 것입니다.  이진 탐색 트리(BST)는 데이터를 효율적으로 저장하고 빠르게 검색할 수 있는 강력한 자료 구조입니다.이 구조는 데이터를 트리 형태로 구성하며, 탐색, 삽입, 삭제 작업을 평균적으로 O(logN) 시간에 수행할 수 있습니다.리스트와 이진 탐색 트리(BST)의 비교이진 탐색 트리를 배울 때, 이런 의문이 든적 있지 않나요?그냥 리스트로 하면되지, 왜 굳이 귀찮게 트리를 만들어서 삽입, 삭제, 탐색을 하는거지? 위 의문에 대한 해답을 얻기 위해서는 리스트와 이진 탐색 트리(BST)의 성능을 비교해보아야 합니다!리스트 성능:삽입: O(n) (단, 맨 끝에 삽입할 경우 O(1))삭제: O(n) (단, 맨 끝.. 2024. 8. 28.
[Data Structure] 트리(Tree) 본 포스트에서는 트리(Tree)에 대해 이야기해보려 합니다.  트리(Tree)는 컴퓨터 과학에서 매우 중요한 데이터 구조 중 하나로, 데이터의 저장 및 검색 효율성을 높이기 위해 다양한 응용 프로그램에서 사용됩니다. 트리가 무엇인지, 어떻게 구성되어 있는지 살펴보도록 하겠습니다!트리의 개념비선형 구조원소들 간에 1:n 관계를 가지는 자료구조원소들 간에 계층 관계를 가지는 계층형 자료구조상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조트리 용어 정리노드(node): 트리의 원소 (A, B, C, D, E, F, G, H, I, J, K)간선(edge): 노드를 연결하는 선 (부모 노드와 자식 노드를 연결)루트 노드(root node): 트리의 시작 노드 (A)형제 노드(sibling .. 2024. 8. 27.
[Data Structure] 덱(Deque) 본 포스트에서는 덱(Deque)에 대해 이야기해보려 합니다. 덱은 큐의 일종으로, 양방향에서 데이터를 처리하는 유연한 자료구조입니다!큐에 대해 잘 모르신다면, 큐에 대해 간단히 다룬 [Data Structure] 큐(Queue)에서 확인해보시기 바랍니다~ 그럼 본격적으로 덱에 대해 알아보도록 하죠~덱(Deque)이란 무엇인가덱(Deque)은 "Double-Ended Queue"의 줄임말로, 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있는 자료구조입니다.즉, 덱은 양쪽 모두 큐처럼 사용할 수 있다는 것이죠!덱의 기본 동작 append(item): 데이터를 덱의 뒤쪽(꼬리 부분)에 추가합니다.appendleft(item): 데이터를 덱의 앞쪽(머리 부분)에 추가합니다.pop(): 덱의 뒤쪽에서 데이터를 제거하.. 2024. 8. 10.
[Data Structure] 큐(Queue) 본 포스트에서는 큐(Queue)에 대해 이야기해보려 합니다. 큐는 데이터를 순서대로 처리하는 효율적인 자료구조 중 하나입니다!본격적으로 큐에 대해 알아보도록 하죠~큐(Queue)란 무엇인가큐는 FIFO(First In, First Out) 방식으로 작동하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조라는 것이죠!큐의 기본 동작1. 행동Enqueue: 큐의 뒤쪽(꼬리 부분)에 새로운 데이터 추가Dequeue: 큐의 앞쪽(머리 부분)에서 데이터 꺼내기2. 현재 상태 확인Peek: 큐의 앞쪽에 있는 데이터를 제거하지 않고 확인isEmpty: 큐가 비어 있는지 확인큐의 다양한 종류큐는 기본적인 형태 외에도 특정한 상황에 맞게 변형된 여러 종류가 있습니다.원형 큐(Circular Queue): 일.. 2024. 8. 10.

티스토리툴바