코드ing

Deletionerase : vector의 요소 제거, 범윌도 제거가 가능더보기#include  #include  int main() {     std::vector vec = {1, 2, 3, 4, 5};          // 요소 하나 제거     vec.erase(vec.begin() + 2);  // {1, 2, 4, 5}     // 범위 제거     vec.erase(vec.begin(), vec.begin() + 2);  // {4, 5}     for(int n : vec) {         std::cout     }     return 0; }  Assertionpush_back : vector 끝에 요소를 추가 (복사해서 추가, queue의 push와 같은 작업)더보기int main(..

Spanning Tree신장 트리신장 트리가 되기 위한 조건그래프 내의 모든 정점을 포함하고 있어야 함.무방향 연결 그래프싸이클을 제거한 부분 그래프트리가 되기 위한 최소한의 간선만 남긴것  DFS Spanning Tree      BFS Spanning Tree    MST (Minimum Spanning Tree) 최소 신장 트리 - 비용이 최소인 신장 트리MST의 비용 - 신장 트리를 구성하는 간선 가중치의 합MST가 되기 위한 조건가중 무방향 그래프이외의 조건은 모두 신장 트리와 동일MST를 구하는 2가지 알고리즘 - Kruskal, Prim Kruskal Algorithm임의의 정점에서 시작, 가장 작은 가중치의 간선들을 총 n-1개 선택 (n : number of vertex)이때, 싸이클이 ..

GraphG = (V, E) V = Vertex ( Node라고 하기도 함, 정점들의 집합)    /   E = Edge (간선들의 집합, 정점들을 잇는 선들의 집합)정점: 대상      /    간선: 정점(대상)들의 관계'인접하다'의 의미Graph의 종류기본적인 그래프: 방향, 가중치 X가중 그래프: 방향 X, 가중치 O방향 그래프: 방향 O, 가중치 X가중성 방향 그래프 : 방향 O, 가중치 X(쉬우니까 그림 생략)    Adjacency Matrix, Adjacency List (인접 행렬, 인접 리스트)n * n 행렬로 표시됨 (n: number of vertex)Adjacency Matrix더보기            출처: 학교 강의 자료    Adjacency Array더보기       출처..

Shellsort (쉘 정렬)데이터를 일정한 간격(gap)에 의해 여러 개의 부분 집합으로 나누기삽입정렬이 부분적으로 정렬된 리스트에서 시간이 덜 걸린다는 것에서 착안한 정렬Insertionsort(삽입정렬)를 일정한 gap에 의해 실행Not stable, In-place 정렬 (추가 메모리X)시간복잡도: 일반적으로 O(n^1.5)   (gap sequenc에 따라 다름)최악의 경우: O(n^2) - 역순 정렬, 최선의 경우: O(n) - 정렬된 입력, 원소가 모두 같은 입력Shellsort Visualization Shellsort Code with Python더보기출처: 학교 강의자료    Mergesort (병합정렬 or 합병정렬)Divide & Conquer : 분할 후 부분배열을 정렬Merge:..

운영체제- 컴퓨터 시스템의 자원을 보다 효율적으로 사용할 수 있도록 도와주는 시스템 소프트웨어- 사용자와 컴퓨터 하드웨어 간의 인터페이스  운영체제의 목적- 시스템 성능 극대화 처리 능력 증대응답시간 단축사용 가능도 증대신뢰도 향상- 사용자 편의 극대화 (인터페이스 제공)- > 결국 유저가 시스템을 잘 쓰기 위해, 효율적으로 쓰기 위함.    운영체제의 기능- 컴퓨터 시스템의 초기화 기능- 효율적인 자원관리와 할당 기능- 편리한 사용자 인터페이스 제공 운영체제의 기능 - 시스템 초기화 기능  CMOS (RAM) : 컴퓨터 부팅 시, 필요한 모든 하드웨어의 정보를 가지고 있음 (ex: 시간, 날짜, 암호, 하드 디스크 사양 등등)BIOS (ROM) : 컴퓨터 시스템과 주변 장치 사이에서 정보 제어 및 조작..

※ 여기서 Stable, Unstable이란 동일한 key값에 대하여 정렬 후 순서가 바뀌면 Unstable, 바뀌지 않으면 Stable더보기 BubbleSort좌우 대소비교를 하면서 정렬시간복잡도: O(N^2) - 평균의 경우Stable한 정렬  Bubblesort 정렬과정더보기- List = [6, 8, 1, 3, 10, 11] - 진행과정  [6, 8, 1, 3, 10, 11]   -> [6, 1, 8, 3, 10, 11]  -> [6, 1, 3, 8, 10, 11]  -> [6, 1, 3, 8, 10, 11]  [6, 1, 3, 8, 10, 11]  -> [1, 6, 3, 8, 10, 11 ]  -> [1, 3, 6, 8, 10, 11]   -> [ 1, 3, 6, 8, 10, 11 ]...위 과..

Binary Search Tree (이진 검색 트리)노드는 모두 다 다른 키(value)값을 가져야 함각 노드는 최대 2개의 자식을 가짐모든 노드의 키(value)값은 다음 성질을 만족  더보기            -  자신의 왼쪽 subtree에 있는 모든 노드의 키보다 크다.            -  자신의 오른쪽 subtree에 있는 모든 노드의 키보다 작다.  Binary Search Tree의 시간 복잡도 Array(배열, 정렬X)Linked ListArray(배열, 정렬 O)Binary Search TreeSearchO(n)O(n)O(log n)O(log n)InsertO(n)O(n)O(n)O(log n)RemoveO(n)O(n)O(n)O(log n) ※ Insert, Remove의 경우는 임..

Binary Search Tree ⊂  Binary Tree ⊂ Tree ⊂ Graph  >Binary Tree (이진 트리)Tree의 종류 중 1개특징: 모든 노드들이 2개 이하의 자식을 가진다.   Binary Tree의 종류     1. Full Binary Tree (정 이진트리)모든 노드가 0 or 2개의 자식 노드를 가짐.  2. Complete Binary Tree (완전 이진 트리)마지막 Level을 제외하고 모든 레벨이 꽉 채워져 있음마지막 Level이 꽉 채워져 있지 않으면, 왼쪽부터 채워져 있어야 함. (일반적인 견해)    더보기 완전 이진 트리- 높이가 h일 때, 레벨 0부터 h-1까지의 모든 부모노드의 차수가 2이고, 레벨 h는 레벨 h-1의 왼쪽부터 노드가 2개씩 채워져 있는..

Tree 란?- 그래프의 부분집합 [ Graph ) Tree ]- 모든 점이 서로 연결돼 있으면서 순환되지 않는 형태의 그래프 (no cycle)-  Binary Search Tree ⊂  Binary Tree ⊂ Tree ⊂ Graph  >  Tree의 특징- 비선형적 구조 (Non-linear) : 1차원 배열로 표현이 불가함. - 재구적인 구조 (Recursive) : Root + Subtrees로 나뉜다.- 계층적인 구조 (Hierarchical) : Parent- children의 구조를 가진다.   Tree의 특성- 임의의 두 노드를 연결하는 path는 유일하다. -> 순환되지 않는 구조이기 때문에- E = V - 1  ( 간선의 수 = 노드의 수 - 1)  Tree의 Depth와 Height..