자료구조 알고리즘/자료구조6 자료구조 - 해쉬 테이블(Hash Table) 언어는 python을 사용하였습니다. 6. 해쉬 테이블(Hash Table) 키(Key)에 데이터(Value)를 저장하는 데이터 구조 해쉬구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 매우 빠름 파이썬의 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예시 이다. 보통 배열로 미리 Haash Table의 사이즈만큼 생성 한 뒤에 사용한다. 해쉬 테이블의 크기를 크게 만듦으로써 충돌로 인한 추가적인 알고리즘을 실행시키지 않도록 한다 즉 공간과 탐색 시간을 맞바꾸는 기법 이다. 배열보다 빠르게 데이터를 찾을수 있다. 알아둘 용어 해쉬(Hash): 임의 값을 고정된 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Has.. 2022. 10. 4. 알고리즘의 복잡도 표현 언어는 python을 사용하였습니다. 5. 알고리즘의 복잡도 표현 알고리즘을 해결하는 방법에는 여러가지 방법이 있고, 여러가지 방법중 더 좋은 알고리즘을 분석하기 위해 계산한다. ex) 1부터 10까지의 합을 구하는 방법. (1)1부터 10까지 모두 더한다. (2)공식을 사용한다. 알고리즘 복잡도 계산 항목 시간 복잡도 : 알고리즘 실행 속도 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 가장 중요한 것은 시간 복잡도 로서, 시간 복잡도는 반복문이 가장 큰 영향을 미친다. 알고리즘 성능 표기법 Big O(빅-오) 표기법: O(N) -> 알고리즘의 최악의 실행 시간을 나타낸다. -> 가장 많이 사용한다. -> 아무리 최악의 상황이더라도, 최소한 이정도의 성능은 보장한다 라는 의미 Ω (오메가) 표기법:.. 2022. 10. 3. 자료구조 - 링크드 리스트(Linked List) 언어는 python을 사용하였습니다. 4. 링크드 리스트(Linked List) 링크드 리스트는 연결 리스트라고도 하며, 배열을 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 이다. C언어에서 주요한 데이터 구조 이지만, 파이썬에서는 리스트 타입이 링크드 리스트의 기능을 지원 한다. 링크드 리스트의 형태 노드(Node): 데이터 저장 단위로서, 데이터값과 포인터로 구성된다. 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보 즉 주소를 가지고 있는 공간 이다. #링크드 리스트 만들기 class Node: def __init__(self, data, next=None): self.data = data self.next = next # 데이터 추가하기 def add(dat.. 2022. 10. 3. 자료구조 - 스택(stack) 언어는 python을 사용하였습니다. 3. 스택(Stack) 스택은 데이터를 임시 저장할 때 사용하는 자료구조로서, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 입니다. 기본적으로 가장 나중에 넣은 데이터를 가장 먼저 뺄수있는 LIFO(Last- in, First-Out) 구조 입니다. 삽입 삭제 데이터를 스택에 넣기 push() 데이터를 스택에서 빼기 pop() 장, 단점 (장점) 구조가 단순해서 구현하고 쉽고, 덕분에 데이터의 저장 읽기 속도가 빠르다 (단점) 데이터의 갯수를 미리 정해 그에따른 저장공간을 확보해야 한다, 따라서 공간의 낭비가 발생할수도 있다. 파이썬의 경우 재귀 함수는 최대 1000번까지만 호출이 가능하다. 파이썬 리스트를 통한 스택 구현 #리스트 생성 data_stack = li.. 2022. 9. 11. 자료구조 - 큐(Queue) 언어는 python을 사용하였습니다. 2. 큐(Queue) 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조 입니다. FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대 큐의 경우 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기위해 OS에서 많이 사용된다. 삽입, 삭제 큐에 데이터를 추가하는 작업 인큐(Enqueue) 큐에 데이터를 꺼내는 작업 디큐(dequeue) 데이터를 꺼내는 쪽 프런트(front) 데이터를 넣는 쪽 리어(rear) 파이썬에서의 큐(Queue) 파이썬에서는 queue 라이브러리를 통해 다양한 큐 구조를 제공한다 일반적인 Queue, LIFO 구조의 LifoQueue(), 우선순위를 .. 2022. 9. 9. 자료구조 - 배열 (Array) 언어는 python을 사용하였습니다. 1. 배열(Array) 데이터를 나열하고, 각 데이터 인덱스에 대응하도록 구성하는 데이터 구조 파이썬에서는 리스트(list)와 튜플(tuple)로 구현한다. 같은 종류의 데이터를 효율적으로 관리하고, 순차적으로 저장하기 위해 사용 또한 다른 언어의 경우 배열의 데이터 타입을 정해주어야 하지만, 파이썬의 경우 하나의 배열에 여러가지 데이터 타입이 올 수 있다. 특징 (장점) 인덱스 번호로 데이터에 접근할수 있기 때문에 빠르다. (단점) 미리 길이를 설정해야 하므로 데이터의 추가/삭제가 어렵다. but 파이썬에서는 길이를 미리 정할 필요가 없이 가변적 이다. 예시 # 1차원 배열: 리스트로 구현시 data_list = [1, 2, 3, 4, 5] # 2차원 배열: 리스트.. 2022. 9. 9. 이전 1 다음