[시스템디자인&인터뷰] 2. 알고리즘과 데이터 구조

시스템 디자인 및 디자인

목적 : 기업의 비즈니스 모델에 효율적인 아키텍처를 고안하기 위한 능력 배양 

 

목차

1. 확장 가능한 시스템 설계

2. 알고리즘과 데이터 구조 

3. 빅데이터를 활용한 작업

4. 설계 인터뷰 전략 

5. 모의 설계 인터뷰 

7. 일반적인 기술 인터뷰 팁 

 

ref) 

http://media.sundog-soft.com/SystemDesign/SystemDesign.pdf 

 

알고리즘과 데이터 구조 

시스템 설계의 관점에서 데이터 구조 및 알고리즘을 바라볼 수 있어야 한다. 

 

1. 연결 리스트 

단일 연결 리스트

- 동적으로 데이터를 붙일 수 있음에 의미를 가진다. 

- 접근, 헤드에 삽입, 테일에 삽입의 시간복잡도를 고려하면 Stack, Queue 구조에 적합  

- 장점은 노드당 하나의 포인터만 있으면 되므로 메모리를 적게 사용한다. 

 

2. 이진트리, 해시 테이블 

이진트리는 자식노드를 2개 가지며, 이는 순서에 따라 정렬될 수 있다. ( 부모 보다 작은 값은 왼쪽으로 등 )

- 접근시간 O(logN) 이지만, 최악의 경우 ( 왼쪽 자식으로만 쭉 뻗은 꼴 )은 O(N)이 걸린다.  

- 삭제,수정 = O(logN) , 또한 트리를 재배열하는데 시간이 걸린다.  

해시 테이블은 최악의 경우 ( 해시 충돌, 혹은 하나의 버킷에 모두 매핑되는 경우 ) O(N)의 접근, 삭제가 걸릴 수 있다. 

 

해시 테이블의 활용 :

- 1. 전체 클러스터에서 해당 데이터가 어디 있는지 해시함수를 통해서 찾을 수 있어야 한다.

- 2. 해시함수 결과를 따라 실제 데이터를 획득해야 한다. 

 

3. 그래프 및 순회법

 

 

4. 검색 및 분류 알고리즘 

 

 

5. 정보 검색, 전문 검색 

 

엘라스틱 서치 같은 경우 검색이 어떻게 되는지 알아야 한다. 

 

일반 색인 (Forward Index)

- 키워드를 각 문서, 위치 튜플에 매핑한다. 

- 여기서 키워드는 n-그램 이라고 한다. 검색에 사용되는 2개 이상의 단어 이다. 

- 역색인( inverted index ) 문서에 키워드를 매핑을 만들 수 있다. 

- *Palm tree > 문서 432 번에 있다. > 문서 432번은 1번, 55번 위치에 해당 키워드가 나온다. 

TF-IDF ( 단어 빈도 대 문서 빈도 )

TF-IDF : 단어의 빈도 - 리버스 문서의 빈도 뜻 

- 단어 빈도 : a, the, and 등을 제외한 특정 키워드가 하나의 문서에 얼마나 나왔는지 카운트

- 리버스 문서 빈도 : 위에서는 문서당 단어수를 봤었다.

-  *반대로 단어당 문서들을 볼 수 있고,

-  *다른 문서와 달리 해당 단어가 특정 문서에만 높은 빈도로 나온다면 TF-IDF는 높은 점수가 나온다.  

 

하지만, 모든 문서를 수집해서 단어수를 파악하고 단어에 문서를 매핑하는 작업은 현실적으로 어렵다. 

구글이 독창적으로 만든 PageRank라는 개념이 있다. 

 

PageRank ( 백링크 계산 )

페이지 랭크는 문서의 a 태크 (링크)를 보고 점수를 매기는 방식이다. 

- 백링크 : 어떠한 다른 페이지에서 이 페이저로 이어지는 링크 

- 이러한 '인바운드' 링크 ( 쉽게 생각해서 참조 자료에 내 사이트가 많이 언급되면 좋은 것 ) 가 많을수록 유용

- d라는 감쇄계수값이 있으며, 첫번째 페이지 / 첫번째 페이지의 백링크 수 부터 더해 나간다. 

 

요즘에는 TF-IDF, PageRank 방식보단 딥러닝 활용하여 검색순위를 매긴다.