본문 바로가기

자료구조

[자료구조]해시테이블, hash function Hash Table Key와 Value를 1:1로 연관지어 저장하는 자료구조 (연관배열 구조) 왜 필요한가?(장점) 예를 들어 key : 이름, value : 전화번호의 자료를 저장할 때 특정 이름으로 전화번호를 찾으려면 배열에서는 선형탐색(O(n))을 해야 함 해시테이블을 이용하면 특정 이름(키)로 자료를 찾을 때 O(1)로 찾을 수 있음 배열의 인덱스를 사용하기 때문에 빠른 검색, 삽입, 삭제 (O(1)) 작동 방식 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용 Key -> Hash Function -> Hash Function 결과 = Hash 예를 들어 크기 5인 해시테이블에 자료를 저장할 때 키 -> 해시함수 -> 해시값 % 5 를 이용해 인덱..
[자료구조]배열과 연결리스트 Array vs Linked List 배열은 고정된 양의 데이터를 임시로 저장해두고 수시로 데이터에 접근하는 경우에 유용하게 사용될 수 있으며, 연결리스트는 데이터의 추가와 삭제가 빈번하게 일어나거나, 복잡한 형태의 자료구조를 만들 때 유리하다. 배열 논리적 저장 순서와 물리적 저장 순서가 일치해 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 인덱스 값을 알고 있으면 Big-O(1)로 접근할 수 있다. 하지만 원소를 삭제, 삽입시, 배열의 연속적인 특징은 깨진다. 따라서 삭제 및 삽입시 해당 인덱스보다 큰 인덱스를 갖는 원소들을 이동해야하고 이 경우의 시간 복잡도는 O(n)가 된다. 데이터의 삽입 또는 삭제 등의 연산이 빈번하게 발생하여 데이터의 수가 다이나믹하게 변하게 되는 자료구..
[자료구조] 트리, 이진트리, 이진탐색트리, 완전이진트리 트리와 그래프 그래프 : 노드와 간선으로 표현, 사이클 가능, 루트노드 개념 없음, 부모-자식 개념 없음, 네트워크 모델 트리 : 노드로 이루어진 자료구조, 사이클 불가능 루트노드 반드시 한 개, 모든 자식노드는 한 개의 부모노드를 가짐, 계층 모델 트리 비선형 자료구조, 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조 노드로 이루어진 자료구조(노드는 어떤 자료형으로도 표현 가능) Terminal Node ( = leaf Node, 말단 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다. Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다. 하나의 루트노..
[자료구조]Array, Linked list 차이 배열과 연결리스트 활용 배열은 고정된 크기의 데이터를 저장하고 자주 데이터에 접근하는 경우에 유용하게 사용 연결리스트는 데이터의 추가와 삭제가 빈번하게 일어나거나, 복잡한 형태의 자료구조를 만들 때 사용 Array(배열) 장점 논리적 저장 순서와 물리적 저장 순서가 일치한다 인덱스(index)를 이용해 원소에 접근할 수 있다(인덱스 값을 알고 있으면 O(1)의 시간복잡도로 접근) 단점 삭제, 삽입시 배열의 연속적인 특징이 깨짐(빈 공간이 생긴다) 따라서 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 데이터의 삽입 또는 삭제 등의 연산이 빈번하게 발생하여 데이터의 수가 다이나믹하게 변하게 되는 자료구조에서는 배열을 활용하는 것이 비효율적 Linked L..
[자료구조] 힙(heap), 우선순위큐, 파이썬 최대힙, 최소힙 힙이란? 완전 이진트리의 일종으로 우선순위큐(PriorityQueue)를 위하여 만들어진 자료구조 큐에 우선순위가 적용되어 있으므로 최대값이나 최소값을 빠르게 찾아내기 위한 자료구조 (큐는 가장 먼저 들어온 데이터가 먼저 나가지만 우선순위큐는 해당 우선순위 데이터가 가장 먼저 나간다) 단 모든 값들이 정렬되어 있지 않은 일종의 반정렬(느슨한 정렬) 상태이며 최소값 혹은 최대값 만을 보장 (최소 최대가 모두 필요할 때는 이중 힙 구조를 써야함) 삽입 및 삭제가 BST보다 빠르며 모든 삭제나 삽입이 배열의 가장 끝에서 발생 힙의 추가 추가되는 숫자는 가장 마지막 레벨 빈 자리(왼쪽부터 채워짐)로 저장 됨 부모의 숫자가 클 때는 조건을 만족하지 않으므로 부모와 자식을 교환 교환이 발생하지 않을 때까지 반복하여..
Set, List 자료형 remove 시간복잡도 O(1), O(n) 릿코드 127. Word Ladder 번 풀다가 list를 굳이 set으로 변환시키길래 중복 제거하려고 했나보다 싶었지만 set 변환 전후로 len()로 비교해보니 중복 자료형이 없었다. 이유는 remove 메소드의 시간복잡도 차이 때문 왜 set 자료형과 list 자료형의 remove 메소드 시간 복잡도 차이가 생길까? 1. Set 자료형의 remove 메소드 시간복잡도는 O(1) - 알려진 바와 같이 set 자료형은 중복이 불가능하고, 순서가 없다. - 또한 값 수정은 불가능하지만 추가(add) 와 삭제(remove)는 가능하다 -> 딕셔너리 자료형의 키 값으로 사용 가능( 딕셔너리 키 값은 수정 불가능) - 위 특징의 이유는 set 자료형의 경우 hash function에 의해 hash 값을 구하고..

티스토리툴바