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바이트를 더해야 합니다. 


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

백업 vs 아카이브 차이점  (0) 2019.01.19
절차지향 VS 객체지향  (0) 2018.12.22
엔디안(Endian)이란?  (0) 2018.07.15
이진법, 16진법, 비트와바이트, 인코딩  (1) 2018.07.12
마이크로소프트 REST API 가이드라인  (0) 2017.03.14
칸반  (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와의 호환성 향상 이점이 존재.

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

절차지향 VS 객체지향  (0) 2018.12.22
엔디안(Endian)이란?  (0) 2018.07.15
이진법, 16진법, 비트와바이트, 인코딩  (1) 2018.07.12
마이크로소프트 REST API 가이드라인  (0) 2017.03.14
칸반  (0) 2017.03.13
XP - 익스트림 프로그래밍  (0) 2017.03.13
  1. APPLE 2019.02.14 14:50

    APPLE가 아니고
    ApplE로 된것 같습니다.

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

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

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

+ Random Posts