비선형 문제선형 자료 구조로 표현할 수 없는 대표적인 문제계층적 문제(hierachical problem)순환 종속성 문제(cyclic dependency)계층적 문제ex)회사 조직과 같은 조직 구성은 계층적으로 표현되지만, 선형 자료구조로 표현하기 어렵다선 이수 체계를 갖는 대학교 과정에 대한 종속 관계를 표현할 때에도 마찬가지다.트리를 이용하여 해결순환 종속성ex)SNS에서 사람들과의 친구관계 (그래프)도시와 도시를 잇는 도로망그래프를 이용하여 해결

Process Concept(프로세스 개념)운영 체제는 다양한 프로그램을 실행합니다.배치 시스템 - jobsTime-shared systems(시분할 시스템) - user programs 또는 tasks교재에서는 job과 process라는 용어를 번갈아가면서 사용할 거라고 하네요프로세스실행 중인 프로그램(a program in execution)프로세스는 다음을 포함합니다.프로그램 코드(code), 텍스트 섹션(text section)이라고도 함전역 변수 및 정적 변수를 포함하는 데이터 섹션(data section)임시 데이터를 포함하는 스택(stack)함수 매개변수, 반환 주소, 로컬 변수실행 중 동적으로 할당된 메모리를 포함하는 힙(heap)프로그램 카운터(program counter), 프로세서 레..

운영체제 서비스 (Operating System Services)운영체제는 사용자에게 다음과 같은 서비스를 제공사용자 인터페이스(User Interface)명령어 인터페이스 (CLI), 그래픽 사용자 인터페이스 (GUI)프로그램 실행(Program execution)프로그램을 메모리에 로드, 실행, 종료I/O 작업(I/O operation)키보드/마우스 입력, 모니터/프린터 출력파일 시스템 조작(File system manipulation)파일 또는 디렉토리 읽기/쓰기, 생성/삭제/검색 등통신(Communications)프로세스 간 정보 교환오류 검출(Error detection)하드웨어 (메모리 오류, power failure)I/O 장치 (네트워크 연결 실패, 프린터 용지 부족)사용자 프로그램 (산술..

운영체제 정의컴퓨터 시스템의 네 가지 구성 요소사용자 (Users)애플리케이션 (Applications) (워드 프로세서, 웹 브라우저, 게임, …)운영체제 (Operating System)하드웨어 (Hardware) (CPU, 메모리, I/O 장치)운영체제 정의운영체제 (Operating System)애플리케이션과 컴퓨터 하드웨어 사이의 중개자(intermediary) 역할을 함.컴퓨터 하드웨어 자원을 관리.애플리케이션을 위한 일부 서비스를 제공.사용자 관점 (User View)운영체제가 애플리케이션을 실행.운영체제가 컴퓨터 시스템을 사용하기 편리하게 만듦.시스템 관점 (System View)운영체제는 자원 할당자 (Resource Allocator).하드웨어 자원: CPU, 메모리, I/O 장치.소프..

분리 집합(Disjoint Set)집합의 정의 : 특정 조건에 맞는 원소의 모임분리 집합(Disjoint Set) : 서로 공통된 원소를 갖지 않는, 즉 교집합을 갖지 않는 복수의 집합분리 집합의 개념은 2개 이상의 집합을 일컬을 때만 사용할 수 있음분리 집합은 교집합을 허락하지 않기 때문에 소속 관계가 분명해야 하는 데이터를 다룰 때 아주 유용함ex) 도서 판매 관리 프로그램에서 일반 도서 집합과 베스트셀러 집합을 만들고, 베스트셀러들의 BookPrice가 베스트셀러 집합의 원소가 되도록 함이처럼 분리 집합은 원소 또는 개체가 '어느 집합에 소속되어 있는가?'라는 정보를 바탕으로 무언가를 하는 알고리즘에 응용할 수 있음분리 집합 표현 보통의 트리와 이진 트리는 부모가 자식을 가리키는 포인터를 갖고 있음..

수식 트리(Expression Tree)수식 이진 트리(Expression Binary Tree)라고 부르기도 함일반적으로 다음 두가지 규칙을 가짐피연산자는 잎 노드이다.연산자는 뿌리 노드 또는 가지 노드이다.ex) 1 * 2 + (7 - 8)의 경우 피연산자 1, 2, 7, 8은 모두 잎 노드, 연산자들은 모두 뿌리 노드 or 가지 노드임뿌리 노드와 가지 노드 모두 피연산자를 양쪽 자식으로 가짐여기서 피연산자는 수(Number)일 수도, 또 다른 식(Expressioin)일 수도 있음ex) + 연산자는 하위 트리가 표현하는 수식 (1 * 2)와 (7 - 8)을 피연산자로 가지고 있음수식 트리는 가장 아래에 있는 하위 수식 트리(잎 노드)로 부터 수 또는 계산 결과값을 병합해 올라가는 과정을 반복하며 계..

이진 트리(Binary Tree)하나의 노드가 자식 노드를 2개까지만 가질 수 있는 트리예시수식을 트리 형태로 표현하는 계산하는 수식 이진 트리(Expression Binary Tree)아주 빠른 데이터 검색을 가능하게 하는 이진 탐색 트리(Binary Search Tree)이진 트리의 종류노드의 최대 차수가 2임모든 이진 트리의 자식 노드 수는 0, 1, 2 중 하나포화 이진 트리(Full Binary Tree): 잎 노드를 제외한 모든 노드가 자식을 둘 씩 가진 이진트리잎 노드들이 모두 같은 깊이에 위치한다는 특징을 가짐완전 이진 트리(Complete Binary Tree): 잎 노드들이 트리 왼쪽부터 차곡차곡 채워져 있는 트리포화 이진 트리로 진화하기 전 단계임트리의 노드를 가능한 완전한 모습으로 ..

트리 ADT트리(Tree)란?나무를 닮은 자료구조HTML이나 XML 문서를 다룰 때 사용하는 DOM, 운영체의 파일 시스템 등이 트리 구조로 이루어져 있음트리의 구성요소트리는 뿌리, 가지, 잎 세 가지 요소로 이루어져 있다.세 가지 요소 모두 똑같은 노드이지만 어디에 위치하는지에 따라 불리는 이름이 달라진다뿌리 : 트리 자료구조의 가장 위에 있는 노드를 가리킴가지 : 뿌리와 잎 사이에 있는 모든 노드를 말함잎 노드(단말 노드) : 가지의 끝에 있는 마지막 노드를 잎 노드(단말 노드)라고 한다.부모, 자식 형제 관계가 존재한다. 위 그림을 봐보자노드 B, C, D를 보면 B에서 C와 D가 뻗어 나오는데 이때 B는 C와 D의 부모(Parent)이고, C와 D는 B의 자식(Children)이다.그리고 한 부모..

Floating-Point Binary Representation부동 소수점 이진 표현 부동 소수점 십진수는 세 가지 구성 요소를 포함함부호 (Sign), 가수 (Significand 또는 Mantissa), 지수 (Exponent)예: -1.23154 x 10^5에서 부호는 음수, 가수는 1.23154, 지수는 5IEEE Binary Floating-Point RepresentationIEEE 이진 부동 소수점 표현  x86 프로세서는 IEEE 754-1985 표준에 지정된 세 가지 형식을 사용 단정밀도 (Single Precision)32비트: 부호 1비트, 지수 8비트, 가수 23비트. approximate 정규화 범위: 2^-126 ~ 2^127. "short real"이라고도 함.Double P..

보호되어 있는 글입니다.