목차
1장 컴퓨터와 자료
2장 자료구조
3장 알고리즘
4장 컴퓨터 구조
5장 운영체제
6장 프로그래밍 언어
7장 데이터베이스
8장 컴퓨터 네트워크
9장 인공지능
1장 컴퓨터와 자료
(1) 컴퓨터
- 컴퓨터 → 프로그램이 가능한 자료처리기
- 프로그램 → 컴퓨터가 자료를 어떻게 처리할지를 알려주는 일련의 명령어의 집합으로, 처리 가능한 작업의 유형과 연산의 집합을 결정
- 초기(1930년대~1950년대)의 특징적인 전자식 컴퓨터 → ENIAC, EDVAC - 컴퓨터 기술의 세대별 분류 → 1세대~5세대
- 컴퓨터의 분류 → 사용 목적(범용 컴퓨터, 전용 컴퓨터), 자료 표현 방식(디지털 컴퓨터, 아날로그 컴퓨터), 성능(슈퍼 컴퓨터, 대형 컴퓨터, 미니 컴퓨터, 워크스테이션, 마이크로 컴퓨터)
(2) 컴퓨터과학
- 다양한 관점에서의 컴퓨터과학의 정의
▸ 자료의 획득, 표현, 처리, 저장, 통신, 접근을 위한 방법들의 실행 가능성, 구조화, 표현, 기계화에 관련된 내용을 다루는 학문
▸ 컴퓨터 자체, 자료, 프로그램, 알고리즘의 연구를 통해 효율적인 자료 처리를 위한 제반 기술과 방법들을 제공하기 위한 학문
▸ 알고리즘과 관련된 이슈를 다루는 학문
- 컴퓨터공학 vs 컴퓨터과학
▸ 컴퓨터공학 : 가격 대비 성능 특성이 가장 좋은 컴퓨터 엔진을 만들기 위해 하드웨어와 소프트웨어 요소를 조립하는 방법에 관심을 둠
▸ 컴퓨터과학 : 현재의 기술에 덜 의존적인 방식으로 주어진 문제에 대한 해결책이 효율적이고 실현할 수 있도록 하는 데 초점을 맞춤
(3) 컴퓨터 시스템
- 완전한 컴퓨터 시스템을 구성하는 4가지 요소 → 하드웨어, 소프트웨어, 자료, 사용자
▸ 하드웨어 : 컴퓨터를 구성하는 물리적인 기계 장치
▸ 소프트웨어 : 프로그램을 총체적으로 표현하는 것이며, 크게 시스템 소프트웨어와 응용 소프트웨어로 구분
▸ 자료(데이터) : 컴퓨터가 처리하는 대상으로 컴퓨터 내부에서 비트 패턴으로 변환되어 처리되며, 출력할 때에는 우리가 알아볼 수 있도록 적절한 변환 과정을 다시 거쳐야 함
▸ 사용자 : 컴퓨터가 자료를 처리하는 전반적인 과정에 다양하고 적극적인 형태로 개입함
- 폰 노이만 모델은 컴퓨터의 내부 구조와 처리 과정을 정의한 모델이다.
▸ 컴퓨터는 4개의 서브시스템인 기억장치, 산술논리연산장치, 제어장치, 입출력장치로 구성된다.
▸ 실행될 프로그램은 메모리에 적재되어야 한다. : 내장 프로그램 방식
▸ 프로그램은 기본 명령어들의 유한개의 조합으로 구성된다.
(4) 자료와 정보
- 자료 정보의 관계 : 정보 = 처리기(자료) I = P(D)
- 자료처리 : 자료를 정보로 가공하고 변환하는 일련의 과정
- 자료 : 현실 세계로부터 관찰이나 측정을 통해 단순히 얻어지는 사실이나 값
- 정보 : 자료를 가공 또는 변환 등의 처리 과정을 거쳐서 얻어진 결과로서, 어떤 상황에 대해 적절한 의사결정을 수행할 수 있게 하는 지식
- 모든 자료는 유형에 상관없이 일관된 자료 표현 방식인 비트 패턴으로 표현된다.
- 자료의 표현 단위 : 비트, 바이트, 워드, KB, MB, GB, TB, PB 등
(5) 진법
- r 진법 : 0, 1, …, r-1까지의 숫자만을 사용해서 수를 표현하는 방식/단위
- 컴퓨터에서는 2진법만을 사용 : 진법(8진법, 10진법, 16진법) 간의 변환이 필요
▸ 2진수를 10진수로 변환 : 각 비트와 해당 위치에 따른 가중치의 곱을 모두 더한다.
▸ 10진수를 r 진수로 변환 : 정수 부분과 소수 부분을 나눠서 변환 (☞ 교재 그림 1.8~1.9)
▸ 2진수와 8진수/16진수의 관계 : 2진수의 3자릿수 = 8진수의 1자릿수, 2진수의 4자릿수 = 16진수의 1자릿수
(6) 정수 표현 방법
- 정수 표현 방법은 크게 부호 없는 정수와 부호 있는 정수로 나눌 수 있고, 부호 있는 정수의 경우에는 다시 부호화-크기 방식, 1의 보수 방식, 2의 보수 방식으로 나눌 수 있다.
▸ 부호 없는 정수 : 부호 비트가 없으며, 주어진 n 비트 전체로 정수(0~2n-1)를 표현한다.
▸ 부호화-크기 방식 : 최상위 1비트를 부호 비트로 사용하고, 음의 정수는 음수에 대한 절대값으로 표현
▸ 1의 보수 방식 : 부호 비트 사용. 음의 정수는 양의 정수 표현에 대한 보수(0 -1, 1 :-0)를 취해서 표현
▸ 2의 보수 방식 : 부호 비트 사용. 음의 정수는 1의 보수 방식의 결과에 1을 더해서 표현
(7) 실수 표현
- 부동소수점 방식을 사용해서 표현
- -10.100011011×25 : (-1)부호×가수×2지수 → 부호(1비트)+지수(m비트)+가수(n비트)
- 지수의 표현
▸ 초과표기법 : 부동소수점의 지수 부분만을 위한 표기 방법으로, m비트가 할당된 경우 두 개의 매직 넘버(초과_2m-1, 초과_2m-1-1)가 존재
▸ 지수값을 저장하는 경우 : (지수값 + 매직 넘버)를 이진수로 표현
▸ 지수값을 해석하는 경우 : 이진수를 십진수로 변환한 값에서 매직 넘버를 뺀다. - 가수의 표현
▸ 정규화 :소수점 바로 왼쪽에 오직 하나의 1만 있도록 소수점의 위치를 조정, 가수값을 저장하는 경우에는 소수점 이하 부분만 저장한다.
(8) 문자 표현
- 각 문자마다 유일한 코드 할당이 이루어지며, 이를 위해 약속된 문자 체계가 필요
▸ 대표적인 종류로는 ASCII(또는 확장된 ASCII)와 유니코드가 있다.
2장 자료구조
(1) 자료구조
- 자료 사이의 논리적 관계를 컴퓨터나 프로그램이 더 쉽게 이해하고 다룰 수 있도록 구성한 것
(2) 배열
- 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수로 묶어놓은 데이터의 집합체이며, 각 원소를 구분하기 위해 인덱스(또는 첨자)와 데이터값의 쌍으로 이루어짐
- 배열의 원소들은 연속적인 기억장소에 저장되어 순차적으로 저장되기 때문에 배열의 시작주소와 각 자료형의 크기를 알면 i번째 원소의 주소를 알면, 직접 접근이 가능함
- 다차원 배열이 저장되는 방식으로는 열 우선 순서와 행 우선 순서가 있음
(3) 연결 리스트
- 노드들을 연결하여 구성하는 것으로, 한 노드는 데이터 필드와 링크 필드로 구성됨
- 단일 연결 리스트 : 링크 필드가 하나이고, 한 방향으로만 검색이 가능함
- 이중 연결 리스트 : 2개의 링크 필드를 사용해서 양방향(선행 노드 방향, 후행 노드 방향)의 검색이 가능함
- 원형 연결 리스트 : 마지막 노드의 링크 필드가 첫 번째 노드에 연결되어, 한 방향이지만 전체 연결 리스트를 원형으로 연결함
(4) 스택
- 리스트의 한쪽 끝에서만 삽입과 삭제가 이루어지는 후입선출(LIFO) 구조
(5) 큐
- 리스트의 한쪽 끝에서는 삽입, 다른 한쪽 끝에서는 삭제가 이루어지는 선입선출(FIFO) 구조
(6) 트리 : 노드와 가지로 구성되어 나무뿌리 모양의 데이터의 계층 관계를 나타내는 자료구조
- 이진 트리 : 차수가 2인 트리를 이진 트리
- 포화이진 트리 : 이진 트리 중에서도 깊이가 k인 이진 트리가 가질 수 있는 최대 노드의 개수(2k-1)를 가진 이진 트리
- 완전이진 트리 : 총 노드의 개수가 (2k+1-1)을 초과하지 않으면서 포화이진 트리의 번호와 일치하는 이진 트리
- 경사 이진 트리 : 한쪽 방향으로 치우친 트리
(7) 트리 순회 방법으로 전위 순회, 중위 순회, 후위 순회가 있음
(8) 그래프 : 정점들의 유한 집합과 정점들의 쌍을 연결하는 간선의 유한집합
- 그래프의 표현 : 인접 행렬, 인접 리스트
- 그래프 순회 방식 : 깊이 우선 탐색, 너비 우선 탐색
3장 알고리즘
(1) 컴퓨터 알고리즘이란?
- 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서에 따라 구성한 것
- 알고리즘이 만족해야 할 조건 → 입출력, 명확성, 유한성, 유효성
- 프로그램 = 자료구조 + 알고리즘
(2) 대표적인 알고리즘의 설계 방법
- 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법
(3) 욕심쟁이 방법
- 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 그 단계에서 가장 최선이라고 볼 수 있는 국부적인 최적해를 선택해 나가면, 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다.
- 여기서 '희망적'이라는 표현은 욕심쟁이 방법을 적용해도 최적해를 구할 수 없는 경우도 존재한다는 것을 의미한다
- 욕심쟁이 방법이 적용 가능한 문제
▸ 거스름돈 문제 → 가게에서 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
▸ 배낭 문제 → 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 배낭에 넣은 방법을 찾는 문제로서, 물체를 쪼갤 수 있다고 가정하며, 만약 물체를 쪼갤 수 없는 경우의 배낭 문제는 욕심쟁이 방법으로 해결할 수 없다.
(4) 분할정복 방법
- 순환적으로 문제를 푸는 방식으로 문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 세 단계를 거친다.
- 적용 가능한 문제 → 퀵 정렬, 합병 정렬, 이진 탐색
- 분할된 문제들은 독립적이어야 한다.
(5) 동적 프로그래밍 방법
- 주어진 문제를 여러 개의 부분 문제로 분할하고, 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고 이를 이용하여 입력 크기가 더욱 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법이다.
- 적용 가능한 문제 → 모든 정점 쌍 간의 최단 경로를 구하는 플로이드 알고리즘
- 부분 문제들은 독립적이지 않아도 된다.
(6) 알고리즘 분석은 두 가지 측면에서 수행
- 정확성 분석 → 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 산출하는지의 여부를 판단한다.
- 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 즉 소요되는 메모리 공간의 크기(“공간 복잡도”)와 수행에 걸리는 시간(“시간 복잡도”)을 추정한다.
- 시간 복잡도
▸ 수행 시간 = 알고리즘에서 사용된 단위 연산들의 수행횟수의 합
▸ 수행 시간은 일반적으로 입력 크기(입력되는 데이터의 크기) n의 함수로 표현
▸ 데이터의 입력 상태에 따라 수행 시간은 달라지며, 일반적으로 최악의 수행 시간을 사용
(7) 점근 성능
- 입력의 크기 n이 충분히 커질 때 알고리즘의 수행 시간이 무엇에 의해 좌우되는가를 나타내는 것
→ 수행 시간이 다항식으로 표현되는 경우에는 입력의 크기가 커짐에 따라 상수항과 차수가 낮은 항들의 역할이 감소하게 되고, 결국 n의 최고차항에 좌우된다.
- 표기법
① “Big-oh” 점근적 상한 f(n)=O(g(n))
② “Big-omega” 점근적 하한 f(n)=Ω(g(n))
③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))
- 시간 복잡도 함수 간의 크기 관계 : O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < … < O(2n)
(8) 정렬의 정의 및 관련 개념
- 정렬 : 여러 원소로 구성된 리스트에 대해서 이 원소들을 키값의 크기 순서에 따라 재배열하는 것
- 내부 정렬과 외부 정렬
▸ 내부 정렬 → 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
▸ 외부 정렬 → 모든 데이터를 주기억장치에 저장할 수 없어서 일부 데이터는 주기억장치에 있고 나머지 데이터는 보조기억장치에 저장된 채 정렬을 하는 방식
- 비교 기반 정렬과 분포 기반 정렬
▸ 비교 기반 정렬 → 데이터의 키값을 직접 비교하여 정렬하는 방식 (선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬)
▸ 분포 기반 정렬 → 데이터의 분포 정보를 이용하여 정렬하는 방식 (계수 정렬, 기수 정렬)
(9) 선택 정렬
- 정렬되지 않은 데이터 중에서 가장 작은 키값을 갖는 원소를 선택한 후, 이것을 미정렬 데이터의 첫 번째 원소와 교환하는 과정을 반복하여 정렬을 수행하는 방법
- 데이터의 입력 상태에 민감하지 않은 수행 시간 O(n2)
(10) 버블 정렬
- 인접한 두 원소를 차례대로 비교하면서 (오름차순의 경우) 왼쪽 데이터의 키값이 오른쪽 데이터의 키값보다 큰 경우 자리바꿈을 통하여 정렬하는 방법
- 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로 정렬된 경우에는 최악의 수행 시간 O(n2)을 가짐
(11) 삽입 정렬
- 미정렬 부분의 첫 번째 원소를 하나씩 꺼내어 정렬된 부분에서 바른 위치에 삽입하여 나열하는 방법
- 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로 정렬된 경우에는 최악의 수행 시간 O(n2)을 가짐
(12) 퀵 정렬
- 특정 원소를 기준으로 주어진 원소들을 두 서브 리스트로 분할하고, 각 서브 리스트에 독립적으로 퀵 정렬을 순환적으로 적용하여 정렬하는 방식
- 피벗 → 리스트를 두 개의 서브 리스트로 분할할 때 기준이 되는 원소로서, 간단히 리스트의 첫 번째 원소를 피벗으로 지정한다.
- 분할 과정 → 퀵 정렬의 가장 핵심적인 부분으로, 피벗을 중심으로 두 서브 리스트로 분할하는 과정 → O(n)
- 최악의 경우 → 피벗 하나만 제자리를 잡고, 나머지 모든 원소가 하나의 서브 리스트로 분할되는 경우 = 피벗이 리스트에서 항상 최대값이나 최소값이 되는 경우 = 입력 데이터가 이미 정렬되어 있고 피벗이 리스트의 맨 왼쪽 원소로 선택되는 경우 → O(n2)
- 최선의 경우 → 피벗을 중심으로 리스트가 거의 같은 크기의 두 개의 서브 리스트로 나뉘는 경우 → O(nlogn)
- 평균 수행 시간 → 피벗 선택의 임의성이 확보되는 경우 → O(nlogn)
(13) 합병 정렬
- 주어진 리스트를 동일한 크기의 두 개의 서브 리스트로 분할하고 각 서브 리스트를 순환적으로 정렬한 후 정렬된 두 서브 리스트를 합병하여 하나로 나열하는 방식
- 합병 과정 → 정렬된 두 서브 리스트를 합병하여 하나의 정렬된 리스트를 만드는 과정
- 최악/평균적인 경우의 시간 복잡도 → O(nlogn)
- 퀵 정렬과 합병 정렬은 모두 분할정복 방법을 적용한 알고리즘이다.
(14) 순차 탐색
- 주어진 원소들을 하나씩 차례로 탐색키와 비교하면서 원하는 키값을 갖는 원소를 찾는 방법 (일반적으로 왼쪽에서부터 하나씩 비교한다)
- 모든 리스트에 적용 가능, 특히 비정렬 데이터의 탐색에 적합한 방법
- 시간 복잡도 O(n)
(15) 이진 탐색
- 정렬된 리스트 형태로 주어진 원소들에 대해 분할정복 방법을 적용한 탐색 방법
- 탐색 방법: 탐색하려는 키와 주어진 리스트의 가운데 원소의 키를 비교해서
▸ 탐색키 = 가운데 원소의 키 ⇒ 탐색 성공
▸ 탐색키 < 가운데 원소의 키 ⇒ 주어진 리스트의 전반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출한다.
▸ 탐색키 > 가운데 원소의 키 ⇒ 주어진 리스트의 후반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출한다.
- 탐색을 한 번 수행할 때마다 탐색 대상이 되는 원소의 개수가 반씩 감소
- 시간 복잡도 O(logn)
- 삽입/삭제 시 정렬된 상태를 유지하기 위한 자료의 이동(평균 n/2번, 최악 n번)으로 인한 오버헤드가 발생
→ 삽입/삭제가 빈번한 경우 부적합
(16) 이진 탐색 트리
- 이진 탐색 트리란? 각 노드 x의 왼쪽 서브 트리의 모든 키는 x의 키보다 작고 오른쪽 서브 트리의 모든 키는 x의 키보다 크다는 조건을 만족시키는 이진 트리
- 탐색 연산 → 루트 노드로부터 시작해서 크기 관계에 따라 트리의 경로를 따라 내려가면서 진행
- 삽입 연산 → 우선 트리를 탐색한 후, 탐색이 실패한 지점에 자식 노드를 생성하여 삽입
- 삭제 연산 → 삭제되는 노드의 자식 개수에 따라 3가지 경우로 나누어 수행
① 자식이 없는 경우(리프 노드): 남은 노드의 위치 조절이 필요하지 않음
② 자식이 하나만 있는 경우: 자식 노드를 삭제되는 노드의 위치로 올리면서 서브 트리 전체도 따라 올린다.
③ 자식이 두 개 모두 있는 경우: 후속자(successor) 노드를 삭제되는 노드의 위치로 올리고, 후속자 노드의 자식 노드를 후속자 노드의 위치로 올리면서 그 서브 트리 전체도 따라 올린다. (successor 노드란? 어떤 노드의 바로 다음 키값을 갖는 노드)
- 평균적인 탐색 시간은 O(logn)이며, 최악의 경우(경사 이진 트리가 생성되는 경우)에는 O(n)이 된다.
(17) 해싱
- 배열에서 인덱스가 주어졌을 때 이를 이용하여 원하는 원소를 상수 시간에 찾듯이, 원소의 키값을 이용하여 데이터 저장을 위한 테이블의 주소를 직접 계산하여 상수 시간 내에 접근할 수 있는 탐색 방법
- 해시 함수 → 키 값을 해시 테이블 주소로 변환하는 함수
▸ 제산 잔여법, 중간 제곱법, 폴딩법, 자릿수 추출법, 기수 변환법 등
- 충돌 해결 방법
▸ 충돌 → 서로 다른 키값 x, y에 대하여 해시 테이블의 주소가 같게 되는 경우
▸ 연쇄법 → 동일한 주소로 해시되는 모든 원소를 연결 리스트 형태로 구성하여 관리
▸ 개방 주소법 → 테이블 내의 다른 곳에 충돌된 데이터를 저장/관리하기 위해서 정해진 방법에 따라 테이블의 다른 위치를 탐사하는 방법 → 종류: 선형 탐사, 이차형 탐사, 이중 해싱
4장 컴퓨터 구조
(1) 컴퓨터 하드웨어의 기본 구성요소
- 중앙처리장치 = 제어장치 + 산술논리연산장치 + 레지스터
- 기억장치, 입력장치, 출력장치
- 시스템 버스 = 주소 버스 + 데이터 버스 + 제어 버스
(2) 불대수
- 이진 변수와 논리연산을 나타내는 대수
- 기본 논리연산 → 논리곱(AND), 논리합(OR), 논리부정(NOT)
- 논리 게이트 → 논리연산을 실제 하드웨어로 구현한 것
- 논리회로 → 논리 게이트들로 구성되며, 조합회로와 순차 회로로 구분
(3) 조합회로와 순차회로
- 조합회로
▸ 출력값이 단순히 현재 입력값에 의해서만 결정되는 회로
▸ 종류 → 전가산기, 디코더, 멀티플렉서
▸ 1비트 전가산기 → 두 개의 비트와 바로 아래 자리에서 올라오는 올림 수를 입력으로 받아서 덧셈을 수행하는 회로, n 비트 전가산기는 1비트 전가산기를 직렬로 연결해 구성
▸ 디코더 → n비트의 이진 코드를 최대 2n개의 서로 다른 정보로 변환해 주는 장치
▸ 멀티플렉서 → 2n개의 데이터 입력선 중에서 하나를 선택하여 단일의 출력으로 내보내는 회로
- 순차 회로
▸ 출력값이 입력값과 기억소자에 저장된 현재 상태에 따라 결정되는 회로
▸ 플립플롭 → 1비트의 상태를 저장하기 위한 기억소자
▸ 종류 → 카운터, 레지스터
▸ 카운터 → 클록 펄스가 입력될 때마다 저장된 이진수의 값을 1씩 증가시키는 장치
(4) 기억장치
- ROM → 한 개의 디코더와 여러 개의 OR 게이트를 사용한 조합회로로 구성 가능
- RAM → 1비트 RAM 기억소자(한 개의 RS플립플롭, 3개의 AND 게이트, 2개의 NOT로 구성), 디코더, OR 게이트를 사용한 순차 회로로 구성 가능하지만, 실제로는 플립플롭이 아닌 축전지로 구현된 DRAM을 사용
- 계층적 구조
▸ 접근 속도와 저장 용량에 따라 기억장치를 구분
→ CPU가 데이터에 접근하면서 가장 적은 비용으로 가장 높은 성능을 얻기 위해 참조의 지역성에 기반을 둔 전략
▸ 레지스터 - 캐시기억장치 - 주기억장치 - 보조기억장치
(5) 명령어
- 명령어 세트 → 컴퓨터 시스템 내에 정의되어 있는 기본적인 명령어들의 집합
- 명령어의 형식과 복잡성에 따른 컴퓨터 구조
▸ CISC → 복합명령어를 포함하여 명령어와 주소지정방식의 수를 많이 사용함으로써 프로그램에 사용되는 전체 명령어의 수를 줄여서 프로그램의 실행 시간을 줄이기 위한 구조
▸ RISC → CISC의 복잡한 명령어를 단순화하여 명령어의 수를 줄이고 하드웨어를 간단히 개신시킨 구조로 각 명령어의 길이를 가능한 한 짧게 함으로써 각 명령어의 실행 시간을 최소화하기 위한 것
- 명령어 형식
▸ 명령어 = 연산자 코드 + 오퍼랜드
▸ 종류(오퍼랜드의 개수에 따른 구분) → 3-주소 명령어, 2-주소 명령어, 1-주소 명령어, 0-주소 명령어
▸ 각 명령어의 연산자와 오퍼랜드는 고유의 이진 패턴으로 표현되고, 프로그램은 이런 2진수가 나열의 형태로 주기억장치에 저장된다.
- 주소지정방식
▸ 연산에 사용될 데이터가 기억장치의 어디에 위치하는 지를 지정하는 방식
▸ 종류 → 즉시 주소지정방식, 직접 주소지정방식, 간접 주소지정방식, 레지스터 주소지정방식, 레지스터 간접 주소지정방식, 상대 주소지정방식, 인덱스된 주소지정방식
(6) 중앙처리장치
- 명령어의 구현 방법
▸ 마이크로프로그램에 의한 제어장치
→ 연산과 명령어 수행 순서 조작회로가 제어기억장치에 저장된 마이크로프로그램으로 기동되는 장치
▸ 직접 회로로 구성된 제어장치
→ 연산과 명령어 수행 회로가 직접 구성된 제어회로에 의해 기동되는 장치
- 특수 레지스터
▸ 누산기(AC), 기억장치 버퍼 레지스터(MBR), 기억장치 주소 레지스터(MAR), 프로그램 카운터(PC), 명령어 레지스터(IR)
- 처리장치 = 연산장치 + 레지스터
▸ 수행되는 모든 연산의 기능은 비트 패턴으로 이루어진 마이크로연산으로 구현
▸ 각 마이크로 연산은 제어단어로 일대일 관계를 가짐
- 제어장치
▸ 기본 기능
① 처리장치를 특정 연산을 수행한 후 처리장치 내의 레지스터 값을 갱신하고 연산 결과를 출력.
② 현재 주어진 명령을 수행한 후 다음에 수행할 명령의 주소정보를 생성
▸ 명령어 사이클: 인출 - 해독 - 실행 - 저장
▸ 구성요소 → PC, IR, 명령어 해독기, 주소결정회로, 제어기억장치, 제어기억장치 주소 레지스터, 제어기억장치 데이터 레지스터
(7) 입출력장치
- 입출력 시스템의 구성요소 : 입출력장치, 입출력장치 제어기, 입출력장치 인터페이스, 입출력 버스
- 입출력 제어 방식 :CPU에 의한 제어 방식(프로그램에 의한 방식, 인터럽트에 의한 방식), DMA 방식, 채널 방식
(8) 병렬처리
- 파이프라인 처리기 : 프로그램 내에 내재하고 있는 시간적 병렬성을 활용
→ 하나의 연산을 서로 다른 기능을 가진 여러 개의 단계로 분할하여 각 단계가 동시에 서로 다른 데이터를 취급하도록 하여 처리 속도의 향상을 도모
- 멀티코어 구조 : 하나의 CPU에 두 개 이상의 코어를 넣어서 동시에 여러 개의 명령어를 처리할 수 있는 구조
5장 운영체제
(1) 운영체제의 주요 기능(자원의 범주) : 프로세서 관리자, 주기억장치 관리자, 장치 관리자, 파일 관리자
(2) 운영체제의 작업 처리 방식
- 일괄처리 시스템 : 처리할 작업이 발생할 때마다 즉각적으로 처리하지 않고 처리해야 할 작업이 일정량에 도달할 때까지 여러 작업을 모아 놓고 작업을 한꺼번에 처리하는 방식
- 다중프로그래밍 시스템 : 여러 개의 프로그램을 효율적으로 실행시키기 위해 여러 개의 프로그램이 컴퓨터 자원이 쉬는 시간에 서로 양보하며 사용하는 방식
- 시분할 처리 시스템 : CPU의 시간을 일정 간격의 작은 시간으로 쪼개서 각 사용자에게 시간 간격이 할당되고, 그동안 직접 컴퓨터와 대화식으로 작업을 수행하는 방식
(3) 주기억장치 할당 방법
- 단일 사용자 연속 기억장치 할당 : 하나의 사용자 프로그램만이 전체 주기억장치에 할당되는 방식
- 고정 분할 다중 프로그래밍 기법 : 다중 프로그래밍 시스템(여러 개의 프로그램이 실행되는 시스템)에서 주기억장치를 여러 개의 고정된 크기의 영역으로 분할하고, 실행 중인 여러 개의 프로세스에 각각 할당하는 방식
- 동적 분할 프로그래밍 기법 : 프로그램이 주기억장치에 적재될 때마다 모든 작업이 필요로 하는 크기 (고정된 크기가 아니라 다양한 크기)만큼 연속된 공간을 할당해주는 방식
(4) 가상기억장치 관리 기법
- 페이징 기법 : 보조기억장치로부터 프로그램 코드나 데이터를 페이지(page)라고 불리는 동일한 크기의 블록으로 쪼개어서 주기억장치에 적재하여 접근하는 방식
- 세그먼테이션 기법 : 세그먼테이션 기법은 프로그램 코드나 데이터를 일정하지 않은 서로 다른 크기로 분할하여 주기억장치에 적재하여 접근하는 방식
(5) 프로세스 : 실행 상태에 있는 프로그램
- 프로세스의 상태 : 생성, 준비, 실행, 대기, 종료
(6) 중앙처리장치 스케줄링 기법: 선점 방식과 비선점 방식
- 기한부 스케줄링: 기한부 스케줄링은 기한이 되면 중앙처리장치를 양보하는 방식
- 우선순위 스케줄링 : 우선순위가 높은 프로세스부터 먼저 처리하는 방식
- FCFS 스케줄링 : 준비 큐에 도착한 순서대로 중앙처리장치를 할당받는 방식
- SJF 스케줄링 : 현재 준비 큐에 있는 프로세스 중에서 수행시간이 가장 짧을 것으로 예상하는 프로세스를 먼저 처리하는 방식
- RR 스케줄링 : 프로세스가 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한하는 방식
(7) 교착상태 : 2개 이상의 프로세스가 대기 중인 프로세스 중의 하나에 의해서만 발생할 수 있는 자원의 획득이나 해제를 무작정 기다리고 있는 상태
- 교착 상태의 필수 조건 : 상호배제 조건, 대기 조건, 비선점 조건, 환형 대기 조건
- 교착 상태 처리 방법 : 교착상태의 방지, 교착상태의 회피, 교착상태의 탐지, 교착상태의 복구
(8) 디스크 스케줄링 기법
- FCFS(First-Come First Served) 스케줄링 기법 : 먼저 도착한 디스크 접근 요청이 가장 먼저 서비스를 받는 방법
- SSTF(Shortest Seek Time First) 스케줄링 기법 : 현재 디스크 헤드의 위치에서 가장 짧은 트랙 탐색 거리(또는 탐색 시간)를 가진 디스크 접근 요청을 먼저 처리하는 방식
- SCAN 스케줄링 기법 : 한쪽에서 가장 짧은 탐색 거리의 디스크 접근 요청을 먼저 서비스하는 방식
- SLTF(Shortest Latency Time First) 스케줄링 기법 : 디스크 헤드가 특정 실린더에 도착하면 그 실린더 내의 모든 요구를 검사한 후 가장 짧은 회전지연을 하는 요구들에 우선으로 서비스하는 방식
(9) 파일 구조 : 파일을 구성하는 레코드들이 보조기억장치에서의 배치 방법
(10) 디스크 공간 할당 방식
- 연속 할당(contiguous allocation) 기법 : 파일이 보조기억장치에 저장될 때 연속된 물리적 공간을 할당받는 기법
- 불연속 할당(non contiguous allocation) 기법 : 파일을 작은 단위로 나누고, 보조기억장치의 불연속적인 공간을 나누어 할당받는 기법
6장 프로그래밍 언어
(0) 프로그래밍 언어 학습 이유
- 프로그래밍 개념의 표현 능력 향상
- 효율적인 알고리즘 개발 능력 향상
- 주어진 과제를 해결하는 적절한 언어의 선택 능력 향상
- 새로운 언어에 대한 적응 능력 향상
- 새로운 언어를 개발할 수 있는 능력 향상
(1) 프로그래밍 언어의 파싱 트리
- 단말 심벌(terminal symbol) : 문장을 이루는 단어들을 단말 심벌
- 비단말 심벌(non-terminal symbol) : 비단말 심벌은 단말 심벌이 아니면서 복합적으로 나열된 단말 심벌과 비단말 심벌의 조합
- 생성 규칙(production rule) : 하나의 비단말 심벌이 어떻게 다른 단말 심벌이나 비단말 심벌을 대체할 수 있는지 정의하는 규칙
- 시작 심벌(start symbol) : 가장 상위 계층의 비단말 심벌로 보통 <문장>에 해당함
(2) 프로그램에서 실행 가능 코드로의 변환
- 어휘분석 : 프로그램을 구성하는 문자들의 나열로부터 단어(token, 토큰)를 추출하는 과정
- 구문 분석 : 어휘 분석의 결과로 나온 토큰들의 나열이 해당 프로그래밍 언어의 문법에 맞는지를 확인하는 과정
- 코드 생성 : 구문 분석의 결과로 변수, 상수, 제어의 흐름 등이 결정되면 이러한 각각의 명령어를 어셈블리어로 풀어쓰거나 직접 기계어 이진 코드가 생성
(3) 프로그래밍 언어의 기본 공통 개념
- 대입문(할당문) : 변수나 기억장치 주소에 값을 저장하는 역할
(1) 변수의 유효범위
- 변수나 기타 식별자가 코드의 어떤 범위에서 유효한가 하는 유효 범위 결정 문제 (변수에 대한 저장장치의 할당이 유지되는가에 대한 문제)
(2) 함수의 매개변수 :
- 매개변수(parameter) : 호출하는 프로그램과 호출되는 함수 사이에서 주고받는 데이터
- 형식매개변수 : 호출되는 함수의 정의에 사용된 매개변수
- 실매개 변수 : 호출하는 프로그램에서 함수를 호출하기 위해 사용된 매개변수
(3) 변수의 수명 : 변수가 값을 저장하기 위해 기억장소를 할당받고 있는 시간
(4) 객체 지향 프로그램을 위한 추상 자료형
- 자료와 그 자료를 처리할 연산을 함께 선언할 수 있어야 하며, 선언은 구현에 의존적이어서는 안 되며, 연산의 선언에는 의미에 대한 명세가 포함되어야 함.
- 정보 은닉(information hiding) 개념을 도입하여 프로그램을 쉽게 읽을 수 있어야 하고 유지 보수를 쉽게 해야 함.
7장 데이터베이스
(1) 데이터베이스
- 파일 처리 시스템에서의 데이터 종속성과 데이터 중복성의 문제를 해결하기 위해 데이터 공유의 개념을 바탕으로 등장
- 한 조직의 여러 응용 시스템이 공용으로 사용하기 위한 통합, 저장된 운영 데이터의 집합
- 특성 → 실시간 접근성, 계속적인 변화, 동시 공유, 내용에 의한 참조
(2) 데이터베이스 시스템
- 데이터를 데이터베이스에 저장하고 관리해서 필요한 정보를 생성하는 컴퓨터 중심의 시스템
- 3단계 구조
▸ 추상화와 데이터 독립성을 확보하기 위해 3단계(외부 단계, 개념 단계, 내부 단계)로 구성
▸ 스키마 → DB 구조에 대한 정의와 제약조건의 명세를 기술한 것으로 외부 스키마(서브 스키마), 개념 스키마, 내부 스키마(저장 스키마)로 구분
▸ 사상 → 외부/개념 사상과 개념/내부 사상을 통해 데이터 독립성을 제공
- 구성요소
▸ 데이터베이스
▸ 데이터베이스 관리 시스템(DBMS) : 데이터베이스의 구성, 접근 방법, 관리 유지 등에 대해 모든 책임과 권한을 갖고 응용 프로그램과 데이터의 중재자 역할을 담당하는 소프트웨어 시스템
▸ 데이터 언어 : DBMS와 통신을 할 수 있는 수단으로, 데이터 정의어, 데이터 조작어, 데이터 제어어로 구분
▸ 데이터베이스 사용자 : DB에 접근하는 사람의 총칭, 일반 사용자, 응용 프로그래머, DBA
▸ 데이터베이스 관리자(DBA) : 데이터 정의어와 데이터 제어어를 통해 DB를 정의하고 제어할 목적으로 DB에 접근하여 관리하는 사람
▸ 데이터베이스 기계 : 데이터베이스 관리 기능을 효율적으로 수행할 수 있도록 특화되어 설계된 하드웨어 또는 소프트웨어
(3) 데이터 모델링
- 실세계 데이터를 데이터 모델상의 DB 구조로 변환하는 과정
- 데이터 모델
→ DB 구조를 명시하기 위해 사용할 수 있는 다양한 개념의 집합
→ 지원 개념에 따라 개념적 모델, 구현 모델, 물리적 모델로 구분
- 데이터베이스 구현 모델
▸ 종류 → 관계형 모델, 객체지향형 모델, 객체관계형 모델, 망형 모델, 계층형 모델
- 관계형 모델
▸ 실세계의 정보를 2차원 테이블의 형식으로 나타내 구현한 것
▸ 주요 용어 → 릴레이션, 투플, 속성, 차수, 영역, 카디널리티
▸ 키 → 각 투플에 접근할 때 유일하게 구분되는 속성 집합 → 기본키, 후보키, 외래키
▸ 릴레이션 = 릴레이션 스키마 + 릴레이션 인스턴스
▸ 릴레이션의 특징 → 투플의 유일성, 투플의 무순서성, 속성의 무순서성, 속성값의 원자성
▸ 제약조건 → 모든 릴레이션 인스턴스가 만족해야 하는 조건, 영역 제약조건, 키 제약조건, 개체 무결성 제약조건, 참조 무결성 제약조건
(4) 데이터베이스의 설계
- 사용자의 요구 조건에서부터 DB 구조를 도출해 내는 과정
- 요구 조건 분석 → 개념적 설계 → 논리적 설계 → 물리적 설계 → 구현
▸ 요구 조건 분석 → 데이터 및 처리 요구 조건 분석
▸ 개념적 설계 → DBMS에 독립적인 개념 스키마 설계, 트랜잭션 모델링
▸ 논리적 설계 → 목표 DBMS에 맞는 스키마 설계, 트랜잭션 인터페이스 설계
▸ 물리적 설계 → 목표 DBMS에 맞는 물리적 구조 설계, 트랜잭션 세부 설계
▸ 구현 → 목표 DBMS DDL로 스키마 작성, 트랜잭션 작성
(2) E-R 모델
- 현실 세계에 존재하는 개체와 개체 간의 관계를 사람이 이해할 수 있도록 개념적으로 표현하는 방법
▸ 개체 → 데이터로 표현하려는 실세계의 유무형의 사물로서, 개체의 특성이나 상태를 설명해주는 속성의 집합을 가진다.
▸ 관계 → 개체 집합 사이의 대응성(사상)을 의미하며, 미리 어떤 관계를 정의해놓고 주어진 값을 정의된 관계에 따라 해석하면 유용한 의미의 표현이 가능
▸ E-R 다이어그램 → E-R 모델을 그래프로 표현한 것으로, 기본적으로 개체 타입을 사각형, 관계를 다이아몬드, 속성은 타원으로 나타내고 이들을 연결하는 링크로 구성
▸ E-R 다이어그램을 관계 데이터 모델로 변환하는 논리적 모델링 과정
① 사각형의 개체 타입은 개체 릴레이션으로 변환(개체 타입의 속성은 해당 개체 릴레이션의 속성으로 포함),
② 다이아몬드의 관계 타입은 관계 릴레이션으로 변환 (연관된 개체 타입의 키 속성을 관계 릴레이션의 속성으로 포함, 관계에 속한 속성은 관계 릴레이션의 속성으로 포함)
(3) SQL (Structured Query Language )
- 구조화된 질의어
- 데이터 정의어
▸ 스키마, 도메인, 테이블, 뷰, 인덱스를 정의, 변경, 제거하는 문장
▸ CREATE 문, ALTER 문, DROP 문
- 데이터 조작어
▸ 기본 테이블과 뷰를 대상으로 검색, 갱신, 삭제, 삽입을 수행하는 문장
▸ SELECT 문, UPDATE 문, DELETE 문, INSERT 문
- 뷰
▸ 하나 이상의 기본 테이블로부터 유도되어 만들어지는 가상 테이블
→ 뷰 내용은 물리적으로 구현되어 존재하는 것이 아니라 뷰에 대한 조작을 요구할 때마다 기본 테이블의 데이터를 이용해서 내용을 만드는 것
8장 컴퓨터 네트워크
(1) 네트워크의 구성 요소
- 채널(channel) : 모든 통신은 전선, 전화선, 광케이블, 무선 링크 등 통신 매체를 통해서 통신 신호가 전달된다. 통신 신호가 실제로 전달되는 통로
- 주파수(frequency) : 통신채널을 통해 전달되는 통신 신호는 디지털/아날로그 모두 주기성을 가지는 파형의 모습을 가지고 있는데, 이 통신 신호가 초당 몇 번 진동하는가를 계산한 것
- 대역폭(bandwidth) : 대역폭은 통신 채널의 최대 주파수에서 최소 주파수 사이의 주파수 대역
- 노드(node) : 네트워크에 연결된 컴퓨터나 관련 장비
- 네트워크 인터페이스(network interface) : 컴퓨터와 네트워크를 연결해주는 장치
- 프로토콜(protocol) : 통신 프로토콜은 컴퓨터 통신을 위해 통신을 하는 노드 간의 합의된 통신 약속
(2) 컴퓨터 네트워크의 연결 형태
- 버스(bus)형 컴퓨터 네트워크 : 버스형의 경우 컴퓨터들이 하나의 버스(기본적으로 대역폭이 넓은 채널)를 공유하면서 메시지 송신 시 버스에 방송하듯 버스에 연결된 모든 컴퓨터에 메시지를 보내는 형태
- 성(star)형 컴퓨터 네트워크 : 중앙에 있는 컴퓨터가 모든 메시지의 중계자 역할을 하며, 모든 메시지는 먼저 중앙의 컴퓨터로 보내지고, 중앙의 컴퓨터가 수신한 메시지를 다양한 목적지 컴퓨터에 전달되는 형태
- 원(ring)형 컴퓨터 네트워크 : 원형 컴퓨터 네트워크는 메시지가 원형 네트워크를 돌면서 차례로 다음 컴퓨터로 전달되어 최종 수신 컴퓨터에 도달할 때까지 계속 전달되는 형태
(3) 메시지 교환(switching) 방식
- 회선 교환 방식(circuit switching) : 메시지의 송신 컴퓨터에서 수신 컴퓨터까지 여러 개의 스위치를 통해 물리적으로 연결된 임시 전용 회선을 동적으로 구성한 후, 임시로 설정된 회선을 통해서 메시지를 주고받는 방식
- 메시지 교환 방식(message switching) : 송신하려는 메시지 전체를 한 단계씩 목적지 방향으로 스위치(또는 컴퓨터, 라우터 등)를 거쳐서 전송하는 방식
- 패킷 교환 방식(packet switching) : 메시지를 패킷(packet)이라는 작은 단위로 나누어 패킷별로 보내는 방식
(4) OSI 참조 모델
- 물리 계층(physical layer) : 물리적으로 연결된 채널을 통해 비트 단위로 전송되는 계층
- 데이터링크 계층(data link layer) : 직접 연결된 두 컴퓨터나 장비 간에 프레임(frame, 블록 단위의 정보) 단위로 전송하는 계층
- 네트워크 계층(network layer) : 패킷 단위의 전송이 이루어지는 계층
- 전송 계층(transport layer) : 세그먼트 또는 데이터 그램 단위의 메시지가 송신 컴퓨터에서 수신 컴퓨터까지 신뢰성을 보장하며 전달하는 계층
- 세션 계층(session layer) : 통신 컴퓨터 간 연결의 접속/차단과 데이터 통신 방식을 결정하는 계층
- 표현 계층(presentation layer) : 응용 계층에서의 데이터의 사용 방식과 무관하게 잘 작동할 수 있도록 해주는 계층
- 응용 계층(application layer) : 웹에서 사용하는 HTTP나 파일 전송을 위한 FTP, 이메일 전송을 위한 SMTP 등과 같은 응용 프로토콜의 기능을 지원하는 계층
9장 인공지능
AI (Artificial Intelligence) : 1956 존 메카시, ‘다트머스 학회, 인공지능 연구회‘:
- 전산학, 공학, 과학, 인문학, 논리학, 확률론, 통계학, 게임이론, 전자공학, 기계공학, 로보틱스, 심리학, 인지과학, 심리철학, 윤리학, 신경과학, 뇌과학, 진화론, 유전공학 등
- 약한 인공지능 : 개체 내부의 주관적인 현상에 대해서는 관심이 없으며, 오직 시스템이 실생활에 유용한 행동을 할 수 있는지에 초점을 맞춤
- 강한 인공지능 : 인공지능 시스템은 실제로도 내부적인 이해를 가지고 있다고 인정해야 함. 이런 시스템을 만드는 것이 궁극적인 목표
탐색 : 가장 기초적인 인공지능 방법 중 하나
탐색 문제 : 상태공간, 시작 상태, 연산자의 집합, 목적 상태로의 정의
지식 미사용 탐색 : 너비 우선, 깊이 우선, 깊이 제한, 반복 심화 탐색 등이 존재
지식 사용 탐색 : 최선 우선, 탐욕스러운 방법, A-star, 반복 심화 A-star 등이 존재
추론 : 주어진 논리식의 집합으로부터 새로운 논리식을 도출하는 것
인공신경망 : 입력/목표 출력의 쌍만을 가지고 입력에서 출력으로 가는 함수를 자동으로 학습
퍼셉트론 : 단층 인공신경망의 대표적인 예로, 선형 분리 가능한 문제만을 해결
오류 역전파 알고리즘 : 다층 인공신경망의 대표적인 예로, 기울기법을 사용해 학습
유전자 알고리즘 : 자연계의 진화과정을 본 뜬 학습 방법
유전자 알고리즘의 주요 연산 : 선택, 번식, 변이가 있으며, 각 개체의 적합도 계산이 중요한 요건