본문 바로가기

CS/Data Structure7

Linked List와 STL List 해당 게시글은 '바킹독의 실전 알고리즘 강의'를 학습한 후 개인적으로 정리한 내용임을 밝힙니다.[출처] https://blog.encrypted.gg BaaaaaaaarkingDog blog.encrypted.gg 1. Linked List정의노드들이 포인터로 연결된 구조각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함 유형① 단일 연결 리스트 (Singly Linked List) ② 이중 연결 리스트 (Doubly Linked List) ③ 원형 연결 리스트 (Circular Linked List) 시간 복잡도임의의 위치에 접근/변경 : O(n)임의의 위치에 삽입/삭제 : O(1) (추가하고 싶은 위치의 주소를 알고 있는 경우) 장점동적으로 크기 조절 가능 → 메모리 낭비 적음 (필요 시 할당.. 2025. 6. 17.
Array와 STL Vector 해당 게시글은 '바킹독의 실전 알고리즘 강의'를 학습한 후 개인적으로 정리한 내용임을 밝힙니다.[출처] https://blog.encrypted.gg BaaaaaaaarkingDog blog.encrypted.gg 1. Array정의연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 자료구조 시간 복잡도임의의 위치에 접근/변경 : O(1)맨 끝에 원소를 추가 : O(1)맨 마지막 원소를 제거 : O(1)임의의 위치에 삽입/삭제 : O(n) 특징고정 크기논리적 저장 순서 = 물리적 저장 순서 장점빠른 인덱스 접근 (Random Access)메모리 접근이 효율적추가적으로 소모되는 메모리의 양 (=overhead)가 거의 없음Cache hit rate가 높음 단점크기 변경 불가임의의 위치에 삽입/삭제 시 .. 2025. 6. 17.
Tree : 개념 정리 1. Tree : 그래프 중 cycle이 없는 형태 2. Terminology Node Tree 구성요소 Ancestor 한 node의 parent, grandparent 모두 Offspring node 한 node의 child, grandchild 모두 Root Node without Parents Subtree 하나의 node와 그 descendants로 구성된 tree Terminal node Node without children Non-terminal node Node with at least one child level tree의 layer 수 (3) height maximum level of the tree degree 그 node가 가진 child nodes의 수 3. Tree Type B.. 2022. 6. 7.
Graph : 개념 정리 1. Graph : A data Structure that represents the relationships between connected objects. 2. Terminology Vertex = Node Edge = link 3. Graph Type Undirected Graph Directed Graph ONLY undirected edge ONLY directed edge Both way One way (A, B) (A, B) == (B, A) != ▶ Weighted Graph : A graph with the weight assigned to edges ▶ Sub Graph : A graph consisting of a subset of the vertex set V(G) & the edg.. 2022. 4. 19.
Array : 개념 정리 1. Array (1) data type이 동일한 자료를 연속으로 저장함 (2) A set of pairs of 2. 1차원 배열 ▷ 1차원 배열의 선언 자료형 배열명[element 개수 = 배열 크기] ; int MyArr[100]; ▷ 1차원 배열의 초기화 자료형 배열명[배열 크기] = { 초기값 리스트 } ; int MyArr[3] = {1,2,3}; or int MyArr[ ] = {1,2,3,4}; #include void main() { int score[3] = { 91, 86, 97 }; char grade[3] = { 'A', 'B', 'A' }; printf("\n *** 학년별 취득 학점 ***\n\n"); for (int i = 0; i < 3; i++) { printf("%d학년 .. 2022. 4. 10.
Time Complexity Analysis Time Complexity Analysis : 시간 복잡도 ▶ 시간 복잡도 표기법 ① Big O Notation ② Big Ω Notation ③ Big θ Notation 함수의 상한 나타냄 함수의 하한 나타냄 함수의 상한과 하한 나타냄 모든 n >= n0 에 대하여, |f(n)| = n0 에 대하여, |f(n)| >= c |g(n)| 을 만족하는 상수 c와 n0이 존재하면, f(n) = Ω(g(n)) 이다. 모든 n >= n0 에 대하여, c1 |g(n)| 2022. 4. 10.
Data Structure 1. Importance of Data Structure 우리는 일상에서 방대한 양의 데이터와 함께 살아간다. 그러나, 아무렇게나 뒹굴고 있는 데이터는 우리의 생활에 빛나는 도움을 주지 못한다. 따라서 데이터들을 찾기 쉬운 형태로 정리하기 위한 바구니가 필요한데, 이것이 바로 자료구조이다. 자료구조는 배열, 리스트, 스택, 큐 등 그 종류가 다양하다. 우리는 상황에 따라 가장 적합한 자료구조를 선택하여 데이터를 저장하고, 쉽게 꺼내쓰면 된다. ※ Program = data structure + algorithm 2. ADT (Abstract Data Type) ▶ Data type : data (-2, 0, 1, 3 ...) & opeartion ( *, +, /, % ...) 집합들의 모임 우리는 '무.. 2022. 3. 31.

티스토리툴바