여름의 서재

💡 Tree : 트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다. 이 트리라는 자료구조는 표현에 집중한다. 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보자. 💡 Binary Tree (이진 트리) : 모든 노드들이 둘 이하의 자식을 가진 트리. 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다. 📌 Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전..

💡 Stack 선형 자료구조의 일종으로 Last In First Out (LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 Stack 의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다. 💡 Queue 선형 자료구조의 일종으로 First In First Out (FIFO). 즉, 먼저 들어간 원소가 먼저 나온다. Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다. 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 Priority queue등을 사..

💡 Array 가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다. 하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하..

- List : 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조 : mutable (수정 가능한) + iterable (순회 가능한) -> 순서 O 1) list 생성 a = list() b = [1, 2, 3] 2) list 원소 접근 - [인덱스] : list 인덱싱 a = [1, 2, 3, 4] print(a[2]) # 3 -> 리스트의 인덱스는 0 부터 시작 - [시작 인덱스: 마지막 인덱스 + 1] : list 슬라이싱 a = [1, 2, 3, 4, 5] print(a[1:4]) # [2, 3, 4] 3) list 원소 추가 - append(원소) : 리스트의 마지막에 원소 추가 a = [1, 2, 3] a.append(4) print(a) # [1, 2, 3, 4] - in..