컴퓨터과학 총정리~!

1.컴퓨터와 자료

- 폰노이만 모델 : 컴퓨터의 내부 구조와 처리 과정을 정의한 모델로서, 현대의 모든 컴퓨터는 이 모델을 기반으로 한다.

- 워드 : 컴퓨터 연산의 기본 단위가 되는 정보의 단위로서, 시스템에 따라 달라진다.

- ASCII (American Standard Code for Information Interchange, 정보 교환을 위한 미국 표준 코드)

- 유니코드 ( Unicode) : 세계의 모든 문자를 컴퓨터에서 일관되게 표현하고 다룰 수 있도록 설계된 산업 표준의 코드체계로서, 사용중인 플랫폼, 프로그램, 언어에 무관한 특징을 가지며 1995년 국제표준으로 제정되었다.

 

2. 자료구조

- 자료구조란 컴퓨터로 자료를 처리하기 위해서는 자료 사이에 존재하는 다양하고도 복잡한 관계를 적절히 나타낼 수 있어야 하며 , 자료 사이의 논리적 관계를 프로그램에 의해 쉽게 이용하도록 구성한 개별적인 자료 원소들의 집합을 의미한다.

- 이진트리 : 트리 중에서 차수가 2인 트리를 의미하고, 모든 노드의 차수는 최대2를 넘지 않으며 모든 노드는 최대 2개의  서브트리를 가짐(데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조) 

   * AVL 트리 → 균형 요소가 –, 0, 1이 되어 균형을 이루고 있는 트리(균형 요소(balance factor)→왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이의 차이)

   * 완전이진트리 - 트리의 최대 레벨이 K일 때, K-1까지는 포화 이진 트리를 형성하고, 레벨 K에서는 왼쪽부터 오른쪽으로 채워진 트리

 

 

3. 알고리즘

- 알고리즘이란 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 유한개의 일련의 명령들을 순서에 따라 구성한 것

- 욕심쟁이 방법 - 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 그 단계에서 '가장 최고' 라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법

- 분할정복 방법 - 순환적으로 문제를 푸는 방식으로 문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 단계를 거친다.

- 동적프로그래밍 방법 : 주어진 문제를 여러 개의  부분 문제로 분할하고, 가장 작은 부분 문제부터 해를 구하여 테이블(표)에 저장해 놓고 이를 이용하여 입력 크기가 더욱 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법

- 거스름돈 문제 : 가게에서 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제

- 배낭문제 : 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾아내는 문제

 * N개의 각 물체에는 각각 무게와 이익이 부여되어 있고, 물체를 쪼갤 수 있다고 가정한다.

- 시간복잡도 : 알고리즘을 실행시켜 완료하는데 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 횟수를 모두 더해서 나타낸다.

- 점근성능 : 입력의 크기 N이 충분히 커질 때의 알고리즘의 성능

- 선택정렬 : 주어진 원소 중에서 가장 작은 키값을 갖는 원소를 선택하여 차례대로 나열하는 방법

- 버블정렬 : 주어진 리스트의 왼쪽에서부터 모든 인접한 두 원소를 차례대로 비교하면서 왼쪽의 값이 더 큰 경우에는 오른쪽의 값과의 자리바꿈을 통해 정렬하는 방법

 

 

 

-순차 탐색 : 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로 비교하여 원하는 값을 갖는 원소를 찾는 방법

- 이진탐색 :  정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 키 값을 찾는 방법

- 이진탐색트리 : 각 노드 X의 왼쪽 서브 트리의 모든 키는 X의 키도다 작고 오른쪽 서브 트리의 모든 키는 X의 키보다 큰 값을 갖는 이진 트리

- 해시함수 : 주어진 키 값을 이용하여 해시테이블의 주소를 계산하는 함수

  *종류 : 제산 잔여법, 중간 제곱법, 폴딩법, 자릿수 추출법, 기수 변환법 등

- 충돌 : 서로 다른 둘 이상의 키가 해시테이블의 동일한 주소로 사상되는 현상

 * 충돌 해결 방법

 -> 연쇄법, 개방 주소법(선형 탐사법, 이차형탐사, 이중해싱)

 

4. 컴퓨터 구조

- 불대수 : 디지털 회로의 설계와 분석을 위해서 이진 변수의 논리연산을 나타내는 대수

- 시스템 버스 : 중앙처리장치와 컴퓨터 시스템 내의 다른 장치 간의 물리적 연결 및 데이터 교환의 통로로서, 주소 버스, 데이터 버스, 제어 버스로 구성된다.

- 논리 게이트

 논리연산을 하드웨어로 구혆나 것으로 논리회로를 구성하는 기본 소자

- 조합회로

 논리 게이트로 구성되고 기억회로는 가지고 있지 않기 때문에 출력값이 단순히 현재 입력값의 조합에 의해서만 결정되는 회로

 - 순차회로

 연산의 각 단계마다 회로의 특정 상태가 저장되고 참조되는 회로로서, 출력값이 입력값과 기억소자에 저장된 현재 상태에 따라 결정되는 회로

- 플립플롭

 1비트의 정보를 저장할 수 있는 장치로서, 입력 신호로 상태를 바꾸도록 지시할 때까지는 현재의 이진상태를 유지하는 논리소자

- 전가산기

 두개의 2진수를 입력받고 바로 아래 자리에서 올라오는 올림수도 고려하여 덧셈을 수행하는 조합회로

- 디코더

  N비트의 이진코드를 최대 2n개의 서로 다른 정보로 변환해 주는 조합회로로서, 출력 중에서 오직 한 개만 1이 되고 나머지 출력은 모두 0이 된다.

- 멀티플렉서

 여러 개의 입력선 중에서 하나를 선택하여 단일의 출력을 내보내는 조합회로

-카운터

 플립플롭을 사용하는 순차 회로로 클록 펄스가 입력될 때마다 저장된 이진수가 1식증가하는 장치

- 참조의 지역성

 기억장치의 특정 위치에 있는 정보를 참조하고 있을 때 다음 순간에 접근할 위치가 현재의 접근위치에 근접해 있거나, 최근에 접근한 위치들이 가까운 미래에 다시 접근될 가능성이 크다는 것을 의미한다

- 캐시기억장치 

 CPU와 주기억장치 사이에 있는 접근속도가 빠른 소규모 기억장치로, 수행중인 명령어와 자주 사용하는 데이터를 저장하였다가  CPU요청이 있을 때 즉시 제공하여 CPU와 주기억장치 간의 속도 차이를 줄여주기 위한 것

- 명령어 싸이클 : 인출(fetch), 해독(decode), 실행(execute) , 저장(write back)

- 병렬처리

  * 파이프라인 처리기 : 하나의 연산을 서로 다른 기능을 가진 여러개의 단계로 분할하여, 각 단계가 동시에 서로 다른 데이터를 취급하는 병렬처리 기술 -> 분할되는 각 명령어 간의 충돌/간섭이 일어나지 않아야 한다.

 * 멀티코어 구조 : 하나의 CPU에 두 개 이상의 코어를 넣어서 동시에 여러 개의 명령어를 처리할 수 있는 구조

 

 

5. 운영체제

 

6. 프로그래밍 언어

파스트리  : 문장의 구조를 표현하는 트
컴파일 과정 : 프로그램 입력 → [어휘 분석] → [구문 분석] → [코드 생성] → 실행코드 출력

❒BNF(Backus-Naur Form)

•PL의 정확한 문법을 기술하기 위한 형식으로 주로 사용되는 방법

▪터미널: 이중따옴표(“ ”)안의 문자열

▪논-터미널: 부등호(< >) 안의 문자열

▪메타심벌: 여러 개 중 택일 ... | ..., 0번 이상 반복 , ... 6, 선택 사항 [ ... ]

•<조건문>에 대한 BNF와 파스트리의 예: (☞교재 201쪽과 그림 5.2

•“<수식1> = <수식2>”의 의미 → <수식2>의 값을 <수식1>의 주소가 가리키는 저 장 장소에 저장하라.

▪<수식1> : l-value라고 하고 값이 저장될 위치를 가리킴

▪<수식2> : r-value라고 하고, 저장할 값을 의미

▪값호출(call-by-value) 방식 → 실매개변수의 값만을 복사해서 형식매개변 수에게 전달한다. 따라서 피호출 함수 내에서 형식매개변수의 상태가 변화 더라도 실매개변수 에게는 아무런 영향을 미치지 않음 → C언어의 기본 방법

▪참조호출(call-by-reference) 방식 → 실매개변수의 기억장소의 주소를 형식매개변수 로 전달한다. 이는 결국 실매개변수와 형식매개변수가 같은 기억장소를 공유하는 것을 의미하기 때문에 형식매개변수의 변화는 결국 실매개변수의 상태 변화로 이어 진다

▪C++ → C언어 기반으로 시뮬라67로부터의 클래스/객체 개념을 추가, 크고 복잡한 언어(절차적 프로그래밍과 객체지향 프로그램을 모두 지원)

▪Java → 가전제품의 내장형 전자장치를 위해 개발된 언어, C++ 기반으로 상당히 단순화된 형태로서 오직 객체지향 프로그래밍 개념만 지원, 웹 프로그래밍을 위해 널리 사용

 

7. 데이터베이스

 - 데이터일관성 : 현실 세계의 한 사실을 나타내는 두 개 이상의 데이터간의 일치 여부

 - 데이터 무결성 : 데이터베이스에 들어있는 데이터 값과 그것이 표현하는 현실 세계의 실제값이 일치하는 정확

- 투플(행,레코드), 속성(열, 필드, 데이터항목), 영역(도메인, 필드가 가질 수 있는 값), 카디널리티(투플의 개수), 차수(필드의 개수

- 키 → 각 투플에 접근할 때 유일하게 구분되는 속성 집합

  * 기본키(primary key) → 각 투플을 유일하게 구분하는 최소 단위의 속성 .

  * 후보키(candidate key) → 각 투플을 구분할 수 있는 여러 개의 속성 중에서 기본 키 이외의 속성 

  * 외래키(foreign key) → 어떤 릴레이션에 속해 있는 속성이나 속성 집합이 다른 릴 레이션의 기본키가 되는 키

8. 컴퓨터 네트워크