❓컴퓨터란 무엇인가

프로그램 이 가능한 데이터 처리기

• 단순히 입력에 의해서만 출력이 결정되는 것이 아니라
  입력+프로그램에 의해서 출력이 결정되는것

🐣 프로그램

• 컴퓨터가 데이터를 어떻게 처리할지를 알려주는 일련의 명령어 집합
• 처리 가능한 작업의 유형과 연산의 집합

1. 어떤 작업/연산을 처리할 수 있고 어떤 연산을 처리할 수 없는것을 결정함
2. 컴퓨터 : 특수 목적의 작업을 처리하는 기계가 아니라
   다양한 형태의 작업을 수행할 수 있는 범용의 기계

🐣 프로그래밍 과정의 결과물

1. 문제의 해결 방법과 절차를 찾는다 = "알고리즘"
2. 그것(알고리즘)을 적절한 프로그래밍 언어를 사용해서
   컴퓨터가 이해할 수 있는 형태로 표현한다

🐣 폰 노이만 모델의 주요 개념

• 폰 노이만 모델 : 컴퓨터 내부 구조와 처리 과정을 정의한 모델

1. 내장 프로그램

• 실행될 프로그램은 메모리에 저장되어야 한다
  🌠 처리될 데이터와 처리를 담당할 프로그램은 메모리에 있어야 한다는 것은
  프로그램과 데이터가 동일한 형식으로 메모리에 표현된다는 뜻(비트 패턴)

2. 프로그램은 유한개의 명령어의 나열이다

• 미리 정의된 기본 명령어의 유한개의 조합으로 구성
• 메모리에서 한번에 하나씩 명령어를 가져와 해석/실행 한다
  🌠 그로 인해서 명령어의 재사용

🐣 데이터

• 모든 데이터는 유형(숫자,문자,오디오,비디오)에 관계 없이 비트 패턴으로 표현
• 메모리에는 단순하게 데이터만 저장하는 형태이므로 이게 무슨 데이터인지
  어떤 유형인지는 표기하지 않으므로 해석과 처리를 입출력 장치나 프로그램이 책임진다

• 비트 패턴 : 0과 1의 나열된 형태
• 🌠 폰 노이만 모델에서는 실제 데이터가 어떻게 표현되고 저장돼야 한다는 것에 대해서는 정의하고 있지 않다! 그러므로 데이터 입출력을 위해서는 적절한 형태로의 변환이 필요
  ( 데이터를 컴퓨터가 이해할수 있게 변환 or
  처리한 결과가 사람이 이해할 수 있게 변환 )

❓자료 구조

• 자료 사이의 논리적 관계를 컴퓨터나 프로그램이 보다 쉽게 이해하고 다룰 수 있도록 구성한 것
• 추상화를 통해 자료의 논리적 관계를 구조화한 것
  🐣 실제로 프로그램에서 사용될 데이터들을 얼마나 잘 정리해 놓은것인가!
• 자료(데이터)의 추상화 : 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 데이터를 구조에 대해서 공통의 특징만 뽑아 정의한 것

자료의 추상화나 구조화가 적절히 이루어지지 못하면 소프트웨어는
1. 비효율적으로 개발되거나
2. 비효율적으로 수행되거나
3. 소프트웨어의 확장성에 문제가 생기거나
4. 소프트웨어의 유지보수에 문제가 생길 수 있음

🌈 배열

• 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수로 묶어놓은 데이터의 집합체이며, 각 원소를 구분하기 위해 인덱스(첨자)와 데이터 값의 쌍으로 이루어짐
• 배열의 원소들은 컴퓨터 메모리에 연속적인 기억장소에 저장되어 순차적으로 저장되기 때문에 배열의 시작주소와 각 자료형의 크기를 알면 직접 접근이 가능함
• 다차원 배열이 저장되는 방식으로는 열 우선 순서와 행 우선 순서가 있음

🌈 연결 리스트

노드들을 연결하여 구성하는 것으로, 한 노드는 데이터 필드와 링크 필드로 구성됨

• 단일 연결 리스트 : 링크 필드가 하나이고, 한 방향으로만 검색이 가능함
• 이중 연결 리스트 : 2개의 링크 필드를 사용해서 양방향(선행 노드 방향, 후행 노드 방향)의 검색이 가능함 (메모리를 좀 더 많이 차지하지만 성능이 빠름)
• 원형 연결 리스트 : 마지막 노드의 링크 필드가 첫 번째 노드에 연결되어, 한 방향이지만
  전체 연결 리스트를 원형으로 연결함

🌈 스택

• 리스트의 한쪽 끝에서만 삽입과 삭제가 이루어지는 후입선출(LIFO) 구조
• pop연산(삭제)과 push 연산(삽입)이 가장 중요한 연산임

🐣 스택 오브플로
삽입 연산 시 발생, 스택을 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상
🐣 스택 언더플로
삭제 연산 시 발생, 스택에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

🌈 큐

• 리스트의 한쪽 끝에서는 삽입, 다른 한쪽 끝에서는 삭제가 이루어지는 선입선출(FIFO) 구조
• insert 연산과 delete 연산이 가장 중요한 연산임

🐣 오버플로
큐의 크기를 기본적으로 한계를 짓는 경우가 많기 때문에 오버플로우 발생한다
삽입 연산 시 발생, 큐를 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상
🐣 언더플로
삭제 연산 시 발생, 큐에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

큐의 만원상태
큐의 삽입 연산을 수행할 수 없는 상태

왜 삽입연산이 안되는가❓

큐의 만원상태는 큐의 rear 포인터가 큐의 마지막 항목을 가리키는 경우 발생한다
이 경우 큐에 새로운 항목을 삽입하려면 rear 포인터를 다음 항목으로 이동해야 하는데
더 이상 이동할 수 있는 항목이 없기 때문이다

따라서 큐의 만원상태는 🌠큐의 모든 항목이 가득차 있다는 것이 아니라
큐에 새로운 항목을 삽입할 수 있는 공간이 없다는 것을 의미한다

🌈 트리 : 노드와 가지로 구성되어 나무 뿌리 모양의 데이터의 [ 계층 관계 ]를 나타내는 자료구조

• 노드 : 정보 항목을 의미
• 루트 : 빈 트리가 아닌 경우에 맨 꼭대기에 있는 하나의 노드
• 차수 : 각 노드에 있는 가지의 수
• 레벨 : 루트 노드로부터의 거리 (가지의 수) 를 의미 함
• 트리의 깊이(depth)/높이(height) : 루트 노드로부터 가장 긴 경로에 있는 단말 노드의 레벨에 1의 값을 더한 것

• 트리(tree) : 데이터간의 관계를 나타내는 비선형 자료구조로서 노드(node)라고 불리는 부분과 노드를 연결하는 가지(branch, edge)로 구분됨
• 잎 노드(leaf node) : 단말 노드(terminal node)라고도 하며, 노드의 차수가 0인 노드
• 내부 노드(internal node) : 비단말 노드(non-terminal node)라고도 하며, 루트 노드와 단말 노드를 제외한 나머지 노드

• 이진트리 (binary tree) : 트리 중에서 차수가 2인 트리를 의미하고, 모든 노드의 차수는 최대 2를 넘지 않으며 모든 노드는 최대 2개의 서브 트리를 가짐

  • 포화 이진트리
    이진트리 중에서도 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 개수(-1)를 가진 이진트리 (각레벨의 노드가 빈 자리가 없는것)
  • 완전 이진트리
    총 노드의 개수가 (-1)을 초과하지 않으면서 포화이진트리의 번호와 일치하는
    이진트리 (왼쪽에서 오른쪽으로 채워지는 트리)(완전 이진트리 안에 포화 이진트리가 있다)
  • 경사 이진트리
    한쪽 방향으로 치우친 트리 이 때 높이가 최대가 된다

• 🌠 이진트리의 순회 : 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 것
  🐣 트리 순회 방법으로 전위 순회, 중위 순회, 후위 순회가 있음
  1. 전위 순회 DLR : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
  2. 중위 순회 LDR : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
  3. 후위 순회 LRD : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

🌈 그래프 : 정점들의 유한 집합과 정점들의 쌍을 연결하는 간선의 유한집합

• 그래프(graph) : 정점(vertex)들의 유한 집합 V와 두 개의 정점을 연결하는 간선(edge)들의
  유한 집합 E로 정의되며, G=(V,E)로 표시됨
• 무방향 그래프(undirected graph) : 간선이 방향성이 없는 간선으로 연결된 그래프
• 방향 그래프(directed graph, digraph) : 두 정점을 연결하는 간선이 방향성을 가지는 간선으로 연결된 그래프

• 두 정점이 간선으로 직접 연결되어 있으면 인접해 있다고 하며 해당 간선은 두 정점에 부수되었다고 한다
  🐣인접 : 정점 간의 관계
  🐣부수되었다 : 정점과 간선 간의 관계

• 그래프의 표현 : 인접행렬, 인접 리스트
• 그래프 순회 방식
  1. 깊이 우선 탐색 : 최근 방문하지 않은 인접한 하나의 정점을 우선적으로 방문함
  2. 너비 우선 탐색 : 최근 방문하지 않은 인접한 모든 정점을 모두 방문함

❓알고리즘

🌠 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고
간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것

• 이론적 관점에서 반드시 만족해야 할 조건

       1. 입출력 : 0개 이상의 외부 입력, 1개 이상의 출력
       2. 명확성 : 각 명령은 모호하지 않고 단순 명확해야 함
       3. 유한성 : 한정된 수의 단계를 거친 후에는 🌠반드시 종료해야 함
       4. 유효성 : 모든 명령은 컴퓨터에서 실행 가능해야 함    

• 실용적 관점에서의 추가 조건 : 효율성

🌈 알고리즘 설계

• 문제와 그에 따른 조건 등이 매우 다양하기 때문에 일반적이고 범용의 설계 기법은 없다
• 대표적인 설계 기법 : 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법

🐣 분할정복 방법 : 순환적으로 문제를 푸는 방식
문제를 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고,
분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는
하향식 접근 방법으로 각 순환 호출 시마다 분할 / 정복 / 결합의 세 단계를 거친다

특징 : 분할된 작은 문제는 서로 독립적이고 원래 문제와 동일하지만 입력 크기만 작아진 것이다

🌠 적용 가능한 문제 : 퀵 정렬, 합병 정렬, 이진 탐색

🐣 동적 프로그래밍 방법
문제의 크기가 가장 작은 소문제부터 해를 구해서 테이블에 저장해 놓고
이를 이용하여 입력 크기가 보다 큰 원래의 문제를 점진적으로 만들어가는 상향식 접근 방법

			🌀 테이블에 저장하는 이유 : 재사용하기 위해

🌠 적용 가능한 문제 : 모든 정점 간의 최단 경로를 구하는 플로이드 알고리즘

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

🌠 거스름돈 문제
고객에서 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
단순히 동전의 액면가가 가장 큰 동전부터 차례대로 최대한 거스름돈을 만든다

🌠 배낭 문제(물체를 쪼갤 수 있는 경우)
배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾는 문제
단위 무게당 이익이 가장 큰 물체부터 통째로 배낭에 넣고, 만약에 배낭의 남은 용량보다 물체의 무게가 큰 경우에는 물체를 쪼개서 배낭에 넣는다

🌈 알고리즘 분석

• 정확성 분석
  유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지를 수학적으로 증명

• 효율성 분석
  알고리즘 수행에 필요한 컴퓨터 자원, 즉 소요되는 메모리 공간의 크기
  (“공간 복잡도”)와 수행에 걸리는 시간(“시간 복잡도”)을 측정

• 시간 복잡도
  • 🌠 알고리즘의 수행 시간 : 알고리즘에서 수행되는 기본적인 연산의 수행횟수의 합
  • 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현
  • 입력 데이터의 상태에 따라 달라지며, 일반적으로 최악의 수행 시간을 사용

• 🌠 점근성능

  • 입력 크기 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(n^2) < O(n^3) < … < O(2^n)
  < 효율적 -------------------------------------------------------- 비효율적>

🌈 정렬 알고리즘

🐣 내부 정렬 vs 외부 정렬

• 내부 정렬
모든 데이터를 주기억장치에 적재한 후 정렬하는 방식

• 외부 정렬
모든 데이터를 주기억장치에 저장할 수 없는 경우, 일부 데이터만 주기억장치에 있고 나머지는 외부기억장치에 저장한 채 정렬하는 방식

🐣 비교 기반 정렬 vs 분포 기반 정렬

• 비교 기반 정렬
데이터의 키값을 직접 비교하여 정렬하는 방식
ex) 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬

• 분포 기반 정렬
데이터의 분포 정보를 사전에 얻어서 정렬에 이용하는 방법 (일반성은 떨어짐)
ex) 계수 정렬, 기수 정렬

🔅 선택 정렬 O(n^2)

• 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식
① 미정렬 부분의 데이터 중에서 가장 작은 값을 선택하고
② 선택된 값과 미정렬 부분의 첫 번째 데이터와 교환

• 데이터의 입력 상태에 민감하지 않고 언제나 동일한 수행 시간

🔅 버블 정렬

• 왼쪽에서부터 모든 인접한 두 데이터를 차례대로 비교하여 왼쪽의 값이 더 큰 경우에는 오른쪽 값과 자리바꿈을 통해 정렬하는 방법

• 🌀 데이터가 원하는 순서로 이미 정렬된 경우에는 O(n)을 갖고, 역순으로 정렬된 경우에는 최악의 수행 시간 O(n^2)을 가짐

• 데이터의 교환이 많이 발생하여 선택 정렬보다 비효율적

🔅 삽입 정렬

• 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은
데이터를 바른 위치에 삽입해서 나열하는 방식
미정렬 부분의 첫 번째 데이터를 꺼낸 후, 정렬된 부분에서 제자리를 찾아 삽입하는 과정을 반복

• 🌀주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로
정렬된 경우에는 최악의 수행 시간 O(n^2)을 가짐

🔅 퀵 정렬
특정 데이터를 기준으로 주어진 입력 배열을 두 개의 부분배열로 분할하고, 각 부분배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용하는 방법
🌀피벗이 제자리를 잡도록 해야함!
🌈 정렬하는 방식

• 분할정복을 적용한 알고리즘

• 피벗 : 두 개의 부분배열로 분할할 때 기준이 되는 데이터
(보통 배열의 첫 번째 원소를 피벗으로 지정)

• 분할 과정 O(n)
퀵 정렬의 가장 핵심 부분 피벗을 중심으로 두 부분배열로 분할하는 과정

• 최선의 수행 시간 O(nlogn)
피벗을 중심으로 동일한 크기의 두 개의 부분배열로 분할되는 경우

• 최악의 수행 시간 O(n^2)
🌀입력 데이터가 이미 정렬되어 있고
배열의 맨 왼쪽 원소를 피벗으로 사용하는 경우에는
피벗이 항상 최대값이나 최소값이 되기 때문에
피벗만 제자리를 잡고 나머지 모든 데이터가
하나의 부분배열로 분할되는 경우
🌀 피벗을 선택할 때 임의로 선택만 보장해되면 평균 수행 시간을 보일 가능성이 높음!!

• 평균 수행 시간 O(nlogn)
피벗 선택의 임의성만 확보되면 최악의 수행 시간이 아닌 평균 수행 시간이 보장됨

🔅 합병 정렬
동일한 크기의 두 개의 부분배열로 분할하고, 각 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병(merge)하여 하나의 정렬된 리스트를 형성하는 방식
• 분할정복을 적용한 알고리즘
• 합병 과정 : 정렬된 두 부분배열을 입력으로 받아 하나의 정렬된 배열로 만드는 과정
• 최선/평균/최악 수행 시간 → O(nlogn)

선택정렬 O(n^2) : 언제나 동일한 수행시간
버블정렬 O(n^2) : 입력 데이터 상태에 민감 최악=O(n^2), 최선 O(n)
삽입정렬 O(n^2) : 입력 데이터 상태에 민감 최악=O(n^2), 최선 O(n)

• 버블정렬은 선택정렬에 비해 데이터교환이 더 많이 발생하므로 비효율적

선택,버블,삽입의 개선된 정렬 방법 : 퀵,합병 O(nlongn)

🌈 탐색 알고리즘

🐣 순차 탐색과 이진 탐색

순차 탐색 O(n)

리스트 형태로 주어진 데이터를 처음부터 하나씩 차례대로 비교하여 원하는 값을 가진 데이터를 찾는 방법

• 모든 리스트(배열, 연결 리스트)에 적용 가능, 특히 데이터가 정렬되지 않은 경우에 적합

이진 탐색 O(logn)

정렬된 입력 배열 에 대해서 주어진 데이터를 절반씩 줄여가면서 원하는 데이터를 찾는 방법

• 분할정복을 적용한 알고리즘

• 주어진 배열의 가운데 데이터의 값과 탐색키를 비교
① ‘탐색키 = 배열의 가운데 값’이면 탐색 성공
② ‘탐색키 < 배열의 가운데 값’이면 주어진 배열의 전반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출
③ ‘탐색키 > 배열의 가운데 값’이면 주어진 배열의 후반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출
🌀탐색을 한 번 수행할 때마다 탐색 대상이 되는 원소의 개수가 절반씩 감소

• 항상 정렬 상태 유지를 위한 데이터 이동으로 인해 오버헤드 발생
빈번한 삽입/삭제가 있는 응용에는 부적합

🐣 이진 탐색 트리 (이진탐색에서 삽입/삭제 문제를 보완)

• 이진 탐색 트리
  각 노드 x의 왼쪽 서브트리의 모든 키값은 x의 키값보다 작고
  오른쪽 서브트리의 모든 키값은 x의 키값보다 크다는 조건을
  만족시키는 이진 트리

• 탐색 연산
  루트 노드로부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 원하는 키값을 갖는 원소를 찾음

• 삽입 연산
  삽입할 원소를 탐색한 후, 탐색이 실패한 지점의 왼쪽/오른쪽 자식 노드를 생성하여 추가 탐색 성공 시 삽입 없이 종료

• 삭제 연산
  삭제되는 자식 노드의 개수에 따라 3가지 경우로 구분해서 처리

  • 자식 노드가 없는 경우
  남은 노드의 위치 조절이 불필요

  • 자식 노드가 하나인 경우
  자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다

  • 자식 노드가 두 개 모두 있는 경우: 후속자 노드(어떤 노드의 바로 다음 키값을 갖는 노드)를 삭제되는 노드의 위치로 올리고, 후속자 노드의 자식 노드의 개수에 따라 다시 삭제 연산을 처리

• 성능
  • 평균 탐색 시간 O(logn) : 리프 노드를 제외한 모든 노드의 차수가 2인 경우
  • 최악 탐색 시간 O(n) : 경사 이진 트리, 즉 리프 노드를 제외한 모든 노드의 차수가 1인 경우

❓운영체제

🐣 운영체제의 주요 기능(자원의 범주)

프로세서 관리자 / 주기억장치 관리자 / 장치 관리자 / 파일 관리자

🌈 운영체제의 작업 처리 방법 (전체적인 작업/프로세스 에서의 운영체제의 역할)

• 일괄처리 시스템
  처리할 작업이 발생할 때마다 즉각적으로 처리하지 않고 처리해야할 작업이 일정량에 도달할 때까지 여러 작업을 모아 놓고 작업을 한꺼번에 처리하는 방식

• 다중프로그래밍 시스템
  여러 개의 프로그램을 효율적으로 실행시키기 위해 여러 개의
  프로그램들이 컴퓨터 자원이 쉬는 시간에 서로 양보하며 사용하는 방식
  

• 🌠 시분할 처리 시스템
  CPU의 시간을 일정 간격의 작은 시간으로 쪼개서 각 사용자에게 시간 간격이
  할당되고, 그동안 직접 컴퓨터와 대화식으로 작업을 수행하는 방식

🐣 기억장치의 계층 구조

• 컴퓨터 시스템에서 사용되는 기억장치는 접근속도,비용 및 장치의 용량에
  따라 계층적으로 구성

🌀CPU가 일할 수 있게 보조기억장치 -> 주기억장치 -> 캐시기억장치 -> 레지스터 순서로 올라간다
🌀CPU 내에는 여러 레지스터가 존재하며 CPU에 직접 내장되어 있기 때문에 기억장치 중에서 가장 빠른 처리 속도를 제공한다!!!

🌈 주기억장치 할당 방법 (기억장치를 할당할 때 운영체제의 역할)

• 단일 사용자 연속 기억장치 할당 (옛날방법)
  하나의 사용자 프로그램만이 전체 주기억장치에 할당되는 방식

  단점

  • 하나의 프로그램이 모든 기억장치,주변장치 및 CPU 등을 할당받아 사용하기 때문에 유휴 자원에 대한 낭비가 심하고 다른 프로그램들은 기다려야 하므로 대기시간이 길어짐
  • 프로그램의 크기가 주기억 장치의 크기를 벗어나면 실행시킬 수 없는 단점을 보완하기 위해 🌀오버레이 기법이 사용됨

• 고정 분할 다중 프로그래밍 기법
  🌀한 번에 하나의 프로그램만 실행시킬 수 있는 문제점을 보완!
  다중 프로그래밍 시스템(여러 개의 프로그램이 실행되는 시스템) 에서 주기억장치를 여러 개의 고정된 크기의 영역으로 분할하고, 실행 중인 여러 개의 프로세스에게 각각 할당하는 방식

• 동적 분할 프로그래밍 기법 [ 통합 / 집약 ]
  프로그램이 주기억장치에 적재될 때마다 모든 작업이 필요로 하는 크기(고정된 크기가 아니라 다양한 크기)만큼 연속된 공간을 할당해주는 방식

고정 분할 / 동적 분할 에서 분할되는 것는 주기억장치 이다

🐣 가상기억장치 관리 기법

❓가상 기억장치란
주기억장치에서 이용 가능한 영역보다 큰 프로그램을 작은 단위로 쪼개어 실행 시키기 위해 보조기억장치의 주소를 🌀주기억장치의 주소로 변환
하여 프로그램에게 제공되는 가상의 기억장치를 말함

• 페이징 기법
  보조기억장치로부터 프로그램 코드나 데이터를 페이지(page)라고 불리는 동일한 크기의 블록으로 쪼개어서 주기억장치에 적재하여 접근하는 방식

• 세그먼테이션 기법
  세그먼테이션 기법은 프로그램 코드나 데이터를 일정하지 않은 서로 다른
  크기로 분할하여 주기억장치에 적재하여 접근하는 방식

❓프로세스

실행 상태에 있는 프로그램
프로세스의 상태 : 생성, 준비, 실행, 대기, 종료

운영체제가 프로세스를 관리하기 위해서는 프로세스의 정보를 알고있어야 하는데
이를 PCB (Process Control Block) 이라고 한다
메모리와 CPU에 자원 할당을 주었다 회수했다 하면서 관리 한다

🐣 중앙처리장치 스케줄링 기법

프로세스 스케줄링의 2가지 분류

🌈선점 스케줄링 기법
이미 중앙처리장치를 점유하여 실행중인 프로세스를 내보내고
다른 프로세스에게 중앙처리장치에 할당하는 스케줄링 기법이다

🌈비선점 스케줄링 기법
일단 프로세스에 중앙처리장치가 할당되어 프로세스의 실행이 시작되면
프로세스가 종료될 때까지 중앙처리장치의 다른 프로세스에게 양보하지 않는 기법이다

짧은 작업이 긴 작업으로 인해 기다리게 되는 경우가 있지만 모든 프로세스 관리가 공평
우선순위에 관계없이 대기중인 작업에는 변동이 없으므로 응답시간을 예측할 수 있다는 장점

1. 기한부 스케줄링
   기한부 스케줄링은 기한이 되면 중앙처리장치를 양보하는 방식

2. 우선순위 스케줄링
   우선순위가 높은 프로세스부터 먼저 처리하는 방식

   우선순위는 중앙처리장치 관리자(운영체제)에 의해 결정됨

3. FCFS 스케줄링(비선점)
   준비 큐에 도착한 순서대로 중앙처리장치를 할당받는 방식

4. SJF 스케줄링(비선점)
   현재 준비 큐에 있는 프로세스들 중에서 수행시간이 가장 짧을 것으로 예상되는 프로세스를 먼저 처리하는 방식

   대기하는 프로세스의 수를 최소화할 수 있으므로 빠른 응답시간을 제공하지만
   수행시간이 긴 프로세스는 CPU를 할당 받지 못한 채 계속 기다려야 한다는 단점도 있음

5. 🌠RR 스케줄링(선점)
   프로세스가 도착한 순서대로 CPU가 할당되지만
   CPU의 시간 할당량 또는 시간 간격에 의해 제한하는 방식

   시간 할당량을 모든 프로세스에게 동일하게 주고
   그 시간동안 완료되지 못한 프로세스는 준비 큐의
   맨 뒤에 배치되고 준비 중인 다음 프로세스에게 중앙처리장치를 할당함

🌀교착상태
2개 이상의 프로세스가 대기 중인 프로세스들 중의 하나에 의해서만 발생할 수 있는
자원의 획득이나 해제를 무작정 기다리고 있는 상태

• 교착 상태의 필수 조건 : 상호배제 , 대기 , 비선점 , 환형 대기
• 교착 상태 처리 방법 : 교착상태의 방지, 교착상태의 회피, 교착상태의 탐지, 교착상태의 복구

🐣 디스크 스케줄링 기법

• FCFS(First-Come First Served) 스케줄링 기법
  먼저 도착한 디스크 접근 요청이 가장 먼저 서비스를 받는 방법

• SSTF(Shortest Seek Time First) 스케줄링 기법
  현재 디스크 헤드의 위치에서 가장 짧은 트랙 탐색 거리(또는 탐색 시간)를 가진
  디스크 접근 요청을 먼저 처리하는 방식

• 🌠SCAN 스케줄링 기법 (엘레베이터 기법)
  한쪽 방향에서 가장 짧은 탐색거리의 디스크 접근 요청을 먼저 서비스하는 방식

• SLTF(Shortest Latency Time First) 스케줄링 기법
  디스크 헤드가 특정 실린더에 도착하면 그 실린더 내의 모든 요구를 검사한 후 가장 짧은 회전지연을 갖는 요구들에게 우선적으로 서비스하는 방식

파일 구조 : 파일을 구성하는 레코드들이 보조기억장치에서의 배치 방법

🐣 디스크 공간 할당 방식

• 연속 할당(contiguous allocation) 기법 (순차파일과 찰떡궁합)
  파일이 보조기억장치에 저장될 때 연속된 물리적 공간을 할당받는 기법
• 불연속 할당(noncontiguous allocation) 기법 (직접파일과 찰떡궁합)
  파일을 작은 단위로 나누고, 보조기억장치의 불연속적인 공간을 나누어 할당받는 기법

  🌀섹터단위 불연속 할당 기법
  파일을 더 확장할 필요가 생기면 추가 섹터를 할당 받아 연결 리스트에 추가
  🌀블록단위 불연속 할당 기법
  개별적인 섹터를 할당하는 대신에 연속된 섹터로 구성된 블록을 이용함

❓불 대수와 논리 게이트

🐣 컴퓨터 하드웨어의 기본 구성요소 : 중앙처리장치, 기억장치, 입력장치, 출력장치
• 중앙처리장치 = 처리장치(제어장치 + 산술논리연산장치) + 레지스터
• 시스템 버스 = 주소 버스 + 데이터 버스 + 제어 버스

1. 주소 버스
   CPU가 기억장치나 입출력장치의 주소 정보를 전송하는 신호선의 집합
   버스의 폭이 시스템의 메모리 용량을 결정
   단방향 버스

2. 데이터 버스
   CPU와 기억장치/입출력장치 사이에 데이터를 전송하기 위한 신호선의 집합
   버스의 폭은 전송할 수 있는 비트의 수(워드)를 의미
   양방향 버스

3. 제어 버스
   CPU가 각종 장치의 동작을 제어하기 위한 다양한 신호들의 통로
   버스의 폭은 제어의 신호수를 나타내고 CPU나 시스템의 구성에 따라 달라짐
   양방향 버스

🐣 불대수 : 이진 변수의 논리연산을 나타내는 대수

• 기본 논리연산 : 논리곱(AND), 논리합(OR), 논리부정(NOT)

• 복합 논리연산 : NAND, NOR, XOR

🐣 논리 게이트 : 논리연산을 하드웨어로 구현한 것으로, 논리회로를 구성하는 기본 소자

• 논리 게이트의 완전집합 : 원하는 임의의 회로를 구성할 수 있는 게이트들의 부분집합

• 불 대수의 법칙들을 사용하여 불 함수를 간소화하면 논리 게이트의 수를 줄일 수 있으므로
동일한 기능을 수행하는 보다 단순한 형태의 회로 구성이 가능

🌈 논리회로

• 조합회로
  논리 게이트로만 구성되어 출력값이 단순히 입력값의 조합으로만 결정되는 회로

  • 종류 : 전가산기, 디코더, 멀티플렉서 등

  (1비트) 전가산기
  두 개의 입력 비트와 바로 아랫자리에서 올라오는 올림수까지 입력으로 받아 덧셈을 수행하는 회로(세 개의 입력과 두 개의 출력으로 구성)
  n비트 전가산기는 1비트 전가산기를 직렬로 연결시켜 구성

  디코더
  n비트의 이진 코드를 최대 2n개의 서로 다른 정보로 변환해 주는 장치
  주소방식으로 주어진 입력으로부터 각각의 하드웨어 구성요소를 개별적으로 구동하기 위해 주로 사용

  멀티플렉서
  2n개의 입력선 중에서 하나를 선택하여 단일의 출력으로 내보내는 회로
  어떤 장치로부터 들어오는 데이터가 버스를 사용할 것인가를 정할 때 사용

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

  • 플립플롭 : 1비트의 이진 정보를 저장할 수 있는 장치 → 종류: RS 플립플롭, T 플립플롭 등

  • 종류 : 카운터, 레지스터

  카운터 : 클록펄스가 입력될 때마다 저장된 이진수가 1씩 증가하는 장치

🌈 기억장치

• ROM : 한 개의 디코더와 여러 개의 OR 게이트를 사용한 조합회로로 구성 가능
• RAM
  • 1비트 RAM 소자 : 1개의 RS 플립플롭, 3개의 AND 게이트, 2개의 NOT 게이트로 구성
  • RAM은 1비트 RAM 소자, 디코더, OR 게이트를 사용한 순차회로로 구성 가능 하지만,
  실제로는 플립플롭이 아닌 축전지로 구현된 DRAM 사용

🌠 기억장치의 계층 구조
• 접근 속도와 저장 용량에 따른 기억장치의 구분
CPU가 데이터에 접근함에 있어서 가장 적은 비용으로
가장 높은 성능을 얻기 위해 참조의 지역성에 기반을 둔 전략

참조의 지역성

• 공간적 지역성
  다음 순간에 접근할 위치는 현재의 접근 위치와 근접해 있을 가능성이 큼!
• 시간적 지역성
  최근에 접근한 위치들이 가까운 미래에 다시 접근할 가능성이 큼!

레지스터 : CPU 내부에 존재하여 각종 연산에 직접적으로 사용
캐시기억장치 : CPU와 주기억장치 간의 속도 차이를 줄여 주는 역할
주기억장치 : 현재 수행 중인 프로그램과 데이터를 저장

ㅡㅡㅡㅡㅡㅡㅡㅡㅡ 까지 CPU가 직접 접근 가능

보조기억장치 (주기억장치로 적재되어야 CPU가 접근 가능)

명령어

• 명령어 집합 : 컴퓨터 시스템 내에 정의된 기본적인 명령어들의 집합

  • 명령어 집합이 정의되면 그에 상응하는 하드웨어 구조가 결정됨 → CISC, RISC

• 명령어 형식 : 연산자코드와 오퍼랜드로 구성

  • 오퍼랜드의 개수에 따른 구분
  3-주소 명령어, 2-주소 명령어, 1-주소 명령어, 0-주소 명령어

  • 명령어의 메모리 표현
  각 연산자에게 고유의 이진 패턴이 부여되고, 주기억장치의 주소와
  레지스터도 고유의 이진 패턴이 부여되며, 이런 연산자코드-오퍼랜드 쌍이 2진수의 나열의
  형태로 표현되어 주기억장치에 저장됨
  

• 주소지정방식 : 연산에 사용될 데이터가 기억장치의 어디에 위치하는지를 지정하는 방식

  • 종류
  즉시 주소지정방식
  직접 주소지정방식
  간접 주소지정방식
  레지스터 주소지정방식
  레지스터 간접 주소지정방식
  상대 주소지정방식(→인덱스된 주소지정방식, 베이스 레지스터 주소지정방식)

❓중앙처리장치

🐣 명령어 집합

컴퓨터 시스템 내에 미리 정의되어 있는 기본적인 명령어들의 집합
이런 집합에 따라서 컴퓨터의 구조가 달라진다 즉!
🌠 명령어의 종류, 명령어 형식, 주소지정방식 등을 고려해서 명령어 집합이 정의되면 상응하는 하드웨어 구조가 결정된다!

• 복합 명령어 집합 컴퓨터 (CISC)
  명령어를 많이 정의해서 프로그램에 사용되는 전체 명령어 수를 줄여서 프로그램 실행 시간 단축!

• 단축 명령어 집합 컴퓨터 (RISC)
  명령어를 단순화하고 개수를 줄여서 하드웨어를 개선시킨 구조

🌈 명령어의 종류

• 데이터 전송 명령어
  • 데이터 이동 (레지스터 -> 레지스터 / 주기억장치 -> 레지스터 / 기억장치 -> 기억장치 등)
    실제 데이터가 변경되는건 아니고 단지 ~ 에서 ~로 이동하는 것에 관련된 명령어
• 데이터 처리 명렁어
  • 산술 명령어, 논리연산 명령어, 비트 단위 명령어, 시프트 명령어 등 실제 연산과 관련된것!
• 프로그램 제어 명령어
  • 프로그램의 제어 흐름 관리 : 무조건적 분기 와 조건적 분기
• 입출력 명령어
  • 보조기억장치,IO장치 등과의 정보 교환 명령어 , 인터럽트 관련 명령어

    인터럽트 : 프로그램의 정상 수행을 잠시 멈추고 CPU 이외의 다른 장치의 요구 사항을 수행하는 기능!

🌈 명령어의 형식

각 명령어는 실행에 필요한 모든 정보를 포함해야 한다

연산자 코드 + 오퍼랜드

연산자 코드 : CPU가 처리할 연산의 종류 ( + , - , * , / ... )
연산자 코드에 할당된 비트 수 : CPU가 수행할 수 있는 명령의 최대 개수

오퍼랜드(피연산자) : 명령어가 사용할 데이터 또는 데이터가 저장되어 참조될 기억장치의 주소
🌠오퍼랜드의 개수는 컴퓨터의 구조에 따라 달라짐

명령어의 형식은 오퍼랜드가 어디에 저장되는지 또는 오퍼랜드의 개수에 따라서 구분할 수 있다!!

• 오퍼랜드 개수에 따른 구분
  • 3-주소 명령어
    [ 연산자 코드 + 오퍼랜드 + 오퍼랜드 + 오퍼랜드 ]
  • 2-주소 명령어
    [ 연산자 코드 + 오퍼랜드 + 오퍼랜드 ]
    가장 많이 사용되는 형식
  • 1-주소 명령어
    [ 연산자 코드 + 오퍼랜드 ]
    누산기(AC)를 사용하게 됨
  • 0-주소 명령어
    [ 연산자 코드 ]
    스택 사용

🌈 주소지정방식

연산에 사용될 데이터가 기억장치의 어디에 위치하는 지를 지정하는 방법

유효주소 : 주소지정방식에 의해 계산되어 실제 데이터가 저장된 주소

즉시 주소지정방식 (왕왕왕왕빠름)

[ 연산자코드 + 오퍼랜드(실제 데이터) ]

• 오퍼랜드값이 실제데이터 값이여서 읽어오면 바로 사용 가능하기에 가장 빠르다
• 메모리에 접근하지 않아도 된다
• 오퍼랜드의 크기에 의해서 실제 사용될 데이터의 크기가 제한을 받는다
• 레지스터/변수 초기화에 유용

레지스터 주소지정방식 (왕왕왕빠름)

[ 연산자코드 + 오퍼랜드(레지스터 번호) ]

• 레지스터 번호에 가면 실제 데이터가 저장되어 있음

직접 주소지정방식 (왕왕빠름)

[ 연산자코드 + 오퍼랜드(주기억장치 주소) ]

• 오퍼랜드에 주기억장치 주소가 적혀져 있고 이것이 유효주소이다

상대 주소지정방식 (왕빠름)

[ 연산자코드 + 오퍼랜드(내용) ]

• 내용과 + 레지스터에 있는 내용을 더해서 나온 값이 유효주소 이므로
  주기억장치 주소로 가면 실제 데이터가 있다

간접 주소지정방식 (빠름)

[ 연산자코드 + 오퍼랜드(주기억장치 주소) ]

• 메모리주소에 가도 실제 데이터가 저장되어 있는게 아니라 또 주기억장치의 주소가 있으므로
  실제 데이터에 접근하기 위해서는 주기억장치를 2번 접근해야 함

🐣 명령어의 구현 방법

• 마이크로프로그램에 의한 제어장치
연산과 명령어 수행 순서 조작 회로가 제어기억장치에 저장된
마이크로연산(비트패턴)으로 기동하는 장치
각 명령어는 여러 개의 마이크로 연산으로 구현
명령어 세트의 변경이나 추가가 용이
CISC 컴퓨터 구조에서 주로 사용

• 직접 회로로 구성된 제어장치
연산과 명령어 수행 회로가 직접 구성된 제어회로에 의해 기동하는 장치

🐣 레지스터

범용 레지스터와 특수 레지스터로 구분

🌈 특수 레지스터의 종류

• 누산기(AC)
  데이터나 연산 결과를 일시적으로 저장하는 레지스터
• 기억장치 버퍼 레지스터(MBR)
  기억장치에 저장될 또는 기억장치에서 읽어온 데이터를 임시로 저장
• 기억장치 주소 레지스터(MAR)
  현재 PC(프로그램 카운터)의 내용을 시스템 버스의 주소 버스로 출력되기 전에 일시적으로 저장
• 프로그램 카운터(PC)
  다음에 수행될 명령어가 저장되어 있는 기억장소를 가지고 있는 레지스터
• 명령어 레지스터(IR)
  주기억장치에서 인출되어 현재 실행 중인 명령어를 저장

🐣 처리장치

연산장치(ALU) + 레지스터

• 수행되는 모든 연산의 기능은 비트 패턴으로 이루어진 마이크로연산으로 구현
• 각 마이크로연산은 처리장치 내의 각종 논리회로와 연결되어 하드웨어를 직접적으로 통제할 수 있는 제어단어로 일대일 매핑되어 있음

🐣 제어장치

• 기본 기능
① 처리장치를 구동해서 특정 연산을 수행한 후 처리장치 내의 레지스터 값을 갱신하고 연산 결과를 출력.
② 현재 명령을 수행한 후 다음에 수행할 명령의 주소정보를 생성

• 명령어 사이클 → 인출 – 해독 – 실행 – 저장

• 구성요소
PC, IR, 명령어 해독기, 주소결정회로, 제어기억장치, 제어기억장치 주소 레지스터, 제어기억장치 데이터 레지스터

❓입출력장치 및 병렬처리

• 입출력 시스템의 기본 구성요소
  • 입출력장치, 입출력장치 제어기, 입출력장치 인터페이스, 입출력 버스

• 입출력 제어 방식
  • CPU에 의한 방식
  입출력장치의 정보가 CPU를 통해 주기억장치에 쓰고 읽혀지는 방식
  프로그램에 의한 방식과 인터럽트에 의한 방식으로 구분 (가장 비효율적)

  • DMA 방식
  입출력장치가 주기억장치와 직접 연결되어 CPU는 두 장치 간의 초기 설정 및
  허가에만 관여하고 직접적인 정보의 이동은 장치 간에 DMA 제어기가 처리하는 방식

  • 채널 방식
  채널이라는 입출력 전용의 별도 프로세서를 사용하는 방식
  정보 전송 통로 제공 및 CPU와 같은 연산 작업도 수행 가능

• 병렬처리
  • 파이프라인 처리기
  프로그램 내에 내재하고 있는 시간적 병렬성을 활용
  하나의 연산을 서로 다른 기능을 가진 여러 개의 단계로 분할하여 각 단계가 동시에 서로 다른 데이터를 취급하도록 하여 처리 속도의 향상을 도모
  

❓프로그래밍 언어

프로그래밍 언어는

• 구문론적 측면에서 명확하게 정의되어야 하며
• 의미론적 측면에서 언제나 동일하게 해석되어야 한다

기계어 (Machine Language)

컴퓨터가 직접 이해할 수 있는 가장 기본적인 언어
0과 1로 구성된 이진 코드로 표현되며, 하드웨어가 직접 해석하여 실행

어셈블리어 (Assembly Language)

기계어보다는 사람이 이해하기 쉽게 만들어진 저수준 프로그래밍 언어
메모리 주소를 직접 다룰 수 있으며, 하드웨어와 매우 밀접한 관련이 있다

함수형 프로그래밍언어 (Functional Programming Language)

함수의 호출을 통해 프로그램의 상태를 변경하는 방식을 사용하는 언어
부작용(Side-effect) 없는 계산과 불변성(Immutability)을 강조
예) Lisp, Haskell

구조적프로그래밍언어 (Structured Programming Language)

순차, 선택, 반복 등의 제한된 제어구조를 사용하여 코드의 복잡성을 줄이는 방법론 GOTO문 등 복잡한 제어 흐름을 배제하고 명확한 입/출력을 갖는 모듈 단위로 분리하여 작성

논리형프로그래밍언어 (Logic Programming Language)

문제를 논리식으로 표현하고 그 식을 충족하는 해답을 찾아내는 방식으로 동작하는 언어예) Prolog가 대표적인 예시입니다.

객체지향프로그래밍언어 (Object-Oriented Programming Language)

데이터와 그 데이터에 관련된 연산들을 객체라는 단위로 묶고, 이 객체들간의 상호작용으로 프로그램 동작을 설명하는 패러다임

스크립트언어 (Scripting language)

보통 소스코드 형태로 배포되며, 주요 목적은 소스코드를 한 줄씩 읽으면서 즉시 실행하는 것
일반적으로 컴파일 과정이 없거나 간단하며, 작업을 자동화하거나 빠르게 프로토타이핑하는데 유용
예) Python, JavaScript

인터프리터 언어 (Interpreted Language)

인터프리터 언어는 프로그램을 한 줄씩 읽고 바로 실행하는 방식의 프로그래밍 언어
별도의 컴파일 과정 없이 소스 코드를 직접 실행하기 때문에 개발과 디버깅이 용이하다는 장점
그러나 컴파일 언어에 비해 실행 속도가 느린 경우가 많디
Python, Ruby, JavaScript

🌈 프로그램에서 🌀실행가능 코드로의 변환

• 어휘분석
  프로그램을 구성하는 문자들의 나열로부터 단어(token, 토큰)를 추출해 내는 과정
• 구문 분석
  어휘 분석의 결과로 나온 토큰들의 나열이 해당 프로그래밍 언어의 문법에 맞는지를 확인하는 과정
• 코드 생성
  구문 분석의 결과로 변수, 상수, 제어의 흐름 등이 결정되면 이러한 각각의 명령어를 어셈블리어로 풀어쓰거나 직접 기계어 이진 코드가 생성

🐣 프로그래밍 언어의 기본 공통 개념

대입문(할당문) : 변수나 기억장치 주소에 값을 저장하는 역할이며, l-value와 r-value로 구성됨

l-value : 값이 저장될 위치(기억장치(메인메모리)의 주소)
r-value : 저장할 값(정수,실수,문자열 ...)

🐣 변수형 검사

정적(static) 형 검사 방식 : 컴파일 과정에서 이루어 짐
동적(dynamic) 형 검사 방식 : 프로그램 실행(run-time) 중에 이루어 짐

코드블럭내에 선언된 변수나 객체는 기억장소(메모리)를 할당받았다고 생각하면 됨!
코드블럭이 끝나면 지역변수는 기억장소에서 삭제됨

🐣 함수와 프로시저

기능적으로는 유사하다

• 함수 : 함수의 코드 부분의 실행 결과값을 돌려줌 (return)
• 프로시저 : 실행 결과값을 돌려주지 않음

C, C++ 같은 언어에서는 함수와 프로시저의 구분없이 모두 함수로 취급!
요즘 트랜드는 구분없이 사용!

🐣 매개변수

호출하는 프로그램에서 함수를 호출하기 위해 사용되는 매개변수를 실매개변수
호출되는 함수의 정의에 사용되는 매개변수를 형식매개변수 라고 한다

🐣 함수의 매개변수 전달 방식

• 값 호출 방식
  C언어에서 함수 호출의 실매개변수를 전달할 때 매개변수 주소를 전달하는 것이 아니고
  실매개변수의 값만을 형식매개변수에 복사하는 방식!

• 참조 호출 방식
  실매개변수가 형식매개변수 자리를 취해서 함수 안에서 형식매개변수에 행해진 모든 조작이 그대로 실매개변수에 반영되는 방식!

🐣 변수의 수명

변수의 값을 저장하기 위해 기억장소를 할당받고 해제될 때까지의 시간

• 자동 할당 방식
  한 변수가 선언된 블록이 시작할 때 변수는 기억장소를 할당받고 블록이 끝나면 변수의 기억장소는 자동적으로 회수됨
  🌀 자동 할당 방식에서 변수의 수명은 그 변수가 포함된 블록의 범위와 같음
• 정적 할당 방식
  프로그램이 시작될 때 기억장소가 할당되며 블록이 끝나더라도 기억 장소는 그대로 유지되고 프로그램 종료 시 회수됨
• 프로그래머 지정 할당 방식
  프로그램의 실행 도중에 프로그래머가 기억장소를 요청하여 할당받고 프로그래머가 직접 할당받은 기억 장소를 해제하여 운영체제에게 기억 장소를 회수시킬 때까지 기억장소가 유지됨

❓관계형 모델

🌈 주요 용어

• 릴레이션 : 테이블
• 속성 : 컬럼, 열, 필드, 데이터항목, 릴레이션의 스키마
• 투플 : 행,레코드, 릴레이션의 인스턴스
• 차수 : 속성의 개수
• 영역(도메인) : 속성이 가질 수 있는 모든 값의 집합
• 카디널리티 : 투플의 개수

  릴레이션 = 릴레이션 스키마 + 릴레이션 인스턴스

  릴레이션 스키마
  릴레이션의 논리적 구조를 나타냄, 이름과 속성으로 구성
  시간에 무관하며, 속성의 타입을 지정

  릴레이션 인스턴스
  어느 한 시점에 릴레이션이 가지고 있는 투플의 집합
  삽입, 삭제, 갱신 등을 통해 시간에 따라 변하는 릴레이션의 값

🌈 키

각 투플에 접근할 때 유일하게 구분되는 속성의 집합
1. 슈퍼키 : 유일성을 만족하는 속성 똔느 속성의 집합
2. 후보키 : 슈퍼키 중에서 최소성을 만족하는 것
3. 기본키 : 후보키 중에서 기본적으로 사용할 키로 선택된것
4. 대체키 : 후보키 중에서 기본키로 선택되지 않는것

5. 외래키
   다른 릴레이션의 기본키를 그대로 참조하는 속성 또는 속성의 집합
   관련 있는 릴레이션 사이에서 데이터의 일관성을 유지하는 수단

🌈 데이터베이스 설계

사용자 요구 조건에서부터 데이터베이스 구조를 도출해 내는 과정

(요구 조건 분석 → 개념적 설계 → 논리적 설계 → 물리적 설계 → 구현)

• 요구 조건 분석 : 데이터 및 처리 요구 조건 분석
• 개념적 설계 : DBMS에 독립적인 개념 스키마 설계, 트랜잭션 모델링
• 논리적 설계 : 목표 DBMS에 맞는 스키마 설계, 트랜잭션 인터페이스 설계
• 물리적 설계 : 목표 DBMS에 맞는 물리적 구조 설계, 트랜잭션 세부 설계
• 구현 : 목표 DBMS DDL로 스키마 작성, 트랜잭션 작성

논리적 모델링 : 개념적 구조를 목표 DBMS의 구조로 변환하는 과정

• E-R 다이어그램으로부터 관계형 데이터 모델로 변환하는 과정
  ① 사각형의 개체 타입은 개체 릴레이션으로 변환
  (개체 타입의 속성은 해당 개체 릴레이션의 속성으로 포함)
  ② 마름모의 관계 타입은 관계 릴레이션으로 변환
  (연관된 개체 타입의 키속성을 관계 릴레이션의 속성으로 포함, 관계에 속한 속성은 관계 릴레이션의 속성으로 포함)

❓네트워크

🐣네트워크의 구성 요소

• 채널(channel)
  모든 통신은 전선, 전화선, 광케이블, 무선 링크 등 통신 매체를 통해서 통신 신호가 전달된다. 통신 신호가 실제로 전달되는 통로
• 주파수(frequency)
  통신채널을 통해 전달되는 통신 신호는 디지털/아날로그 모두 주기성을 가지는 파형의 모습을 가지고 있는데, 이 통신 신호가 초당 몇 번 진동하는가를 계산한 것
• 노드(node)
  네트워크에 연결된 컴퓨터나 관련 장비
• 프로토콜(protocol)
  🌠통신 프로토콜은 컴퓨터 통신을 위해 통신을 하는 노드간의 합의된 통신 약속
• 네트워크 인터페이스(network interface)
  컴퓨터와 네트워크를 연결해주는 장치
  컴퓨터 내부의 신호를 물리적/전기적 신호로 변환
• 대역폭(bandwidth)
  최대 주파수에서 최소 주파수 사이의 주파수 대역

  🌀 최대 주파수가 높으면 같은 단위 시간에 데이터를 많이보낼 수 있지만 멀리 보내지 못함
  🌀 노드가 될 수 있는것 : 라우터, 일반 컴퓨터, 스마트폰, WIFI 중계기

🐣 네트워크 망

네트워크 망이 구분되는 3가지 방식
1. 컴퓨터 네트워크의 크기 : 근거리(방,빌딩), 도시권(도시), 광역통신(국가,대륙)
2. 네트워크의 연결 형태
3. 메세지 교환 방식

컴퓨터 네트워크의 연결 형태

• 버스(bus)형 컴퓨터 네트워크
  버스형의 경우 컴퓨터들이 하나의 버스(기본적으로 대역폭이 넓은 채널)를 공유하면서
  메시지 송신시 버스에 방송하듯 버스에 연결된 모든 컴퓨터에 메시지를 보내는 형태
• 성(star)형 컴퓨터 네트워크
  중앙에 있는 컴퓨터가 모든 메시지의 중계자 역할을 하며
  모든 메시지는 먼저 중앙의 컴퓨터로 보내지고
  중앙의 컴퓨터가 수신한 메시지를 다양한 목적지 컴퓨터에 전달되는 형태
• 원(ring)형 컴퓨터 네트워크
  원형 컴퓨터 네트워크는 메시지가 원형 네트워크를 돌면서 차례로 다음 컴퓨터로 전달되어
  최종 수신 컴퓨터에 도달할 때까지 계속 전달되는 형태

🌠메시지 교환(switching) 방식

• 회선 교환 방식(circuit switching) - 옛날 전화기지국 있던 시절
  메시지의 송신 컴퓨터에서 수신 컴퓨터까지 여러 개의 스위치를 통해
  물리적으로 연결된 임시 전용 회선을 동적으로 구성한 후
  임시적으로 설정된 회선을 통해서 메시지를 주고받는 방식
• 🌈 메시지 교환 방식(message switching)
  송신하려는 메시지 전체를 한 단계씩 목적지 방향으로
  스위치(또는 컴퓨터, 라우터 등)를 거쳐서 전송하는 방식

  한 번에 많은양의 메세지가 몰려오면
  대기행렬(Queue)을 두어서 저장했다가 수신한 순서대로 전달함

  🌈 패킷 교환 방식(packet switching)
  메시지를 패킷(packet)이라는 작은 단위로 나누어 패킷별로 보내는 방식

게이트웨이 호스트는 다른 네트워크로 향하거나 다른 네트워크에서 들어오는 메세지를 전달함
메세지를 목적지에 가깝게 보내주는게 라우터
라우터는 기본적으로 메세지를 주고받는 형식을 기반으로 한다

🌠 OSI 참조 모델

• 응용 계층(application layer)
  웹에서 사용하는 HTTP나 파일 전송을 위한 FTP, 이메일 전송을 위한 SMTP 등과 같은 응용 프로토콜의 기능을 지원하는 계층
• 표현 계층(presentation layer)
  응용 계층에서의 데이터의 사용 방식과 무관하게 잘 작동할 수 있도록 해주는 계층
• 세션 계층(session layer)
  통신 컴퓨터간 연결의 접속/차단과 데이터 통신 방식을 결정하는 계층
• 전송 계층(transport layer)
  세그먼트 또는 데이터그램 단위의 메시지가 송신 컴퓨터에서 수신 컴퓨터까지
  신뢰성을 보장하며 전달하는 계층

  중간에 사라지거나 순서가 바뀐 패킷을 오류없이 다시 구성해서 전송해주는 역할
  TCP

• 네트워크 계층(network layer)
  패킷 단위의 전송이 이루어지는 계층
  네트워크 계층에서 🌀인터넷의 IP가 정의됨

  패킷이 어떤 경로를 통해 송신 컴퓨터에서 수신 컴퓨터까지
  전달할지 결정하는 라우팅이 일어남
  라우팅은 라우터가 해준다
  패킷들이 몰릴 경우에 혼잡제어 수행

• 데이터링크 계층(datalink layer)
  직접 연결된 두 컴퓨터나 장비 간에 🌀프레임(frame 블록 단위의 정보) 단위로 전송하는 계층

  전송을 위해 프레임의 시작과 끝, 수신자 주소 등이 추가되고
  오류의 발견/수정하는 기능, 흐름 제어의 기능도 담당함!!

  🌠 데이터링크 계층의 프로토콜의 대표 : 이더넷 , 와이파이

• 물리 계층(physical layer)
  물리적으로 연결된 채널을 통해 비트 단위로 전송이 되는 계층

🌈 현재

OSI 참조모델은 표준이라는것에 의의가 있고 현재 실제 사용되지는 않고 일부분만 차용되서 사용됨
가장 대표적인게 인터넷에서의 TCP/IP 이다

TCP/IP 4 Layer                                                 OSI 7 Layer

응용프로그램(브라우저)                       응용계층 + 표현계층 + 세션계층
TCP                                                 전송 계층
IP                                                   네트워크 계층
데이터링크(네트워크 인터페이스)          데이터링크계층 + 물리계층

출처 : 방송통신대학교