BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)

AVL Tree 예시

AVL Tree

Not AVL Tree

용어

  • 노드의 height: h
  • balance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)
  • empty height: -1

특징

  • AVL 트리는 BST이면서 동시에 균형을 유지하고 있음
  • 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1)
    • 즉, 모든 노드들은 balance factor 를 알고 있음
  • 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장

문제는 이러한 균형을 맞추려 하다 보니 유지하는 방법이 복잡함. 예를 들어, 노드 삽입이나 삭제로 인해 왼쪽과 오른쪽 서브트리의 height의 계산결과가 2, -2가 나온 경우, 트리를 rotation 시켜줘야 함


rotation에는 2가지 관점이 있는데 AVL 트리를 height balance로 유지하는 것과 binary search tree로 유지하는 관점이 있음. 관점은 나뉘어 있지만 가장 중요한 것은 rotation 시키면서 트리의 height를 낮춰야 복잡도가 줄어듦

rotation의 방법은 4가지로 1번만 rotation 시키는 LL, RR와 2번 rotation 시키는 LR, RL이 존재.


Single Rotation

LL (Right)


왼쪽은 차이가 2이고 오른쪽은 0이므로 왼쪽이 무너진 경우. 이 경우는 오른쪽으로 트리를 회전시켜주면 해결

RR (Left)


왼쪽은 차이가 0이고 오른쪽은 2이므로 오른쪽이 무너진 경우. 이 경우는 왼쪽쪽으로 트리를 회전시켜주면 해결

Double Rotation

위에서 본 LL, RR과는 달리 방향이 일정하지가 않기 때문에 첫 회전에서는 LL 또는 RR로 방향을 맞춘 다음 다시 회전시켜 높이의 균형을 유지시켜줌

RL (Right & Left)


가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 RR의 형태를 이루기 때문에 자리를 바꾼 후, RR 로 회전을 한번 더 시킴.

LR(Left & Right)

가장 마지막 노드인 422 값을 부모노드와 자리를 바꾸면 바로 LL의 형태를 이루기 때문에 자리를 바꾼 후, LL 로 회전을 한번 더 시킴.

장단점

  • 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춤
  • 프로그래밍하기가 어렵고 디버깅 또한 어려움.
  • 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는데에 시간이 듦
  • 대규모 tree를 이룬 후 검색하는 것은 DB에서 주로 발생하는데 DB는 이미 B-Tree 자료구조를 사용 중임


'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30

Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.

정의

  1. 각각의 모든 node 들의 key는 중복된 값이 아님 (unique)
  2. 기존의 binary tree는 순서가 없지만 BST는 순서가 존재
  3. parent node의 왼쪽은 부모보다 작은 값이고 오른쪽은 부모보다 큰 값임
  4. 왼쪽, 오른쪽의 서브 트리또한 BST임

Search

  1. 찾고자 하는 Key와 root node값이 같으면 성공
  2. Key가 root node 값보다 작다면 (key < root node) 왼쪽의 sub tree로 이동
  3. Key가 root node 값보다 작다면 (key > root node) 오른쪽의 sub tree로 이동
  4. 1~3번 반복
  5. 만약 조건에 맞는 데이터가 없으면 실패 (tree에 값이 존재하지 않는 경우)


위 그림에서 120 값을 찾는 예시입니다. 

  1.  root node(=100)와 찾고자 하는 값 (=120) 비교
  2. root node보다 찾고자 하는 값이 더 크므로 (100 < 120) 오른쪽 subtree로 이동
  3. 오른쪽 subtree의 노드값(=150)과 찾고자 하는 값(=120)과 비교
  4. 찾고자 하는 값이 더 작으므로 (150 > 120) 왼쪽 subtree로 이동
  5. 120값이므로 검색 성공


Insert

값을 삽입하고자 하거나 찾고자 하는 값이 없을 경우 루트노드에서 시작, 값을 비교해가면서 tree의 가장 마지막까지 간 다음 값을 입력

예시

위 그림에서 80을 넣고자 하면 아래와 같은 위치에 삽입


Delete

  1. 첫 단계는 지우고자 하는 값이 해당 tree에 있는지 search
  2. 지우고자 하는 값이 leaft node(가장 마지막)에 위치해있으면, 그냥 지우면 됨
  3. internal node라면 다음과 같이 분기가 됨
    1. 지워야 하는 node가 child node를 1개 가지고 있는 경우, internal node를 지운 후 해당자리에 child node를 옮김
    2. 지워야 하는 node가 child node를 2개 가지고 있는 경우, 왼쪽의 subtree에서 가증 큰 노드 또는 오른쪽 subtree에서 가장 작은 노드를 옮김

예시

50 (leaf node) 삭제


75 (internal node 이며 1개의 child node 존재) 삭제


150 (internal node 이며 2 child node 존재) 삭제

1. 왼쪽의 subtree에서 가장 큰 노드를 이동


2. 오른쪽 subtree에서 가장 작은 노드를 이동



internal node이며 child node를 2개 가지고 있는 경우 삭제하는 방법은 2가지가 있지만 여기서 조건적으로 효율적인 방법이 존재.

1, 2번의 방법 중 트리의 height를 줄일 수 있는 방법을 채택하는 것이 향후 트리 검색의 속도를 향상시킬 수 있음

복잡도

BST는 검색, 삽입, 삭제 모두 O(h)임. h는 BST의 높이(height)

BST에서는 inorder(LVR) 검색 방식을 사용

BST는 평균(최상) 시간복잡도가 O(log₂n)이지만 최악의 경우 O(n)임. (skewed tree이면 node의 수만큼 시간이 소요됨)

  • tree가 complete binary tree거나 full binary tree이면 O(log₂n), skewed tree이면 O(n)

위 O(N)의 경우때문에 노드가 얼마 되지 않아도 검색속도가 나오지 않을 가능성이 존재함. 이 때문에 AVL Tree가 고안됨


'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
  • Heap은 Complete Binary Tree를 기본으로 가지는 자료구조
  • 일반적으로 array로 구현하는 것이 좋음
  • Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
  • 시간복잡도: O(log₂N)
  • Heap은 다음과 같은 속성(property)를 만족함
    • A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립
  • 종종 priority queue를 보충하는대에 사용

종류

max heap: root노드가 가장 큰 수

min heap: root노드가 가장 작은 수

Max Heap

부모노드의 키가 자식노드의 키보다 항상 큼


Node Insertion

max heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 비교하며 자리를 바꿔 나감. (root node 까지)

Node Deletion

max heap에서 노드 삭제는 항상 루트노드를 지움. 그 다음 complete binary tree를 유지하기 위해 tree를 재조정함. 말단의 맨 오른쪽 노드를 지운 다음, 루트 노드 자리에 옮기고 child node와 비교해 자리를 바꿔나감.


Max Heap에서 노드 추가, 삭제는 모두 트리의 depth만큼 걸림 -> O(log₂N)

Min Heap

부모노드의 키가 자식노드의 키보다 항상 작음



키의 대소관계는 오로지 부모노드와 자식노드 간에만 성립되며, 형제(sibling) 사이에는 대소관계가 정해지지 않음

Priority Queue

일반적인 queue는 FIFO 이기 때문에 먼저 들어온 데이터가 먼저 나가지만, priority queue는 우선순위가 높은 데이터 먼저 나감

새로운 노드가 삽입되면 우선순위에 맞는 위치에 삽입 (enqueue)

제거할 때는 우선순위가 가장 높은 맨 앞의 노드를 삭제 (dequeue)



'공부 > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2018.08.17
Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30



degree가 최대 2인 트리

i번째 level에 나올 수 있는 노드의 최대 개수는 2^(i - 1)

  • 주의 할 것은 전체 tree의 노드 최대 개수 또는 i번째 level까지 전체 노드의 개수가 아닌 i번째 level만 단독으로 보고 있음.

k가 tree의 depth일 때, 최대 노드의 개수는 : 2^k -1

위 그림에서 2번째 level의 노드의 최대 개수는 2^(2-1) = 2개이고, depth는 2^2-1 = 3개, height는 2^3 - 1 = 7개임


binary tree에는 skewed tree, complete binary tree, full(perfect) binary tree가 있음

Full (Perfect) Binary Tree

마지막 레벨까지 노드가 꽉 차게 있는 트리


Complete Binary Tree

노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리



위 그림에서 3번 노드가 없어도 complete binary node는 성립하지만 1번이나 2번 노드가 없으면 complete binary tree가 아니게 됨. 

Skewed Tree




binary tree를 구현하는 데엔 array로 구현하는 것이 좋지만 다른 트리에서는 효율성이 떨어지고 컴파일 언어에서 어레이 사이즈 제한때문에 저장공간 문제가 존재. C에서는 이를 linked list로 해결할 수 있음. (근데  linked list는 구현이 어려움)


Binary Tree Traversal

루트노드에서 시작해 linear 하게 노드를 1번씩 방문하는 방식은 아래와 같습니다.

V: 노드 방문

L: 왼쪽 branch를 타고 이동

R: 오른쪽 branch를 타고 이동


  • inorder: LVR (Left Visit Right)
  • preorder: VLR (Visit Left Right)
  • postorder: LRV (Left Right Visit)

예를 들어, preorder는 하위 트리를 탐색하기 전에 노드 방문이 완료

예시 (inorder: LVR)


  1. 루트노드인 X에서 시작.
  2. 왼쪽 브랜치가 있으므로 왼쪽 브랜치를 타고 Y 노드로 이동
  3. Y 노드에서도 왼쪽 브랜치가 있으므로 왼쪽 브랜치를 타고 S 노드로 이동
  4. S 노드에는 왼쪽 브랜치가 없어서 이동할 수 없음. 
  5. 왼쪽으로 이동할 수 없으므로 S 노드를 방문 후 오른쪽 브랜치로 이동하려하나 브랜치가 없어 Y노드로 롤백
  6. Y노드를 방문한 후 오른쪽 브랜치를 타고 이동하여 T 노드로 이동
  7. T노드는 4~5번과 동일.

위와 같은 순서로 값의 출력은 S, Y, T, X, Z 순으로 출력됨


위와 같이 binary tree의 모든 노드를 탐색하는 방법은 stack이 필요함. 

모든 노드를 탐색하는데에 걸리는 time complexity는 O(N)임 (N은 트리에 존재하는 노드의 개수)

'공부 > 자료구조' 카테고리의 다른 글

Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법  (0) 2018.07.29

Tree 구조


트리는 위와 같은 구조를 갖고 있습니다.

용어

  • node: 트리에서 데이터를 의미
  • branch(link): 노드와 노드를 연결
  • root node: 최상위 노드
  • interior node: 자기자신 아래에 연결된 노드가 있는 형태
  • leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태
  • parent: child 노드들이 연결되어 있는 상위 노드
  • child: 부모노드 아래에 연결되어 있는 노드
  • sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드
  • degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지
  • depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수
  • level: 트리의 특정 depth를 가지는 노드의 집합
  • height: 루트노드에서부터 가장 멀리 있는 노드의 depth
  • 트리의 degree: 트리의 최대 degree
    • 위 그림에서 노드의 최대 degree는 2

Skewed Tree (Degenerate Tree)


Full (Perfect) Tree


Binary Tree

degree가 최대 2 (0 <= degree <= 2)


Quad Tree

degree가 최대 4 (0 <= degree <= 4)


정의

  • root 노드를 제외한 모든 노드는 parent 노드를 1개만 가짐
  • leaf 노드를 제외한 모든 노드는 child 노드를 1개 이상을 가짐

Tree 자료구조의 다양한 타입

Binary Tree

  • Binary Search Tree, Heap, Digital Search Tree
  • Red-Black Tree, AA Tree, Splay Tree

Height-Balanced Binary Tree

  • AVL Tree, T-Tree

n-Way Tree

  • m-Way Tree
  • 2-3 Tree, 2-3-4 Tree

Height-Balanced m-Way Tree

  • B-Tree, B+-Tree, K-d B-Tree

Spatial Tree

  • Quad Tree, Oct Tree, R-Tree


'공부 > 자료구조' 카테고리의 다른 글

Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법  (0) 2018.07.29

Stack

LIFO(Last-In-First-Out) - 가장 마지막에 들어온 데이터가 가장 먼저 나감


stack에서 데이터의 삽입, 삭제를 push와 pop으로 부름

stack을 구현하기 위해선, 초기에 pop이 되지 않도록 array가 비어 있는지 확인하는 함수 (isEmpty)가 필요. 타입선언 언어라면 어레이의 사이즈를 정하기 때문에 어레이에 데이터가 가득 찼는지 확인하는 함수 (isFull)이 필요.

Queue

FIFO(First-In-First-Out) - 가장 먼저 들어온 데이터가 가장 먼저 나감


위 그림에서 f(front)는 데이터의 시작위치를 가리키고 r(rear)은 현재 입력된 데이터의 위치를 가리킴


stack과 유사하게 어레이가 비어있는지 확인하는 함수 (isEmpty)와 가득 찼는지 확인하는 함수 (isFull)이 필요함.

Queue의 문제점

데이터를 삭제할 때마다, 포인터가 한 칸씩 앞으로 이동하기 때문에 삭제된 뒷 공간을 활용할 수 없음.

이러한 문제점 때문에 Circular Queue가 등장

Circular Queue

Queue처럼 r을 +1, f를 +1 하는 방식이 아닌 모드(%)를 사용하여 계산

r = (r + 1) % MAX_CIRCULAR_QUEUE_SIZE
f = (f + 1 ) % MAX_CIRCULAR_QUEUE_SIZE


초기 f와 r은 0으로 시작위치가 동일.




Circular Queue에 데이터를 입력하는 함수(add)나 데이터를 삭제하는 함수(delete)를 작성할 때 가장 최상단에 r과 f가 동일한지 비교하는 함수가 무조건 존재해야함.

만일 r과f가 동일하다면 어레이는 더이상 삭제할 데이터가 없거나 이미 가득 찼다는 뜻

'공부 > 자료구조' 카테고리의 다른 글

Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법  (0) 2018.07.29

추상화(Abstraction) - 중요한 속성만 포함하는 개체.

  • 즉 가장 중요한 것에 초점을 두고 그 이외의 부가적인 것은 무시함.

ADT - Abstract Data Type

한 개의 특별한 데이터 타입의 데이터 표현과 그 타입의 연산을 제공하는 부 프로그램만을 포함하는 클로저이다. 한마디로 사용자에게는 연산에 대한 형식과 제약조건만 알려주고 실제로 어떻게 처리되는지는 표현하지 않는 기능

  • 타입 객체의 표현은 숨겨지고 타입의 정의에서 연산 제공
  • 타입 선언과 연산들은 단일 구문 단위에 포함

자바의 클래스 타입이라 볼 수 있음 

ADT에서 중요한 것은 어떻게 구현되는지는 몰라도 무엇을 하는지 알면 사용자는 만들 수 있다는 점.

복잡도 (Complexity)

프로그램의 실행이 얼마나 오래 걸리는가 (= time complexity)

얼마나 많은 메모리를 사용하는가 (= space complexity)

왜 분석할까?

  • 실제로 실행하기 전에 구현할 알고리즘을 결정
  • 실제 실행시키지 않고  주어진 코드에서 병목현상을 찾을 수 있음

공간복잡도 (Space Complexity)

주어진 알고리즘을 실행시키기 위해 필요한 space는 다음과 같이 두 가지로 분류해 볼 수 있다.

  1. 알고리즘과 무관한 부분: 알고리즘의 특성과는 무관한 부분으로 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간 등이 이에 포함된다.
  2. 알고리즘과 밀접한 부분: 알고리즘의 특성과 밀접한 관계가 있는 부분으로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장하기 위한 공간이나 순환 프로그램일 경우, recursion stack 등이 이에 포함된다.

일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지중 두 번째의 것을 계산하게 된다. 즉, 알고리즘이 문제를 해결하기 위해서 반드시 필요한 부분만을 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한다.

시간복잡도 (Time Complexity)

시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과(frequency count)에 각 명령어의 실행시간(execution time)을 곱한 합계를 의미한다. 그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.

 이와 같이 알고리즘을 이루는 명령어들의 실행횟수를 계산하여 알고리즘의 시간

복잡도를 구하는 일을 알고리즘의 분석(analysis of algorithm)이라고 한다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도 보다는 시간 복잡도를 통해서 이루어진다.

 빅 오 분석법 (Big-O Analysis)

빅 오 분석법은 입력 값의 개수에 따라서 알고리즘의 성능을 분석하는 방법. 이 방법을 통해서 간단하게 알고리즘의 성능을 따져볼 수 있음.

Big-O 는 worst case를 기준으로 함. 계산할 때, 차수가 가장 높은 최고차항만 두고 나머지는 버림

O(1): constant

O(n): linear

O(nlogn):

O(n^2): quadratic

O(2^n): expoential


'공부 > 자료구조' 카테고리의 다른 글

Binary Search Tree  (0) 2018.08.15
Heap  (0) 2018.08.13
Binary Tree  (0) 2018.08.01
Tree  (0) 2018.07.31
Stack, Queue, Circular Queue  (0) 2018.07.30
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법  (0) 2018.07.29

엔디안이란?

엔디안(Endian)은 컴퓨터의 메모리와 같은 1차원의 공간에 여러 개의 연속된 대상을 배열하는 방법을 뜻하며, 바이트를 배열하는 방법을 특히 바이트 순서(Byte order)라 합니다. 엔디안은 보통 큰 단위가 앞에 나오는 빅 엔디안(Big-endian)과 작은 단위가 앞에 나오는 리틀 엔디안(Little-endian)으로 나눌 수 있으며, 두 경우에 속하지 않거나 둘을 모두 지원하는 것을 미들 엔디안(Middle-endian)이라 부르기도 합니다.


사람이 숫자를 쓰는 방법과 같이 큰 단위의 바이트가 앞에 오는 방식이 빅 엔디안입니다.


빅 엔디안리틀 엔디안
0x123412 3434 12
0x1a3ecd1a 3e cdcd 3e 1a

16진수는 2개가 1바이트이므로 묶어서 계산합니다.

장단점

빅 엔디안은 소프트웨어의 디버그를 편하게 해 주는 경향이 있습니다. 사람이 숫자를 읽고 쓰는 방법과 같기 때문입니다.

반대로 리틀 엔디언은 메모리에 저장된 값의 하위 바이트들만 사용할 때 별도의 계산이 필요 없다는 장점이 있습니다. 예를 들어, 32비트 숫자인 0x2A는 리틀 엔디언으로 표현하면 2A 00 00 00이 되는데, 이 표현에서 앞의 두 바이트 또는 한 바이트만 떼어 내면 하위 16비트 또는 8비트를 바로 얻을 수 있습니다.

반면 32비트 빅 엔디언 환경에서는 하위 16비트나 8비트 값을 얻기 위해서는 변수 주소에 2바이트 또는 3바이트를 더해야 합니다. 


'공부' 카테고리의 다른 글

엔디안(Endian)이란?  (0) 2018.07.15
이진법, 16진법, 비트와바이트, 인코딩  (0) 2018.07.12
마이크로소프트 REST API 가이드라인  (0) 2017.03.14
칸반  (0) 2017.03.13
XP - 익스트림 프로그래밍  (0) 2017.03.13
스크럼  (0) 2017.03.13

정말정말 간단한건데 사용안할 줄 알고 대충알고 넘어갔다가 이번에 큰코를 다쳤.............

16진법만 다시 정리할까 했는데 전체적인 내용을 다시 까먹지 않기 위해 비트와 관련된 알고 있는 내용까지 전부 정리합니다.

이진법 (binary)

컴퓨터는 이진법으로 이해를 합니다. 우리가 사용하는 수의 표현방법은 십진법입니다. 이진법에는 0 또는 1 만 존재합니다. 알다시피 십진법은 0~9까지 존재합니다.

십진법 ↔ 이진법

십진법에서 1은 이진법에서도 1입니다. 십진법에서 3은 이진법으로 표현하자면 11이 됩니다. 이를 다시 십진법으로 변경하자면 2^1 + 2^0 = 3 으로 성립이 됩니다.  자리 수가 n개인 이진법를 십진법로 계산하는 공식은 2^n-1 + 2^n-2 + ... + 2^1 + 2^0 이 됩니다. 마지막으로 5를 이진법로 변경하면 101이고 이를 다시 공식에 대입하면 5가되는 것을 알 수 있습니다. 아래 예시 표를보고 공식에 대입해보면 쉽게 이해가 됩니다.

십진법이진법
00
11
311
5101
101010


시간이 없을 땐 https://ko.calcuworld.com/%EC%88%98%ED%95%99/2%EC%A7%84%EB%B2%95-%EA%B3%84%EC%82%B0%EA%B8%B0/ 를 사용하면 깔끔하게 변환이 됩니다.

비트와 바이트

위에서 이진법을 설명한 이유는 비트 때문입니다. 

비트는 0, 1로 이루어져 있습니다. 십진법 5를 표현하려면 자리수가 3개이므로 3비트가 필요합니다. 마찬가지로 10을 표현하려면 4비트가 필요하단 뜻입니다. 


위 이진법을 알고 있다면 다음의 비트가 몇개의 수를 표현하고 있는지 읽을 수 있습니다.

0100000101110000


끊어 읽는 규칙이 없으면 위 비트는 많은 방식으로 해석될 수 있습니다. 컴퓨터는 8비트를 데이터의 크기 기본단위로 사용하여 8비트씩 끊어 읽습니다. 8비트인 이유는 초창기 알파벳과 여러 특수문자를 표현하는 데 필요한 최소한의 크기로 채택이 되었기 때문입니다.

이진법0100000101110000
십진법65122


8비트는 1바이트와 같은 개념입니다. 

1바이트는 8비트이며 표현할 수 있는 수는 2^8 = 256가지 입니다.

2바이트는 16비트와 같은개념이고 표현할 수 있는 2^16 입니다.

16진법

십진법이진법16진법
00000 000000
10000 000101
30000 001103
50000 010105
100000 10100A
150000 11110F
170001 000111


위 표처럼 a,b,c,d,e,f 를 합쳐 16가지의 문자를 표현할 수 있습니다. 16진법은 이진법을 보다 쉽게 축약하여 보여줄 수 있습니다.

아래 문자열을 계산하는 예를 확인하면 이진법보단 16진법이 좀 더 보기 간편한 것을 알 수 있습니다.

APPLE
이진법01000001
01110000
01110000
01101100
01000101
16진법41
70
70
6C
65
십진법65
112
112
108
101


코딩을 하다보면 종종 16진법으로 결과가 내려오는 경우가 있는데 (SHA256 결과) 만약 64자의 길이를 가지고 있다면 이는 32bytes 입니다. 위 표에서 보는 것과 같이 16진법은 2개당 1바이트를 사용합니다. 

기타

십진법에서 0.01234 라는 값에서 소수점을 우측으로 옮기고 싶다면 10^n을 곱하면 됩니다. 예) 0.01234 * 10 = 0.1234,  0.01234 * 10^2 = 1.234, 

16진법에서 0.001f24 라는 값에서 소수점을 우측으로 옮기고 싶다면 16^n을 곱하면 됩니다. 예) 0.001f24 * 16^ = 0.01f24,  0.001f24 * 16^2 = 0.1f24

위 16진법에서 주의할 점은 0.001f24에서 지수자리인 0은 00이 생략되었다고 보는 것이 나중에 편합니다.

[00].[00][1f][24] 이와같이 2자리씩 끊어 존재한다고 인식하는게 편합니다.

인코딩

인코딩은 간단하게 설명합니다.

ANSI

미국에서 표준을 지정. 코드표를 이야기 할 경우엔 ANSI에서 제정한 ASCII와 동일

ASCII

아스키코드라 읽으며 1바이트로 문자를 표현.

한글은 표현할 수 없음.

EUC-KR

ANSI의 한국확장판. 영문을 포함한 ANSI 코드 부분은 1바이트, 한글 등의 문자는 2바이트. 일부 한글이나 아랍어 등을 표현 못함

유니코드

unicode. 세계에 존재하는 모든 문자를 표현하기 위해 제정된 표준 코드 표. 하나의 문자는 유일하게 하나의 수와 짝지어짐.

유니코드로 저장된 문서는 맨 앞에 (BOM)값이 존재할 수 있음. 이는 문서가 어떠한 엔디안을 사용해서 인코딩 되었는지 알려주기 위함. 혼란이 없는 경우엔 생략되기도 함.

UTF-16

16비트 즉 2바이트씩 끊어서 표현. 희귀한 일부 문자들을 제외한 대부분의 문자는 하나 글자당 2바이트로 표현될 수 있음. 2바이트로 표현되지 않는 문자는 2바이트가 더해져 4바이트로 표현.

UTF-8

8비트 즉 1바이트씩 끊어서 표현. ASCII는 1바이트, 유럽문자는 2바이트, 아시아문자는 3바이트로 표현. 파일의 용량절약과 ASCII와의 호환성 향상 이점이 존재.

'공부' 카테고리의 다른 글

엔디안(Endian)이란?  (0) 2018.07.15
이진법, 16진법, 비트와바이트, 인코딩  (0) 2018.07.12
마이크로소프트 REST API 가이드라인  (0) 2017.03.14
칸반  (0) 2017.03.13
XP - 익스트림 프로그래밍  (0) 2017.03.13
스크럼  (0) 2017.03.13

https://github.com/Microsoft/api-guidelines/blob/master/Guidelines.md

'공부' 카테고리의 다른 글

엔디안(Endian)이란?  (0) 2018.07.15
이진법, 16진법, 비트와바이트, 인코딩  (0) 2018.07.12
마이크로소프트 REST API 가이드라인  (0) 2017.03.14
칸반  (0) 2017.03.13
XP - 익스트림 프로그래밍  (0) 2017.03.13
스크럼  (0) 2017.03.13

+ Recent posts