본문 바로가기

프로그래밍/Python 자료구조6

6. 파이썬 마지막 자료구조 힙 1. 힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾을 때 시간복잡도는 O(n)이다. 이에 반해, 힙에 데이터를 넣고, 최댓값과 최소값을 찾으려면 시간복잡도는 O(logn)이다. 우선순위 큐와 같이, 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘을 구현할 때 힙을 쓴다 2. 힙의 구조 최대힙 : 최대값을 가지기 위한 구조 최소힙 : 최소값을 구하기 위한 구조 다음 두가지 조건을 가지고 있는 자료구조 최대힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 최소힙 : 각 노드의 값은 해당 노드.. 2023. 1. 21.
2. 파이썬 자료구조 링크드리스트 링크드리스트 - linked list 배열의 삽입과 추가가 어려운 것을 해결할 수 있다. 장점 미리 데이터 공간을 할당하지 않아도 된다. 단점 배열보다 데이터 공간을 많이 쓴다. 저장공간이 비효율적이다. 탐색이 어렵다. head부터 시작하기 때문에 원하는 데이터까지 접근속도가 느리다. 중간 데이터 삭제 시, 앞뒤 데이터 연결을 재구성 해야 한다. 클래스를 사용하여 구현한다. class Node : def __init__(self,data,next=None): self.data=data self.next=next def add(data): node=head while node.next: node=node.next node.next=Node(data) node1=Node(1) head=node1 for in.. 2023. 1. 20.
5. 파이썬 자료구조 트리 Tree, 이진탐색트리 Binary Search Tree 1. 트리 트리란? Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조를 말한다. 트리 중 이진트리 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용된다. 2. 알아둘 용어 Node란 트리에서 데이터를 저장하는 기본 요소이다. 데이터와 다른 연결된 노드에 대한 Branch 정보를 포함한다. Root Node란 트리 맨 위에 있는 노드이다. Leve이란 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 길이를 나타낸다. Parent Node란 어떤 노드의 상위 레벨에 연결된 노드이다. Child Node란 어떤 노드의 다음 레벨에 연결된 노드이다. Leaf Node(Terminal Node)란 Child Node가 하나도 없는 노드이다. Sibli.. 2023. 1. 18.
4. 파이썬 자료구조 해쉬테이블 Hash table 1. 해쉬테이블 구조 Hash Table은 key 에 Value를 저장하는 데이터 구조이다 파이썬의 딕셔너리라고 보면 된다 배열로 미리 Hash Table의 사이즈를 생성한 후 구현한다 공간과 탐색시간을 맞 바꾸는 기법이란, 공간을 늘리면 데이터를 탐색할 때 충돌이 적어져서 탐색 시간이 줄어드는 것을 의미한다. 즉, 각각 다른 key 값이 같은 hash 값을 가지고 있을 때 충돌이 일어나기 때문에 충돌 해결 알고리즘으로 해결해야한다. 파이썬에서는 해쉬를 별도 구현할 이유가 없다. 딕셔너리 타입을 사용하면 된다. 2. 알아둘 용어 Hash란 임의 값을 고정 길이로 변환하는 것을 의미한다. hash function을 이용해 고정길이 값인 hash값을 구한다. Hash Table이란 key 값의 연산에 의해 .. 2023. 1. 15.
3. 파이썬 자료구조 알고리즘 시간복잡도 1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있다. 예를 들어보자. 정수의 절댓값 구하는 문제 1. 정수값을 제곱한 값에 다시 루트를 씌운다 2. 정수가 음수인지 확인해서 음수일 때만 -1을 곱한다 즉, 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산한다. 2. 알고리즘 복잡도 계산 항목 1. 시간 복잡도 : 알고리즘 실행 속도 (반복문이 지배!) 2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 (지금은 별로 안 중요) 알고리즘 성능 표기법 빅오 O(N) 표기법 알고리즘 최악의 실행 시간을 표기한다. 아무리 최악의 상황이라도 이 정도의 성능은 보장한다는 의미이다. 3. 이것이 코딩 테스트다 with 파이썬 참고 시간복잡도.. 2023. 1. 12.
1. 파이썬 자료구조 배열, 큐, 스택 1. 배열 - array 데이터를 인덱스에 대응하도록 구성한 데이터 구조다 string : 각각의 글자가 연결되어 인덱스 처리된다 파이썬 배열은 리스트다 장점 탐색이 용이하다, 즉 데이터에 빠른 접근이 가능하다. 단점 데이터를 추가하려면 기존 공간에 추가해야 하기 때문에 추가가 어렵다. 새로운 공간을 만들어야 할 수도 있어서 추가, 삭제가 어렵다 미리 최대 길이를 정해야 한다(c언어) 2. 큐 - Queue 줄 서는 것과 동일하다. First in, First out. 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. 운영체제, 네트워크에서 많이 사용된다. 명령은 "넣어라, 꺼내라" 파이썬 queue library : Fifo, Lifo, Priority Queue (0,””) 큐의 활용 : 멀티태스킹을 위한.. 2023. 1. 11.