Little bIT awesome

큐 (Queue) Queue 라는 단어의 사전적 의미는 '대기줄', '줄을 서서 기다리다' 먼저 줄을 선 사람이 먼저 서비스를 받듯이 Queue도 먼저 들어온 자료가 먼저 빠져 나가는 FIFO(First In First Out) 구조이다. Offer 과 Poll 대신 Enqueue, Dequeue 등으로도 표현된다. Queue의 특징 정해진 한 곳을 통해서 삽입과 삭제가 이루어지는 스택과는 달리 큐의 삽입과 삭제는 양 끝에서 이루어진다. 새로운 원소의 삽입은 항상 큐의 뒤쪽에서, 원소의 삭제는 큐의 앞쪽에서 이루어지며 프론트와 리어라는 용어를 다음과 같이 정의한다. 프론트(front) : 큐의 삭제 연산이 이루어지는 곳 리어(rear) : 큐의 삽입 연산이 이루어지는 곳 큐의 연산자 메서드 설 명 boo..

Stack 스택(Stack)의 사전적 정의는 '쌓다', '더미'이다. 즉, 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. 그림과 같이 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 특징이 있는데, 이러한 자료의 구조를 LIFO(Last In First Out) 구조라고 말한다. Stack 사용처 스택은 수식계산, 수식 괄호 검사, undo / redo, 웹브라우저의 뒤로 / 앞으로 등에 사용된다. JVM(자바 가상 머신)의 Runtime Data Area에 Stack 메모리에도 사용된다. Stack은 마지막으로 사용이 끝난 지역변수를 바로바로 쳐내버려 메모리를 매우 효율적으로 사용하는 방법이기 때문에 스택의 구조 개념이 프로그래밍 메모리 영역에 고대로 사용되는 것이..

B-Tree & B+Tree 이진트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다는 단점이 있다. 하지만 이진트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 검색 모두 O(logN)의 성능을 보인다는 장점 때문에 개선시키기 위한 노력이 이루어지고 있다. B Tree = Balanced binary tree 이진트리 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조 정이진트리 : 트리의 모든 node가 0개 혹은 2개의 자식을 가지는 경우 포화이진트리 : leaf node가 끝까지 꽉 찬 트리 완전이진트리 : 마지막 레벨을 제외한 모든 레벨에서 순서대로 node가 꽉 채워진 트리 균형이진트리 : leaf node들의 레벨차이가 최..

해시 함수 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다. 이 때, 매핑 전 원래 데이터의 값을 Key 매핑 후 데이터의 값을 hash value(해시 값) 매핑하는 과정 자체를 hashing(해싱) 이라고 한다. 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다. collision Lee → 해싱함수 → 5 Kim → 해싱함수 → 3 Park → 해싱함수 → 2 ... Chun → 해싱함수 →5 // Lee 해싱값과 충돌 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해쉬충돌(c..

Tree Node와 Edge로 이루어진 자료구조 트리는 값을 가진 Node(vertex)와 이 노드를 연결해주는 Edge(link)으로 이루어진다. 노드에는 특정 정보를 저장할 수 있고, edge는 정보들간의 관계를 나타낸다. 제일 상위 노드를 Root(루트) 노드라고 한다. (그림 상 값 1을 가진 노드) 모든 노드들은 0개 이상의 자식 노드를 가지고 있으며 보통 부모-자식 관계로 부른다. + path : edge에 의해 연결된 node들의 집합 leaf 노드 : 자식이 없는 node subtree : 큰 tree에 속하는 작은 tree node의 degree : 각 노드가 지닌 가지의 수 (subtree의 개수) node level : 루트로부터 단순 경로의 길이 트리의 특징 1. 트리에는 사이클이 ..

스택 & 큐 스택(Stack) 입력과 출력이 한 방향으로 제한 LIFO(Last In First Out, 후입선출) : 가장 나중에 들어온 것이 먼저 나옴 ex) 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에 사용됨 sp: 스택 포인터 private int sp = -1; // 초기값 push(): 스택에 데이터 넣기 public void push(Object o) { if(isFull(o)) { return; } stack[++sp] = o; } pop(): 데이터 최상위 값 빼기 public Object pop() { if(isEmpty(sp)) { return null; } Object o = stack[sp--]; return o; } isEmpty(): 스택이 비어있는지 확인하기 pri..

배열 ※ C++ 에서 배열 사이즈 구하기 int arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); // 전체 배열 사이즈 / 원소 하나의 사이즈 1. 배열 회전 프로그램 A. 기본적인 회전 알고리즘 void leftRotatebyOne(int arr[], int n) { int temp = arr[0], i; for (i = 0; i < n - 1; i++) { arr[i] = arr[i + 1]; } arr[i] = temp; } 첫 번째 인덱스 값 temp에 저장 i가 0부터 n - 1까지 돌면서 arr[i]에 arr[i + 1] 값 저장 루프 다 돌고 나오면 temp에 저장되어 있던 arr[0] 값 arr[n] 에 저장 이 함..