newhaneul

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다. https://youtu.be/83XIXfdhx20?si=9LQ-8yzpuNljrGES 1. Graphs Graph는 정점 (Vertex)과 간선 (Edge)으로 이루어진 자료구조이다. 이때 Tree는 사이클이 없고 연결되어져 있는 특수한 그래프이다.Adjacency: 정점 u와 v 사이에 간선이 있으면 인접하다고 말한다.Degree: 한 정점에 연결된 간선 개수Path: 정점들을 연속해서 잇는 간선들의 나열Simple path: 정점을 중복해서 지나지 않는 경로Cycle: 시작 정점과 끝 정점이 같은 경로Conne..

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다. https://youtu.be/SSLNiP438OA?si=EN1kEtPXvAqPP2pp 1. Binary Tree 각 노드가 최대 2개의 자식만 갖는 트리를 의미한다. Root: 가장 위의 노드Parent / Child: 부모 / 자식 노드Sibling: 형제 노드(같은 부모)External node (Leaf) : 자식이 없는 노드Internal node: 자식이 1개 이상 있는 노드Subtree: 어떤 노드를 루트로 하는 작은 트리 Traversal 1) Preorder (Root → Left → Right..

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다. https://youtu.be/8dD4ANue7NY?si=1eOVMOqqAywiAfKf 1. Stacks 동작 구조 선형 자료구조, 한쪽 끝(top) 에서만 넣고 빼는 구조이다.LIFO (Last-In, First-Out) : 나중에 들어간 데이터가 먼저 나온다.기본 연산 push(x) : 맨 위(top)에 원소 x를 넣는다.pop() : 맨 위 원소를 꺼내서 제거한다. top() : 맨 위 원소를 “보기만” 한다. (peek)size() : 스택에 들어 있는 원소 개수empty() : 비었는지 여부 Array ..

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다. https://youtu.be/647aZztdsb0?si=YLRU39A9zVc_lvRp 1. Array 메모리 구조데이터가 연속된 메모리에 저장됨A[0], A[1], ... A[n-1]장점Random access: O(1) 내에서 임의의 위치에 접근할 수 있다.단점중간에 삽입 및 삭제하면 뒤 원소들을 전부 한 칸씩 밀거나 당겨야 해서 O(N)이 된다.불필요한 메모리 공간이 사용된다. 2. Singly Linked List 메모리 구조각 노드가 메모리 공간 내에 흩어져 있고 포인터 변수 "next"로 이어진다.보통 ..

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다. https://youtu.be/0QK_-ygktyM?si=cWZeennCW0u3XZE8 1. Insertion Sort동작 방식i = 1부터 시작해서 arr[0..i-1] 구간은 항상 정렬된 상태라고 가정key = arr[i]를 들고,왼쪽으로 가면서 key보다 큰 값들을 한 칸씩 뒤로 밀고적절한 위치(j+1)에 key를 꽂는 방식제자리 정렬(in-place)임 → 추가 메모리 O(1)안정 정렬(stable)임 → 같은 값들의 상대 순서 유지됨Time Complexity최악의 경우: O(N^2) (역순으로 정렬된 상..