공부기록

Stack? 구현 먼저 stack에서 구현해야 하는 기능은 다음과 같다. public interface Stack { int size(); boolean isEmpty(); void push(E e); E top(); E pop(); } stack을 구현하는 방법은 배열을 사용하는 방법과 linked list를 사용하는 방법이 있다. 배열을 사용한 Stack, ArrayStack 배열을 사용하여 구현한 stack을 ArrayStack이라 칭한다. 구현한 코드는 아래와 같다. public class ArrayStack implements Stack{ public static final int CAPACITY = 1000; private E[] data; private int t = -1; public Ar..

Hashing? key 값에 hash function을 적용하여 hash table의 주소 (entry index)를 산출하여 데이터를 탐색하는 것을 hashing이라고 한다. 데이터를 담은 자료구조를 모두 탐색하는 것이 아닌 키 값을 통해 빠르게 탐색하기 위해 사용한다. O(1)의 복잡도를 기대할 수 있다. hash에서 value를 담는 자료구조를 table이라고 하고 table에 대한 CRUD는 key에 의해 관리된다. hash(key)해서 나온 값이 곧 table의 인덱스이고, 인덱스에 대응하는 entry에 필요한 정보를 저장하게 된다. 당연한 이야기지만, table은 인덱스에 대해 정렬되어 있다. Collision key값에 hash function을 적용하여 주소값을 산출하다 보면 같은 key가..

Heap? 트리 안에 있는 원소들이 서로 비교될 수 있는 이진트리이다. 힙은 다음과 같은 두 가지 규칙이 있는 이진트리이다. 각 노드의 값은 그 노드의 자식들의 값보다 같거나 크다. (max heap의 경우) 이 트리는 complete binary tree (완전 이진 트리) 이므로 가장 깊은 노드들을 제외한 나머지 노드들은 가능한 한 많은 자식들을 가져야 한다. heap의 각 노드는 우선순위를 가진 원소를 하나 포함한다. heap의 규칙은 다음과 같다. 각 노드의 원소는 자식 노드의 원소에 대해 같거나 더 높은 우선순위를 가진다. 이 트리는 완전이진트리이다. Operations adding Reheapification upward의 성격을 가진다. 절차는 아래와 같다. 새로운 원소를 heap의 가능한 ..

선형, 비선형 자료구조 array, list, stack, queue는 모두 선형자료구조이고 graph, tree는 비선형 자료구조이다. Binary Tree? 먼저, 최대 2개의 자식노드를 가질 수 있는 노드들로 이루어진 트리를 이진트리라고 한다. 이진트리의 종류에는 아래와 같은 것이 있다. full binary tree 모든 leaf node가 같은 깊이를 가지고, 모든 non leaf node들은 2개의 자식을 가지는 트리 complete binray tree 가장 깊은 노드를 제외한 노드들은 가능한한 많은 자식을 가져야하고, 가장 깊은 레벨에서 모든 노드들은 왼쪽부터 채워져 있어야한다. Tree의 구현체 배열과 노드로 표현할 수 있다. 배열에서 root를 0 번지부터 시작하면 left child ..

이 게시물을 통하여 배열 (array)와 동적리스트 (linked list)의 차이점과 어느 상황에서 우세한지 비교하고자 한다. 무작위 접근 연산이 일어나면 배열을 쓴다. 링크드리스트는 무작위 접근연산이 일어나서 인덱스가 나오면 거기까지 움직여야 한다. O(N). 배열은 그냥 접근하면 된다. O(1) 커서에서 연산이 일어나면 링크드리스트를 쓴다. 연산이라 함은 insertion, deletion을 말한다. insertion의 경우 링크드리스트는 커서 다음에 새로운 노드를 삽입하고 포인터만 잘 설정해 주면 된다. 이때 O(1)이다. 배열의 경우 커서 다음에 현재 값을 삽입한다고 할 때 커서 다음의 비어있지 않은 공간을 다 뒤로 밀어줘야 된다. 이때 O(N)이다. deletion의 경우 링크드리스트는 포인터..

locking 프로토콜은 가능한 스케줄을 제한한다. exclusive-lock은 쓰기/읽기, shared-lock은 읽기이다. write lock을 할경우 나만 접근하고 다른 트랜잭션은 접근할 수 없다. read lock을 할 경우 다른 read lock은 접근 가능하다. 즉 호환 가능한 lock을 얻을 경우에만 공유 데이터에 접근 가능하다. 락을 얻지 못하면 다른 트랜잭션이 unlock 할 때 까지 기다려야 한다. 근데 스케줄이 serializable하려면 그냥 lock unlock만 하면 안된다. 2-phase locking, tree-based locking이 있다. 2-phase locking growing-phase와 shrinking-phase로 구분된다. growing-phase에서는 락이 ..

트랜잭션의 Isolation 속성은 트랜잭션 연산들을 수행할 때 자기 자신만 하는 것 처럼 보여야 한다는 것이다. 트랜잭션이 들어온 대로 동기화되어 실행되는 것을 serializable이라고 하는데 실제 DBMS는 여러가지 트랜잭션을 동시에 처리해야하기 때문에 실제로 serialize하게 트랜잭션들을 수행하지는 않는다. 트랜잭션들은 active, partially commit, commit, abort가 있다. 오류가 생기면 abort, 그렇지 않으면 commit한다. 동시에 트랜잭션을 수행하기 때문에 발생하는 오류들이 있다. 실제 없는 값을 읽는 dirty read, 내가 update한 값이 사라지는 lost update, 같아야 하는 값을 다르게 읽어버리는 unrepeatable read가 있다. 트..

REST? (Representational State Transfer) REST는 웹에서 데이터를 전송하고 처리하는 방법을 정의한 인터페이스를 말한다. 모든 데이터 구조와 처리 방식은 REST에서 URL을 통해 정의되며, 그래서 매우 직관적으로 이해하기 쉽다. 이는 대중에게 서비스를 제공할 때 좀 더 쉽게 다가갈 수 있도록 하는 요소이기도 하다. REST 개념 HTTP URI(Uniform Resource Identifier)를 통해 자원(Resource)를 명시하고, HTTP Method (POST, GET, PUT, DELETE) 를 통해 해당 자원에 대한 CRUD Operation을 적용하는 것을 의미한다. REST는 자원 기반의 구조 (ROA, Resource Oriented Architectur..