본문 바로가기

장원익 기술블로그

💻 Computer Science191

[운영체제] 2. 컴퓨터 시스템의 동작 컴퓨터 시스템의 동작 컴퓨터 시스템으로 작업을 처리할 때는 다음과 같은 순서로 이루어지는데 입력장치로 정보를 입력받아 메모리에 저장 메모리에 저장한 정보를 프로그램 제어에 따라 인출 후 연산장치에서 처리 처리한 정보를 출력 또는 보조기억장치에 저장 입력장치로부터 유입되는 정보는 데이터와 명령어로 분류된다. 명령어 : 실행할 산술, 논리 연산의 동작을 명시하는 문장으로 명령어의 집합은 프로그램이 된다. 명령어의 구조 명령어는 프로세서가 실행할 연산인 연산 부호와 명령어가 처리할 데이터, 데이터를 저장한 레지스터나 메모리 주소인 피연산자로 구분된다. 명연산 부호 (Operation Code): 연산을 지정하며 산술연산, 논리연산, 시프트, 보수 등을 수행 피연산자 (Operand): 연산할 데이터의 정보를 .. 2019. 12. 7.

[운영체제] 1. 컴퓨터 하드웨어의 구성 컴퓨터 하드웨어의 구성 컴퓨터 시스템은 물리적 장치인 하드웨어와 명령어로 어떤 작업을 지시할 수 있게 작성한 프로그램인 소프트웨어로 구성된다. 하드웨어는 크게 프로세서(CPU) 메모리(RAM) 주변장치로 이루어져 있고 이들은 시스템 버스로 연결된다. 프로세서 프로세서는 하드웨어에 부착된 모든 장치의 동작을 제어하고 명령을 실행한다. 보통 CPU라고 부르기도 하지만 소프트웨어적 느낌이 강한 프로세서를 주로 이야기할 것이다. 프로세서에서는 크게 레지스터 연산장치 제어 장치로 구분되며 이들은 또한내부 버스로 연결된다. 레지스터 레지스터는 여러 관점으로 구분할 수 있는데 용도에 따라 전용 레지스터 와 범용 레지스터로 구분되며 사용 용도에 따라 사용자 가시 레지스터(user-visible) 사용자 불가시 레지스터.. 2019. 12. 7.

[알고리즘-이론] 09 집합의 처리 집합의 처리 상호 배타적인 여러 개의 집합을 처리해야 할 경우가 있는데 최소 신장 트리를 위한 크루스칼 알고리즘에서 상호 배타적인 집합을 처리하는 알고리즘이 필요하다. 집합의 관리에서 필요한 연산은 임의의 원소가 어느 집합에 속하는지 알나내는 연산과 두 집합을 합하는 연산이다. 여기서 말 하는 상호 배타적인 집합은 서로의 교집합이 공집합인 경우를 뜻한다. 연결 리스트를 이용한 집합의 처리 연결 리스트를 이용한 표현은 쉽고 직관적이다. ++각 원소당 하나의 노드를 만들고 이들을 연결리스트로 연결한다++ 노드는 두 개의 포인터와 원소를 갖는 한 개의 필드로 이루어 진다. 다음 원소 포인터 -> 다음 원소를 가리키는 포인터. 각 집합에는 마지막 원소를 가리키는 tail이라는 변수를 둔다. 대표 원소 포인터 -.. 2019. 11. 23.

[알고리즘-이론] 해시 테이블 (Hash Table) 해시 테이블 해시 테이블은 검색의 평균 시간 복잡도가 O(1)이 되는 검색에 최고의 알고리즘이다. 검색 트리는 원소가 저장될 자리가 이미 트리에 존재하는 원소와 비교하여 결정되는 반면, 해시 테이블은 원소가 저장될 자리에 값에 의해 결정되는 자료구조이다. 해시 테이블은 단계적으로 검색키 -> 주소 계산 -> 테이블 참조 의 흐름으로 검색이 이루어진다. 검색 키 해시 함수 h(x) = x mod m에 의해 검색 키가 결정되고 x는 사용자 입력 값,(배열 값) m은 해시 테이블의 크기를 뜻한다. 주소 계산 주소 계산은 검색 키를 통해서 x mod m을 실질적으로 행하는 과정이다. 테이블 참조 검색 키를 통한 주소 계산이 이루어진 후 검색을 하는 단계이다. 원소가 저장될 자리가 값에 의해 결정되므로 평균 한 .. 2019. 11. 23.

[알고리즘-이론] 레드 블랙 트리(Red-Black Tree) 레드-블랙 트리(Red-Black Tree) 이진 검색 트리에서 시간 복잡도는 O(log n)이 될 수도 있고 O(n)이 될 수도 있다고 하였는데 이는 트리의 높이에 따라 결정된다고 했다. 이러한 단점들을 극복하기 위해서 고안해 낸 것은 바로 ==균형잡힌 이진 검색 트리== 이다. 균형잡힌 이진 검색 트리란 것은 최악의 경우 에도 이진 트리의 균형이 맞게 유지되도록 하는 것을 뜻한다. 레드 블랙 트리는 이진 검색 트리의 모든 노드에 레드 또는 블랙의 색상을 칠하는데 다음과 같은 성질을 만족해한다. 1. Root Property: 루트는 블랙이다. 2. External Property: 모든 리프(NIL)는 블랙이다. 3. Internal Property: 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.. 2019. 11. 23.

[알고리즘-이론] 이진 검색 트리(Binary Search Tree) 이진 검색 트리(Binary Search Tree) 이진 검색 트리에 대해서 공부하기 전에 트리에 대해서 먼저 알고 넘어가자 ##트리(Binary Search Tree)란? 트리란 자료들이 List, Stack, Queue와 같은 1:1 관계의 선형 구조가 아닌 1:n 관계의 비선형 구조로 계층 관계로 만들어진 계층형 자료구조라고 한다. 위의 그림에서 숫자들은 아래의 숫자들을 연결하는 관계를 갖고 이를 부모-자식 관계라고 한다. 형제 관계란? 30은 아래로(계층적으로) 20과 40이 연결되어 있다면 부모는 30이 되고 자식은 각각 20과40이 되며 이 둘은 서로 형제관계 라고한다. 노드란? 이 때 30은 부모 노드가 되고 20과 40은 각각의 자식 노드라고 불린다. 이를 미루어 보았을 때 노드는 각각의 .. 2019. 11. 23.

이전 1 ··· 28 29 30 31 32 다음

티스토리툴바