Red Black Tree
RBT(Red-Black Tree)는 BST 를 기반으로하는 트리 형식의 자료구조이다. 결론부터 말하자면 Red-Black Tree 에 데이터를 저장하게되면 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth 를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth 가 최소가 되는 경우는 tree 가 complete binary tree 인 경우이다.
Red-Black Tree 의 정의
Red-Black Tree 는 다음의 성질들을 만족하는 BST 이다.
- 각 노드는 Red or Black이라는 색깔을 갖는다.
- Root node 의 색깔은 Black이다.
- 각 leaf node 는 black이다.
- 어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다.
- 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. cf) Black-Height: 노드 x 로부터 노드 x 를 포함하지 않은 leaf node 까지의 simple path 상에 있는 black nodes 들의 개수
Red-Black Tree 의 특징
- Binary Search Tree 이므로 BST 의 특징을 모두 갖는다.
- Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
- 노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL 들을 leaf node 로 간주한다.
RBT 는 BST 의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조이다. 이를 어떻게 해결한 것인가?
삽입
우선 BST 의 특성을 유지하면서 노드를 삽입을 한다. 그리고 삽입된 노드의 색깔을 RED 로 지정한다. Red 로 지정하는 이유는 Black-Height 변경을 최소화하기 위함이다. 삽입 결과 RBT 의 특성 위배(violation)시 노드의 색깔을 조정하고, Black-Height 가 위배되었다면 rotation 을 통해 height 를 조정한다. 이러한 과정을 통해 RBT 의 동일한 height 에 존재하는 internal node 들의 Black-height 가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지된다.
삭제
삭제도 삽입과 마찬가지로 BST 의 특성을 유지하면서 해당 노드를 삭제한다. 삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라지게 된다. 그리고 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정한다. 지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지된다.
Java Collection 에서 ArrayList 도 내부적으로 RBT 로 이루어져 있고, HashMap 에서의 Separate Chaining에서도 사용된다. 그만큼 효율이 좋고 중요한 자료구조이다.
LIS (Longest Increasing Sequence)
최장 증가 수열 : 가장 긴 증가하는 부분 수열
[ 7, 2, 3, 8, 4, 5 ] → 해당 배열에서는 [2,3,4,5]가 LIS로 답은 4
구현 방법 (시간복잡도)
- DP : O(N^2)
- Lower Bound : O(NlogN)
DP 활용 코드
int arr[] = {7, 2, 3, 8, 4, 5};
int dp[] = new int[arr.length]; // LIS 저장 배열
for(int i = 1; i < dp.length; i++) {
for(int j = i-1; j>=0; j--) {
if(arr[i] > arr[j]) {
dp[i] = (dp[i] < dp[j]+1) ? dp[j]+1 : dp[i];
}
}
}
for (int i = 0; i < dp.length; i++) {
if(max < dp[i]) max = dp[i];
}
// 저장된 dp 배열 값 : [0, 0, 1, 2, 2, 3]
// LIS : dp배열에 저장된 값 중 최대 값 + 1
하지만, N^2으로 해결할 수 없는 문제라면? (ex. 배열의 길이가 최대 10만일 때..)
이때는 Lower Bound를 활용한 LIS 구현을 진행해야한다.
REST & RESTful - 11차에 진행 완료.
Cookie & Session
HTTP는 비상태성(Stateless) 프로토콜로 상태 정보를 유지하지 않는다. 연결을 유지하지 않기 때문에 리소스 낭비가 줄어드는 것은 큰 장점이지만 통신할 때마다 매번 연결 설정을 해야 하며, 이전 요청과 현재 요청이 같은 사용자의 요청인지 알 수 없다는 단점이 존재한다.
쿠키와 세션을 통해서 HTTP의 Stateless한 문제점을 해결할 수 있다.
[저장 위치]
- 쿠키 : 클라인어트의 웹 브라우저가 지정하는 메모리 or 하드 디스크
- 세션 : 서버의 메모리
[만료 시점]
- 쿠키 : 저장할 때, expires 속성을 정의하여 무효화시키면 삭제될 날짜를 지정할 수 있다.
- 세션 : 클라이언트가 로그아웃하거나 설정 시간 동안 반응이 없으면 무효화되기 때문에 정확한 시점을 알 수 없다.
[리소스]
- 쿠키 : 클라이언트에 저장되고 클라이언트의 메모리를 사용하기 때문에 서버 자원을 사용하지 않는다.
- 세션 : 서버에 저장되고, 서버 메모리로 로딩되기 때문에 세션이 생길 때마다 리소스를 차지한다.
[용량 제한]
- 쿠키 : 클라이언트도 모르게 접속되는 사이트에 의하여 설정될 수 있기 때문에 쿠키로 인해 문제가 발생하는 걸 막고자 한 도메인당 20개, 하나의 쿠키당 4KB로 제한해 두었다.
- 세션 : 클라이언트가 접속하면 서버에 의해 생성되므로 개수나 용량 제한이 없다.
[보안]
- 쿠키 : 클라이언트에 저장하기 때문에 보안에 취약하다.
- 세션 : 서버에 저장하기 때문에 쿠키에 비해서는 보안에 우수하다.
[OS] Race Condition
공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태
동시 접근 시 자료의 일관성을 해치는 결과가 나타남
Race Condition이 발생하는 경우
- 커널 작업을 수행하는 중에 인터럽트 발생
- 문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
- 해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
- 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
- 문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
- 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
- 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
- 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
- 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법
NoSQL - 저장 방식에 따른 NoSQL 분류
Key-Value Model, Document Model, Column Model, Graph Model로 분류할 수 있다.
1. Key-Value Model
가장 기본적인 형태의 NoSQL 이며 키 하나로 데이터 하나를 저장하고 조회할 수 있는 단일 키-값 구조를 갖는다. 단순한 저장구조로 인하여 복잡한 조회 연산을 지원하지 않는다. 또한 고속 읽기와 쓰기에 최적화된 경우가 많다. 사용자의 프로필 정보, 웹 서버 클러스터를 위한 세션 정보, 장바구니 정보, URL 단축 정보 저장 등에 사용한다. 하나의 서비스 요청에 다수의 데이터 조회 및 수정 연산이 발생하면 트랜잭션 처리가 불가능하여 데이터 정합성을 보장할 수 없다. ex) Redis
2. Document Model
키-값 모델을 개념적으로 확장한 구조로 하나의 키에 하나의 구조화된 문서를 저장하고 조회한다. 논리적인 데이터 저장과 조회 방법이 관계형 데이터베이스와 유사하다. 키는 문서에 대한 ID 로 표현된다. 또한 저장된 문서를 컬렉션으로 관리하며 문서 저장과 동시에 문서 ID 에 대한 인덱스를 생성한다. 문서 ID 에 대한 인덱스를 사용하여 O(1) 시간 안에 문서를 조회할 수 있다.
대부분의 문서 모델 NoSQL 은 B 트리 인덱스를 사용하여 2 차 인덱스를 생성한다. B 트리는 크기가 커지면 커질수록 새로운 데이터를 입력하거나 삭제할 때 성능이 떨어지게 된다. 그렇기 때문에 읽기와 쓰기의 비율이 7:3 정도일 때 가장 좋은 성능을 보인다. 중앙 집중식 로그 저장, 타임라인 저장, 통계 정보 저장 등에 사용된다. ex) MongoDB
3. Column Model
하나의 키에 여러 개의 컬럼 이름과 컬럼 값의 쌍으로 이루어진 데이터를 저장하고 조회한다. 모든 컬럼은 항상 타임 스탬프 값과 함께 저장된다.
구글의 빅테이블이 대표적인 예로 차후 컬럼형 NoSQL 은 빅테이블의 영향을 받았다. 이러한 이유로 Row key, Column Key, Column Family 같은 빅테이블 개념이 공통적으로 사용된다. 저장의 기본 단위는 컬럼으로 컬럼은 컬럼 이름과 컬럼 값, 타임스탬프로 구성된다. 이러한 컬럼들의 집합이 로우(Row)이며, 로우키(Row key)는 각 로우를 유일하게 식별하는 값이다. 이러한 로우들의 집합은 키 스페이스(Key Space)가 된다.
대부분의 컬럼 모델 NoSQL 은 쓰기와 읽기 중에 쓰기에 더 특화되어 있다. 데이터를 먼저 커밋로그와 메모리에 저장한 후 응답하기 때문에 빠른 응답속도를 제공한다. 그렇기 때문에 읽기 연산 대비 쓰기 연산이 많은 서비스나 빠른 시간 안에 대량의 데이터를 입력하고 조회하는 서비스를 구현할 때 가장 좋은 성능을 보인다. 채팅 내용 저장, 실시간 분석을 위한 데이터 저장소 등의 서비스 구현에 적합하다.
Wrapper Class
기본 자료형을 객체 타입의 자료형으로 변환이 필요할 때 주로 사용한다.
-
사용 용도
- 객체로 저장해야 할 경우
- 매개변수로 객체가 요구될 경우(ex. 제네릭, Collection의 타입)
- 객체 간의 비교가 필요할 경우
- 제네릭이나 컬렉션에서 사용할 경우, 기본형을 쓸 수 없기 때문에 이를 Wrapping한 형태를 사용해야 한다.
-
특징
- 산술 연산을 위한 클래스가 아니기 때문에 Immutable하다.(불변)
- 불변 객체이기 때문에 값에 대한 변경은 불가능하고 새로운 값(객체)의 할당이나 참조만 가능하다.
- Boxing : 기본 자료형 -> Wrapper Class
- UnBoxing : Wrapper Class -> 기본 자료형
- JDK 1.5부터 오토 박싱, 오토 언박싱을 지원한다.
- 언박싱 시 사용되는 메소드는 다음과 같은 형태를 갖는다.
- intValue : 객체 -> int 값으로 변환.
문자를 숫자로 바꾸거나, 숫자를 문자를 바꿀 때 두 가지 방식의 차이점이 존재한다.
[Code]
// 문자열 -> 기본형
int number1 = Integer.parseInt("100");
// 문자열 -> wrapper class
Integer number2 = Integer.valueOf("100");
위에서 언급했듯이, JDK 1.5부터 오토 박싱과 오토 언박싱이 지원되기 때문에 반환값이 기본형이든, wrapper class이든 차이가 없어졌다. 그래서 굳이 구별하지 않고 valueOf()를 사용해도 된다.
단, 성능을 비교하면 valueOf()가 조금 더 느리다고 한다.
접근 제어 지시자
자바에서 기본적인 부분이지만, 실제로 사용할 때 의미를 파악하지 않고 남발하는 경우가 많아 정리하려 한다.
- public : public으로 선언된 멤버는 어떤 클래스에서라도 접근이 가능하다. public 메소드는 private 멤버와 프로그램 사이의 인터페이스 역할을 수행하기도 한다.
- protected : protected 멤버를 포함하는 클래스가 정의되어 있는 해당 패키지 내 그리고 해당 클래스를 상속 받은 외부 패키지의 자식 클래스에서 접근이 가능하다.
- private : private으로 선언된 멤버는 해당 멤버를 선언한 클래스에서만 접근이 가능하다. public 메소드를 이용한다면 해당 객체의 private 한 멤버에 접근이 가능하다.
- Default(package private) : 같은 클래스의 멤버와 해당 클래스가 정의되어 있는 패키지 내에서만 접근이 가능하다.
참고
- private의 경우
Private 멤버나 메소드를 가지고 있는 클래스를 A라고 하자.
그리고 B라는 클래스가 A를 상속받는다. 이 경우, B 클래스는 private으로 선언된 멤버 혹은 메소드에 접근할 수 없다.
따라서 상속을 받더라도 private한 멤버에는 접근이 불가능 하다.
대신, public 메소드 통해 getter를 만들면 private 멤버를 사용할 수 있다.
- protected의 경우
Protected 멤버나 메소드를 가지고 있는 클래스를 A라고 하자.
마찬가지로 B라는 클래스가 A를 상속받는다. 이 경우, B 클래스는 protected로 선언된 멤버 혹은 메소드에 접근이 가능하다. B 라는 클래스가 다른 패키지에 선언되었을지라도 A 클래스의 멤버에 접근이 가능하다.
하지만, 다른 패키지의 A 클래스를 상속받지 않은 클래스는 A 클래스의 멤버에 접근할 수 없다. 마치 private 처럼 말이다.
