* Binary Tree(이진 트리)

자식이 최대 2개만 존재하는 트리구조 

각 층별로 숫자를 매겨서 Level이라고 부르는데 레벨 값은 0부터 시작하므로 루트 노드의 레벨은 0이다.

모든 레벨이 꽉 찬 경우 이를 포화 이진 트리라고 부르며 i번째 노드의 자식은 i*2번째와 i*2+1번째 노드가 된다.

이진 트리는 1차원 배열로 구현할 수 있으며 다음 그림과 같이 구현이 가능하다.

* Binary Search Tree

이진 탐색 트리에서 효율적으로 탐색하는 방법은, 이진 트리에 데이터를 효과적으로 넣는 방법에서부터 시작이다.

이진 탐색 트리는 다음과 같은 규칙을 통해 데이터를 저장한다.

1. 이진 탐색 트리에서 노드에 저장된 키는 유일하다.

2. 루트 키의 왼쪽 서브 트리에 존재하는 모든 키는 루트 키보다 작아야 한다.

3. 루트 키의 오른쪽 서브 트리에 존재하는 모든 키는 루트 키보다 커야 한다.

이러한 조건을 만족시키며 값을 저장하기 때문에 저장과 삽입, 삭제시의 시간복잡도는 O(logN)이다.

하지만, 한쪽으로만 데이터가 저장되는 경우 배열보다 많은 메모리를 사용하면서 시간복잡도가 같은 비효율적인 상황이 발생한다.(편항 트리)

이러한 문제를 해결하기 위해 Rebalancing 기법이 등장하였는데, 이를 구현한 트리중 하나인 Red-Black Tree가 있다.

* Red-Black Tree

Red-Black Tree는 자가 균형 이진 탐색 트리로 편향 트리의 단점을 보완한 이진 탐색 트리이다.

즉, 동일한 노드의 수를 가질 때 Depth를 최소화 하여 시간 복잡도를 줄이는 것이 주 목적이다.

Red-Black Tree의 모든 노드는 Red or Black 의 색깔을 가지며 다음 조건을 만족한다.

1. 루트 노드의 색깔은 Black이다.
2. 모든 리프 노드의 색깔은 Black이다.
3. Red 색깔 노드의 자식의 색깔은 Black이다.
4. 모든 리프 노드에서 루트 노드까지 가는 경로에서 만나는 Black 노드의 수는 같다.

이 경우 3번 조건인 Red 색깔 노드의 자식은 무조건 Black 이여야 하는 조건을 위배한다.

이를 해결하는 전략으로 Restructuring(회전), Recoloring(색깔 변환)의 방법이 있다.

Double Red 문제를 해결하기 위해서는 현재 추가된 Node의 부모의 친척의 색깔에 따라 달라진다. 

아래 그림에서는 Z의 부모 친척 노드는 W가 된다.

## 부모 친척 노드가(W) Black인 경우는 Restructuring 과정을 거친다.

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬한다       
2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다. 
3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다. 

## 부모 친척 노드가(W) Red인 경우는 Recoloring 과정을 거친다.

1. 현재 inset된 노드(z)의 부모와 그 형제(w)를 검정(Black)으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다. 
2. Grand Parent(내 부모의 부모)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다. 

위 과정을 거치면  같은 트리가 구성될 것이다.

하지만, 4가 루트 노드가 아니라면 또다시 Dobule Red 문제가 발생할 수 있고, 이 경우 다시 Restructuring / Recoloring 과정을 거쳐야 한다.

이러한 과정을 거치기 때문에 Red-Black Tree의 삽입, Restructuring, Recoloring 모든 작업의 시간복잡도는 O(logN)가 된다.

* 핵심

삼성 기출문제중 난이도가 낮은 편으로 범위가 작아서 백트레킹과 DP로 풀 수 있는 문제다.

DP를 이용하여 푸는 경우 중간에 계속 Max값을 저장해줘야 한다.

* 문제

* 소스 코드

* 핵심

오르막 수라면 마지막 수보다 다음 숫자가 커지면 안된다.

dp[i][j]는 i번째 자리수가 j일 때의 만들수 있는 경우의 수로 잡으면 

dp[i][j] += dp[i-1][j~10]이 될 것이다.

* 문제

* 소스 코드

*핵심

처음에는 Backtracking으로 접근했다가 n의 범위때문에 시간 초과가 발생했다.

그렇다면 DP로 해결할 수 있는 문제인데, DP에 어떤 값을 저장할 것인지가 문제이다.

dp[i][j] = i번째 순서에 j를 만들 수 있는 경우의 수를 저장했다.

* 문제

* 소스 코드

#List

#Set

#Queue

#Map

* 참고

* 개념 이해

공통 부분 문자열과 최장 공통 부분 수열은 비슷한점이 많다.

공통 부분 문자열(Longest Common Substring)은 중간에 끊어지는 값이 이어지는 부분 배열중에서 문자열을 찾는 방식이고,

최장 공통 부분 수열(Longest Common Subsequence)은 문자열이 연속되지 않아도 선택이 가능하다.

위와 같은 예시가 있을 때,

공통 부분 문자열은 BCD, 최장 공통 부분 수열은 BCDEF 가 될 것이다.

* 공통 부분 문자열

문자열 A와 B가 있을 때,

dp[i][j] = A문자열은 i번째, B문자열은 j번째 글자까지 비교했을 때 가장 긴 공통 부분 문자열의 길이

DBC와 ABC를 비교했을 때 공통 부분 문자열은 BC가 있으므로 답은 2가 될 것이다.

이를 코드로 구현하면 다음과 같다.

* 최장 공통 부분 수열(Longest Common Subsequence) 

문자열 A와 B가 있을 때, 

dp[i][j] = A문자열은 i번째, B문자열은 j번째 글자까지 비교했을 때의 최장 공통 부분 수열의 길이

예를 들어, ABCD와 BACD를 비교한다고 생각해보자.

(3,3) 값을 보면 2라는 값이 나오는데, 이는 BAC와 ABC를 비교한 값이다. 

dp에는 이전 까지 저장된 최장 공통 부분 수열의 길이를 저장하고 A문자열 i번째와 B문자열 j번째가 같으면 +1을 해주면 된다.

A문자열 i번째와 B문자열 j번째가 같지 않더라도 이전까지 구한 값이 최장 공통 부분 수열이기 때문에 (i-1,j)와 (i,j-1) 중에서 최대값을 저장하면 된다.

만약, LCS의 문자열을 구해야 한다면, (i,j)부터 회색으로 색칠된 부분의 문자열만 추가하는 방식으로 진행하면 될 것이다.

이를 코드로 구현하면 다음과 같다.

* Sharding(샤딩)

샤딩은 수평 분할(Horizontal Partitioning)과 동일하며, 인덱스의 크기를 줄이고, 작업 동시성을 늘리기 위한 것이다.

수평 분할(Horizontal Partitioning)이란 스키마(schema)가 같은 데이터를 두 개 이상의 테이블에 나누어 저장하는 디자인을 말한다. 

가령 같은 주민 데이터를 처리하기 위해 스키마가 같은 '서현동주민 테이블'과 '정자동주민 테이블'을 사용하는 것을 말한다. 

데이터베이스를 샤딩하게 되면 기존에 하나로 구성될 스키마를 다수의 복제본으로 구성하고 각각의 샤드에 어떤 데이터가 저장될지를 샤드키를 기준으로 분리한다.

* Sharding(샤딩)의 단점

프로그래밍적, 운영적인 복잡도가 높아진다. 

즉, 샤딩을 시작하기 전에 샤딩을 피하거나 지연시킬 수 있는 방법을 찾는게 우선이다.

1. 좀더 고스펙의 컴퓨터를 사용한다.

2. Read(Select) 명령이 많다면 Cache나 Database Replication을 적용한다.

3. Table의 일부 Column만 사용한다면 수직 분할(Vertically Partitioning)을 사용한다 / Cold & Hot data를 사용한다.

참고) Database Replication이란?

2개 이상의 DBMS를 Master와 Slave로 나누어 동일한 데이터를 저장한다.

Master DB는 Insert, Update, Delete의 기능을 수행하고, Slave DB에 실제 데이터를 복사한다.

Slave DB 시간이 오래걸리는 Select문의 기능을 수행하여 전체적인 Select문 성능을 향상시킨다.

참고) Cold / Hot Data 란?    Naver D2 :: Cold Storage 소개

Hot data : 자주 사용되는 데이터 

Cold data : 드물게 사용되거나 아예 사용되지 않는 데이터

Cold Storage : 에너지 절감을 위해 연산 능력에서 손해를 보더라도 낮은 가격과 저전력으로 자주 사용되지 않는 데이터를 처리하는 데이터 저장 장치 및 시스템 

* Sharding(샤딩)의 주요 관점

분산된 DB에서 어떻게 Data를 읽어올 것인지?

분산된 DB에 Data를 어떻게 잘 분산시킬지?

>> Shard Key를 어떻게 정의하는지에 따라 달라진다.

Case 1. Algorithm Sharding

Database id를 단순하게 나누어 샤딩하는 방식

Sharding Key는 hash(key) % NUM_DB 같은 방식

* 장점

같은 값을 가지는 key-value 데이터베이스에 적합하다.

* 단점

Cluster를 포함하는 Node 갯수가 변하게 되면 Resharding이 필요하다.

Hash Key로 분산되기 때문에 공간에 대한 효율이 부족하다.

Case 2. Dynamic Sharding

클라이언트는 Locator Service에 접근하여 Shard Key를 얻는다.

* 장점

Cluster가 포함하는 Node 갯수가 변하면 Shard Key를 추가하기만 하면 된다.

>> 확장에 유연하게 대처가능하다.

* 단점

Data Relocation시에는 Locator Service의 Shard key Table도 일치시켜야 한다.

Locator에 의존할 수 밖에 없는 구조이다.

Case 3. Entity Group

RDBMS의 Join, Index, Transaction을 사용하여 복잡도를 줄이는 방식과 유사

동일한 파티션의 관련 엔티티를 저장하여 단일 파티션 안에서 추가 기능을 제공하는 방식

* 장점

하나의 물리적인 Shard에 쿼리를 진행하면 효율적이된다.

사용자의 증가에 따른 확장성이 좋은 파티셔닝이다.

* 단점

특정 파티션간 쿼리가 자주 요구되는 경우가 있다.

* 참고자료

Database의 샤딩(Sharding)이란?

How Sharding Works

* 핵심

nCr = (n-1)C(r-1) + (n-1)Cr 공식을 이해한다.

1을 선택했을 때의 경우의 수 (n-1)C(r-1), 1을 선택하지 않았을 때의 경우의 수 (n-1)Cr

* 문제

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

* 소스 코드