Python/[Data Structure] 자료구조 (11) 썸네일형 리스트형 [11] Graph, 그래프 어쨌든 계획한 목록에서는 마지막 챕터이다. 그래프!!!!!!!!!!!!!! 오늘의 짤은 따로 없을 예정 하하 그래프도 참 나를 괴롭게했지...하...(기싫다).... 그림 출처 :https://python.plainenglish.io/graph-data-structure-theory-and-python-implementation-ee8c9795eae7 ✅ 그래프란 그래프(Graph)란 정점과 간선으로 이루어진 자료구조이다. 이전에 배웠던 트리(노드와 간선)도 그래프의 일종인데 사실 트리가 별종이다. 다만, 트리와 그래프의 차이점이라면 다음과 같다. 1. 트리에는 루트 노드가 명백히 존재하지만, 그래프는 그런 거 없다. 2. 트리는 루트에서 리프 노드로 뻗어가는 단방향 경로만 존재하지만, 그래프는 단방향 .. [10] Hash Table, 해시 테이블 ✅ 해시 테이블이란 해시 테이블(Hash Table)은 키(Key)에 데이터(Value)를 저장하는 자료형이다. 파이썬에서 공부했던 딕셔너리와 비슷한 개념 정도가 아니라, 해시를 구현할 때 딕셔너리 타입을 사용하면 된다. 해시 테이블은 키를 통해 데이터를 바로 찾을 수 있는 장점이 있는데 시간 복잡도가 O(1)으로 매우 빠르다. ✅ 해시 주소란 해시 주소(Hash Address)는 해시 값이다. Key를 해싱 함수로 연산해서 나오는 값이 해시 값이다. ✅ 해시 함수란 해시 함수(Hash Function)는 임의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수이다. 가장 간단한 형태는 데이터를 지정된 숫나로 나눈 뒤에 나머지를 인덱스로 사용하는 방법인데 코드로 나타내면 다음과 같다. def HashFu.. [9] Priority Queue, 우선순위 큐 & Heap, 힙 빠지지 않는 오늘의 짤.. 더보기 사실 큐 포스트 다음이 우선순위 큐였는데 조금 공부하다 보니 트리를 알아야 할 것 같아서 트리를 하고 온 것이다. 2022.04.13 - [Python/[Data Structure] 자료구조] - [6] Queue, 큐 [6] Queue, 큐 👇🏻 오늘의 짤 : 최근에 피트 데이비슨이랑 아주 🔥 하게 장안의 화제가 되고 있는 킴언니의 짤을 준비했다. 더보기 몇일 전에 롯데월드에 갔는데 내가 가장 좋아하는 게 아틀란티스다. 근데 sennieworld.tistory.com ✅ 우선순위 큐란 큐에 대해 잠깐 요약해보면 큐는 FIFO, 먼저 들어간게 먼저 나오는, 아틀란티스 줄 구조이다. 하지만, 우선순위 큐는 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나오는 자료.. [8] Binary Search Tree, 이진 탐색 트리 👇🏻 오늘도 지나칠 수 없는 오늘의 짤 더보기 저번 포스트에서 공부했던 이진 트리의 응용버전(?)을 공부하도록 하겠다. ✅ 이진 탐색 트리란 이진 탐색 트리(Binary Search Tree)는 주로 BST라고 부르고 쉽게 말해 [이진 트리 + 조건 한 개 추가]를 만족하는 자료형이다. 바로 그 조건은 듣기에는 간단하다. -> (모든 노드에 대해) 왼쪽 노드.data < 오른쪽 노드.data 이진 탐색 트리(Binary Search Tree, BST) : 모든 노드에 대해 왼쪽 노드의 데이터가 오른쪽 노드의 데이터보다 작음을 만족하는 이진 트리 이진 탐색 트리의 조건은 그다지 까다롭게 느껴지지는 않지만 막상 구현해 보면 생각보다 어렵다고 느끼게 될 것이다. 왜냐하면 트리에 데이터를 삽입하고 삭제할 때, .. [7] Tree, 트리 👇🏻 오늘도 여김없이 오늘의 짤 더보기 무는 뿌리를 바탕으로 가지를 통해 잎이 난다. 나무에 영양분이 공급되는 경로(루트)가 트리(Tree)의 자료구조 형태와 비슷하다. 오른쪽 그림이 트리 자료구조를 시각화한 것이다. 알파벳 트리(오른쪽 그림)에서 화살표가 양분이 뻗어나가는 통로(즉, 가지)라고 하면 나무의 뿌리는 A가 될 것이다. 트리에서는 이것을 루트 노드(root node, 노드는 연결리스트에서 등장한 개념과 동일)라고 한다. 영양분이 뻗어나가는 통로를 간선(edge)라고 하고 영양분이 최종적으로 전달되는 D,E,C를 리프 노드(leaf node)라고 한다. 컴퓨터가 정하기 좋아하는 것 중 하나가 관계를 정의하는 것이다. 트리에서는 edge(화살표)를 기준으로 시작하는 노드가 부모, 가리키는 노드가.. [6] Queue, 큐 👇🏻 오늘의 짤 : 최근에 피트 데이비슨이랑 아주 🔥 하게 장안의 화제가 되고 있는 킴언니의 짤을 준비했다. 더보기 몇일 전에 롯데월드에 갔는데 내가 가장 좋아하는 게 아틀란티스다. 근데 그거 RG 다들. 아틀란티스 줄 엄청 긴거. 기본으로 1시간은 기다려야 함. 어쨌든, 난 그걸 타다가 사촌동생이 주먹으로 눈알을 쳐서 각막이 벗겨진 경험이 있다. 심지어 생일 전 날..ㅎ 아틀란티스에 줄을 서 있다고 생각해보자. 앞과 뒤로 많은 사람들이 줄 서 있고 앞 사람이 차례로 놀이기구를 타야 내 차례가 돌아온다. 아틀란티스에 줄 선 모든 사람들은 큐(Queue)의 원소를 자처하고 있는 것이다. 큐(Queue) : 데이터들이 순서대로 줄 서 있는 자료형 FIFO (First In First Out, 선입선출)으로 .. [5] Stack, 스택 👇🏻 최근에 나에게 감동을 선사한 짤 더보기 해리포터 시리즈 책을 바닥에 1권부터 7권까지 쌓는다고 생각해보자. 가장 먼저 꺼낼 수 있는 책은 무엇인가? 가장 나중에 쌓은 7권을 가장 먼저 빼낼 수 있다. 이것이 스택의 자료형이다. 스택(Stack, 쌓다) : 가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 스택을 LIFO 방식이라고 얘기하는데 Last In First Out (가장 나중에 들어가고 가장 먼저 나온다, 후입선출)라는 뜻이다. 파이썬에서 우리가 사용하는 list로 이미 스택은 구현되어 있으며 내장함수를 이용해 사용하면 된다. list.append(data) : list에 data를 맨 마지막에 추가함. list.pop() : list의 맨 마지막 요소를 반환하고 해당 요소는.. [4] Linked_List, 연결리스트 (3) 👇🏻 오늘의 짤 더보기 지금까지 연결리스트의 기본 형태에 대해 알아보았다. 직전 포스트에서 이 말이 기억이 나는가? "연결리스트는 이전을 가리킬 수 없고 다음만 가리킬 수 있다" 사실 이건 거짓말이다. 우리가 지금까지 배웠던 건 Single Linked List(단일 연결리스트)이다. 베스킨라벤스에도 Single과 Double이 있듯이, Double Linked List(이중 연결리스트)가 존재한다. 그냥 넘어가면 서운할 것 같으니 한번 짚고 넘어가려고 한다. 단일 연결리스트에서는 노드를 찾을 때 node = head로부터 시작을 해 모든 노드를 탐색한 후 찾아야만 했다. 이에 반해 이중 연결리스트는 양방향으로 연결이 되어 있어 head, tail 두 노드에서부터 탐색이 가능하다. 양방향이 무슨 뜻인지는.. [3] Linked List, 연결리스트(2) 👇🏻 시작하기 전 오늘의 짤 더보기 더 늦기 전에 연결리스트에 대해 더 알아보자. 2022.04.08 - [Python/[Data Structure] 자료구조] - [2] Linked List, 연결리스트 (1) [2] Linked List, 연결리스트 (1) 자료구조 수업을 들을 때, 진짜 연결리스트가 너무 싫어서 오열한 적도 있다. 이해와 구현의 갭 차이가 너무 컸기 때문... 실습 때 집에 일찍 가고 싶어서 구글링으로 대충 복붙했다가 내 알고리 sennieworld.tistory.com 👆 저번 시간에 연결리스트로 만들어 준 18과 친구들은 잘 놀고 있었다. 그리고 그들은 오늘 올 새 친구에 설레 있었다. 새 친구 58이 도착했다. 그들은 어느때와 같이 환영인사로 기차놀이를 하려고 하는데 58은 꼭.. [2] Linked List, 연결리스트 (1) 자료구조 수업을 들을 때, 진짜 연결리스트가 너무 싫어서 오열한 적도 있다. 이해와 구현의 갭 차이가 너무 컸기 때문... 실습 때 집에 일찍 가고 싶어서 구글링으로 대충 복붙했다가 내 알고리즘, 자료구조 인생은 망했다지... 혹시나 코드 긁을 사람이라면 당장 멈춰 진심 인생 조진다. 배열의 치명적인 단점 중 하나는 '배열 크기 변경 불가'이다. 연결리스트는 이를 해결하고자 나온 개념인데 어떻게 해결했는지 스스로 제대로 아는 것이 나의 목표이다. 연결리스트( Linked List )를 직역해보면 '연결된 리스트'이다. 뭐가? 뭐가 연결되어 있을까. 바로 첫번째 알아야 할 개념인 노드(Node)가 그 '뭐'이다. 정말 머같다. 노드(Node)는 데이터(data)와 포인터(pointer)로 이루어져 있다. .. [1] 자료구조와 배열 자료구조 : 데이터가 모여 있는 구조로 컴퓨터에서 처리해야 하는 많은 데이터를 모아 효율적으로 관리하고 구조화하기 위해 사용된다. ✓ 시간 복잡도 O(n) : n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어남. [시간 적게] O(1) < O(𝑙𝑜𝑔𝑛logn) < O(n) < O(n𝑙𝑜𝑔𝑛logn) < O(𝑛2n2) < O(2𝑛2n) < O(n!) [시간 많이] 배열(Array) : 묶음 단위로 값을 순차적으로 저장하는 선형 자료 구조로 배열에는 객체가 저장되며 객체 하나하나를 원소(element)라고 한다. ✓ 배열의 특징 추가적으로 소모되는 메모리 양이 거의 없다. Cache hit rate(요청한 데이터를 캐시메모리에서 찾을 확률)가 높다. 배열을 생성하려면 메모리 상에 연속한 구간을 할당해야 해.. 이전 1 다음
