자료의 표현

10진수 표현

zone 형식
1바이트를 한 단위로 사용. 상위 4비트 존 영역 / 하위 4비트 수치영역

• 존영역은 항상 1111
• 부호는 최하위 바이트의 존 영역에 표시

pack 형식
1바이트에 10진수 두 자리 표현

• 부호는 최하위 바이트의 하위 4비트

위의 두 형식에서 부호 표현은 양수일 경우 / 1100(c) 음수일 경우 1101(d)

---

2진수의 정수표현

부호와 절대값 형식
부호를 최상위 비트(MSB)에 표시 0:양수 1:음수

• 가산기와 감산기 모두 필요하다.
• +0 -0이 존재한다.
• 범위: $-2^{n-1}-1$ ~ $(2^{n-1}-1)$

1의 보수 형식(Signed 1's Complement)

• 가산기 회로로 감산을 수행할 수 있다.
• +0, -0 존재
• 범위: $-2^{n-1}-1$ ~ $(2^{n-1}-1)$
• 캐리가 발생하면 더한다.

2의 보수 형식(Signed 2's Complement)

• 가산기 회로로 감산을 수행할 수 있다.
• 범위: $-2^{n-1}$ ~ $(2^{n-1}-1)$
• 캐리가 발생하면 버림.
• 컴퓨터에서 쓰는 방식

음수의 보수도 똑같이 구한다.
빼고 1의 보수나 1의 보수하고 더하나 같다.

2진수의 실수 표현

고정 소수점 표현 방식
소수점이 항상 최상위 비트의 왼쪽 바깥이나 최하위 비트의 오른쪽 밖에 고정되어 있다고 생각한다.

부동소수점 표현 방식
고정소수점 방식에 비해 작은 값이나 큰 값을 표현할 수 있다.

• 정규화: 정수부가 1이 되도록 소수점 이동
• 부호: 양수는 0, 음수는 1
• 가수부: 소수부 저장
• 지수부: 지수와 바이어스를 더한 값 저장, 단정도 바이어스 127 , 배정도 바이어스 1023
• single precision (단정도): 부호 1, 지수부 8, 가수부 23
• double precision (배정도): 부호1 지수부 11 가수부 52
• (덧셈, 뺄셈): 지수 조정, 덧셈 (뺄셈) 수행, 가수 정렬, 지수 정규화
• (곱셉, 나눗셈): 가수끼리 곱한다(나눈다). 지수끼리 더한다(뺀다). 필요시 반올림(소수점), (가수)정규화

문자 자료의 표현

BCD Binary Coded Decimal

• 상위 2비트: 존비트, 하위 4비트는 숫자비트
• 존 비트 값: 00 숫자, 01 A~I, 10 J~R, 11 S~Z

EBCDIC Extended Binary Coded Decimal Interchange Code

• 존비트4 숫자비트 4

ASCII 코드 American Standard Code for Information Interchange

• 존 비트 3 , 숫자 비트 4
• 데이터 통신용으로 사용할 때는 상위 1비트에 패리티 비트를 추가하기도 한다.

유니코드
세계 여러 나라의 언어를 통일된 방법으로 표현할 수 있도록 정의한 국제 표준 코드

• 2바이트를 조합하여 하나의 글자 표현
• wchar_t

논리자료의 표현

• T, F
• 1비트로 표현할 수 있지만 일반적으로 컴퓨터 내부에서는 1바이트나 1워드를 논리값을 표현하는 단위로 사용한다.
  (최하위비트, 전체 비트, 하나 이상의 비트)가 1이면 참

자료의 추상화

자료: 프로그램의 처리 대상이 되는 모든 것을 의미한다. 어떤 값 자체를 의미하기도 한다.
연산: 어떤 일을 처리하는 과정으로 연산자를 이용하여 수행된다.
자료형: 처리할 자료의 집합과 자료에 대해 수행할 수 있는 연산자의 집합

space complexity
알고리즘을 프로그램으로 실행하여 완료하는 데까지 필요한 총 저장공간

• 고정공간: 프로그램의 크기나 입출력에 상관없이 고정적으로 필요한 저장공간으로 프로그램 저장공간과 변수 및 상수를 저장하는 공간
• 가변공간: 실행과정에서 사용하는 자료와 변수를 저장하는 공간과 함수를 실행하는데 관련된 정보를 저장하는 공간

Time Complexity
알고리즘을 프로그램으로 실행하여 완료하는데 까지 걸리는 시간
- 프로그램의 컴파일시간과 실행시간을 더해 구한다.
- 실행 빈도 수를 계산하여 측정한다.

Big-oh Notation

• $O(f(n))$: Big oh of f(n) 상한을 나타내기 위한 표기법
• 함수$f(n)$과 $g(n)$이 주어졌을 때
  모든 n $\geq n_0$ 에 대하여 $|f(n)| \leq c|g(n)|$을 만족하는 상수 c와 $n_0$이 존재하면 $f(n)=O(g(n))$
• 최악의 경우에도 $g(n)$의 수행시간 안에 알고리즘 수행이 완료된다.

Big-Omega Notation

• $Ω(f(n))$ Big Omega of f(n) 하한을 나타내기 위한 표기법
• 함수$f(n)$과 $g(n)$이 주어졌을 때
  모든 n $\geq n_0$ 에 대하여 $|f(n)| \geq c|g(n)|$을 만족하는 상수 c와 $n_0$이 존재하면 $f(n)= Ω (g(n))$이다.
• 알고리즘 수행에는 적어도 $g(n)$의 수행시간이 필요함을 뜻한다.

Big-Theta Notation
$\theta (f(n))$:Big theta of f(n) 상한과 하한이 같은 정확한 차수를 나타내는 표기법

• 함수$f(n)$과 $g(n)$이 주어졌을 때
  모든 $n \geq n_0$ 에 대하여 $c_1|g(x)| <= |f(n)| <= c_2|g(n)|$
  을 만족하는 상수 c_1 c_2 n_0 가 존재하면 $f(n)=\theta(g(n))$이다.
• $f(n)=O(g(n))$ 이면서 $f(n)=Ω(g(n))$ 이어야 한다.
• 시간복잡도를 정확히 계산할 수 있다면 빅 세타 표기법을 사용한다.

일반적으로 최악의 경우를 고려한 해결책을 찾기 때문에 빅오 표기법을 주로 사용한다.
$\log n<n<n\log n<n^2<n^3<2^n<n!$