본문 바로가기

DataStructure

(7)
20210623 DataStructure 07 : Heap(힙), 힙 vs 이진 탐색 트리, 힙 동작 구조, python으로 힙 구현하기(배열활용), 힙의 시간복잡도 DataStructure 07 Heap (힙) 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 힙에 데이터를 넣고, 최대값, 최소값을 찾으면 O(log n)이 걸림 우선순위 큐와 같이 최대값, 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 힙(Heap) 구조 힙의 구조는 2 가지로, 최대 값을 구하기 위한 구조(Max Heap) 와 최소값을 구하기 위한 구조(Min Heap) 중에서 1개를 가지게 된다. Max Heap : 최대 값이 root Node를 ..
20210622 DataStructure 06 : Tree (트리), Binary Tree(이진 트리), Binary Search Tree(이중 탐색 트리), python으로 이진 탐색 트리 구현 DataStructure 06 Tree (트리) 자료구조이기도 하지만, 알고리즘 같은 로직도 많이 들어가서 알고리즘의 느낌도 있음 실제로 구현시 난이도가 높음 Tree(트리) : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한(사이클 관계X) 데이터 구조 이진 트리 (Binary Tree) 형태의 구조로, 검색 알고리즘 구현을 위해 많이 사용됨 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 도드에 대한 Branch 정보 포함) Root Node : 트리 최상위 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 해당 노드의 깊이 Parent Node : 어떤 노드의 상위 레벨을 이루는 노드 (부모 노드) Child ..
20210620 DataStructure 05 : Hash Table(해쉬 테이블), 충돌(Collision), 충돌 해결법(Chaining, Linear Probing), 충돌 개선법, SHA(안전한 해시 알고리즘) DataStructure 05 Hash Table (해쉬 테이블) 해쉬 구조 키(key)에 데이터(value)를 저장하는 데이터 구조 해쉬는 key를 가지고 hash 함수를 계산하면 data가 저장되어야 할 위치(되어 있는 위치)가 나옴 배열은 어떤 데이터를 검색하는 경우 전체 데이터를 순회해야함 하지만, hash는 순회할 필요 없이 해당 데이터의 key만 hash 함수로 계산하면 바로 데이터가 저장되어 있는 위치가 나오기 때문에 성능이 엄청 좋음 Python의 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예임 (key - value 구조) 그래서, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 보통 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용(공간과..
20210618 DataStructure 04 : 알고리즘 복잡도, 시간 복잡도, 알고리즘 성능 표기법, Big-O, 시간 복잡도 계산해보기 DataStructure 04 시간 복잡도 : 알고리즘 복잡도 표현 방법01 하나의 문제를 푸는 알고리즘은 다양할 수 있는데, 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해서 복잡도를 정의하고 계산함 (성능의 판단 기준) 예) 정수의 절대값 구하기 : 방법01 - 정수값을 제곱하여 루트사용 / 방법02 - 양수는 그대로 , 음수는 -1을 곱해서 출력 -> 둘중 어떤것이 좋은 것인지 알아야 할 필요는 있음 알고리즘 복잡도 계산 항목(요소) 알고리즘의 성능을 판단하는 알고리즘 복잡도에 대한 계산 항목이 존재한다. 시간 복잡도 : 알고리즘 실행 속도 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 둘을 비교하자면, 가장 중요한 건 실행 속도이므로 시간 복잡도를 필수적으로 이해하고 계산할 수 있..
20210617 DataStructure 03 : 연결 리스트(Linked List), 이중 연결 리스트(Double Linked List) DataStructure 03 Linked List (연결 리스트) Linked List 구조 연결 리스트라고도 함 배열은 순차적으로 연속된 공간에 공간 개수를 예약을 해서 데이터를 나열하는 데이터 구조 이러한 배열의 단점을 보완한 데이터 구조가 연결 리스트 임 연결 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 연결 리스트의 경우 공간이 연속되지 않고, 공간을 미리 예약을 하지 않고 필요할때 마다 공간을 추가 할수 있음(무한정 데이터를 저장 할 수 있음) C언어에서는 주요한 데이터 구조인데, 파이썬은 list type이 연결 리스트 기능을 모두 지원함 배열은 1개의 공간에 1개의 데이터를 관리하지만, 연결리스트의 경우 배열과 달리 특정한 데이터를 저장하는 경우, 해당 데..
20210616 DataStructure 02 : Queue(큐), Stack(스택), Python&JavaScript DataStructure 02 Queue (큐) 배열과 함께 가장 쉬운 자료구조 중 하나 운영체제, 네트워크 기능에서 많이 쓰임 멀티 태스킹을 위한 프로세스 스케쥴링 방식 구현에 많이 사용됨 (운영체제) 특별히 장단점은 없음 큐의 구조 줄을 서는 행위와 유사함 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 (선입 선출) FIFO(First-In, First-Out 첫번째로 들어간게 첫번째로 나옴) 또는 LILO(Last-In, Last-Out 마지막으로 들어간게 마지막으로 나옴) 방식으로 스택과 꺼내는 순서가 반대임 단순히 어떤것을 꺼내라는 명령이 없고, 꺼내라 라는 명령만 있음(자동으로 당겨지니까) 기능 2가지 : 데이터를 넣는것(Enqueue), 데이터를 꺼내는 것(Dequeue) Data ..
20210616 DataStructure 01 : 자료구조, 알고리즘, Jupyter notebook, Array(1차, 2차 배열), 문제 DataStructure 01 DataStructure & Algorithm (자료구조와 알고리즘) 자료구조 용어 : 자료구조, 데이터 구조, data structure 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화 해야함 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라짐 효율적 데이터를 관리하는 예 우편번호, 학생 관리(학년, 반, 번호) -> 특정 데이터를 효율적으로 찾을 수 있음 대표적인 자료구조 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등... 알고리즘 용어: 알고리즘, algorithm 어떤 문제를 풀기 위한 절차/ 방법 어떤 문제에 대해, 특정한 입력을 넣으면,..