프로세스(Process) 실행중인 프로그램! 프로그램 자체는 디스크 내 파일로 존재하고 동작을 하지 않는 정적이며 수동적인 개체이다. 프로그램을 실행시키려면 운영체제로 부터 프로그램이 동작하는데 필요한 CPU, 메모리, 입출력장치, 파일 드으이 자원을 할당 받아 동작을 시작해야 한다. 프로세스의 상태 변화 1) 생성상태 -&g...

프로그램 일반적으로 특정 작업을 수행하는 소프트웨어 프로세스 메모리나 CPU와 같은 자원을 할당받아 실행 중인 프로그램 독자적인 메모리를 할당받아서 서로 다른 프로세스끼리는 일반적으로 서로의 메모리 영역을 침범하지 못함 스레드: 프로세스를 구성하는 하나의 단위, 작업의 실행 단위 하나의 프로세스는 여러 스레드가 작동하고 ...

red-black 트리와 AVL트리가 생겨난 배경 이진 탐색 트리는 평균적으로 O(logN)의 삽입, 삭제, 검색 연산속도를 가진다. 이진 검색 트리의 구성 조건은 left < root < right이다. 만약 순차정렬된 데이터가 들어온다면 이진 검색트리는 위의 그림과 같이 편향트리가 될 것이다. 트리의 속도는 트리의 깊...

트리란? 계층적인 자료를 표현하기 위한 자료구조 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현 트리는 그래프의 한 종류이며 사이클이 없다. 실제 나무를 거꾸로 한 것과 같은 모양을 하고 있기 때문에 트리라고 부른다. node: 트리를 구성하고 있는 각 요소 Edge(간선): 트리를 구성하기 ...

이진트리(Binary Tree) 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다. 이진트리의 레벨i에서 가질 수 있는 최대 노드의 2^i이다.(i>=0) 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1) 이진트...

Binary Search Tree(이진 탐색 트리) 모든 노드가 자신의 왼쪽 서브트리에는 현재노드보다 작은 키값이, 오른쪽 서브트리에는 현재 노드보다 큰 값이 오는 규칙을 만족하는 이진트리 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 (모든 노드 n에 대해서 반드시 참) 이진 탐색 트리는 이진 탐색을 쉽게 할 수 있도록...

Balanced Binary Search Tree(균형 이진탐색 트리) 이진 탐색트리에 새로운 노드가 삽입이 되면 부모의 노드보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 추가하면서 서브트리가 계속 구성되어진다. 이진탐색트리의 치명적인 단점은 자료가 많아질수록 트리의 높이(height)가 커지기 때문에 검색에 불리해지고 최악의 경우 (...

스택이란? 마지막에 들어온 데이터를 먼저 내보내는 후입선출(LIFO: Last-In-First-Out)을 표현하기 위한 자료구조 예를 들어 접시 쌓기를 예로 들 수 있습니다. 접시를 쌓을 때 위에서부터 차곡차곡 쌓지만 빼낼때는 가장 맨위의(마지막에 들어온) 접시부터 빼내게 됩니다. 스택의 장점 스택에서 데이터를 추가하거나 삭제하는...

우선순위 큐(Priority Queue)란? 우선순위에 따라 우선순위가 높은 객체가 먼저 나오는 자료구조 우선순위 큐는 3가지 방법으로 구현할 수 있다. 1)배열 사용 데이터 삽입, 삭제과정에서 데이터를 밀고 당기는 연산을 해야 하는 단점이 존재 2)...

Queue(큐)란? 먼저 들어온 데이터를 먼저 내보내는 선입선출(FIFO: First-In-First-Out) 구조의 자료구조 예를 들어, 영화관 매표소에서 예매를 하기 위해 손님들은 순서대로 줄을 스게 되며 먼저 온 손님부터 영화를 예매하게 됩니다. Java에서는 Queue를 사용하기 위해 java.util.Queue를 구현한 클래스...