Hello Coding 알고리즘

11. 더 공부해야 할 것

1. 트리 tree

• 이진 탐색 트리 binary search tree
  • 이진 탐색 사용 시, 삽입/삭제마다 배열을 다시 정렬해 사용해야 함.
    • 이진 탐색은 정렬된 배열에서만 쓸 수 있기 때문
  • 이진 탐색 트리는 사용자 이름을 올바른 위치에 바로 넣기 위해 탄생함
  • 모든 정점에 대해 왼쪽에는 더 작은 값을 가진 정점, 오른쪽에는 더 큰 값을 가진 정점이 온다.
    • 작은 값, 큰 값의 기준 = 정렬의 기준 (숫자-작은 순, 영어-알파벳순..)
  • 장점 : 탐색, 삽입, 삭제에 모두 O(log n) 시간이 걸린다.
  • 단점 : 임의 접근(random access)를 할 수 없다, 평균 성능이 트리의 균형도에 따라 달라짐.
• 레드-블랙 트리 red-black tree
  • 스스로 균형을 맞추는 이진 탐색 트리.
• B-트리 b-tree
  • 데이터베이스에서 데이터를 저장할 떄 흔히 사용
• 그 외에 힙 heaps, 스플레이 트리 splay trees 가 있음

2. 역 인덱스 inverted index

• 주로 검색엔진을 만드는 데 사용
• 키 : 단어, 값 : 그 단어가 있었던 웹 페이지.
• 만약 어떤 단어로 검색을 한다면, 검색엔진은 그 단어가 있었던 웹 페이지를 보여줌
• 검색에 관심이 있다면 이 분야를 공부하기.

3. 퓨리에 변환 fourier transform

• 아주 뛰어나고 엄청나게 많은 응용 분야를 가지는 알고리즘
• "퓨리에 변환을 사용하면 스무디가 무슨 성분으로 구성되어 있는지 알아내는 것처럼 하나의 노래를 여러 개의 개별적인 주파수들로 분리할 수 있다"
• 사용 분야
  • 노래를 주파수별로 분리 - mp3포맷 변환. 음악 압축.
  • jpg압축도 같은 원리
  • 지진 발생 예측
  • DNA 분석
  • Shazam - 노래 검색 앱에서도 사용

4. 병렬 알고리즘 parallel algorithm

• 빅 데이터를 다루는 알고리즘 1
• 컴퓨터에 여러 코어가 탑재되면서, 알고리즘을 병렬 실행할 수 있게 됨
• 하지만 병렬 알고리즘을 설계하는 것이 어려움 (속도 향상이 선형적이지 않음)
  • 설계가 어려움
  • 올바르게 동작하는지 확인이 어려움
  • 어느 정도 빨라졌는지 확인이 어려움
• 1코어에서 돌리던 알고리즘을 2코어에서 돌린다고 해서 속도가 2배 빨라지는 것은 아님
  • 병렬화를 관리하는 데 들어가는 부담 : 병렬로 처리한 일을 다시 합치는 데도 시간이 걸림 & 무작정 합칠 수 없음
  • 로드 밸런싱 : 2 코어에 작업을 균등하게 분배하기가 어려움
• 만약 성능과 확장성에 관심이 있다면 병렬 알고리즘 공부하기.

5. 맵리듀스 MapReduce algorithm

• 분산 알고리즘 distributed algorithm : 병렬 알고리즘의 하나.
  • 수백 대의 코어, 여러 대의 컴퓨터에서 돌릴 수 있는 알고리즘.
  • 작업량이 많고 실행시간을 단축시키고 싶을 때 사용
• 맵리듀스 알고리즘 MapReduce algorithm : 인기 있는 분산 알고리즘.
  • 맵 함수map function와 리듀스 함수reduce function 이라는 두 개념을 이용해 만들어짐
  • 맵 함수와 리듀스 함수를 이용해, 여러 대의 컴퓨터에 분산되어 있는 데이터에 대한 질의를 수행함.
  • 일반 DB에서 몇 시간이 걸리는 작업을 몇 분만에 수행할 수 있음.
  • 아파치 하둡 Apache Hadoop과 같은 오픈소스 툴을 통해 맵리듀스 알고리즘을 쓸 수 있음.

맵 함수 map function

• 배열을 입력으로 받아, 모든 원소에 같은 함수를 적용함

arr1 = [1, 2, 3, 4, 5]
arr2 = map(lambda x: 2 * x, arr1)
## [2, 4, 6, 8, 10]. 모든 원소를 2배로 만듦

• 맵 함수는 어떤 작업을 모든 컴퓨터에 골고루 배분하는 역할을 한다.

리듀스 함수 reduce function

• reduce = 리스트 전체 원소를 하나의 원소로 축소한다.

arr1 = [1, 2, 3, 4, 5]
reduce(lambda x,y: x+y, arr1)
## 15. 모든 원소를 합쳐 하나로 만듦

6. 블룸 필터, 하이퍼로그로그

• 구글 검색 서비스 운영을 위해 웹 페이지를 크롤링한다. 이 때, 전에 찾아본 적 없는 웹 페이지만 크롤링하려 한다.
• 해시테이블에 키:주소, 값:O/X 로 넣으면 된다.
• 문제 : 해시 테이블이 너무 커진다. 어마어마한 저장공간이 필요

블룸 필터 bloom filter

• 확률론적인 자료구조
• 거의 대부분 옳은 답을 주지만, 항상 그렇지는 않다.
  • 틀린 답을 맞다고 할 수도 있다.
    • "이 사이트는 이미 크롤링했습니다" = 크롤링하지 않은 사이트일 수도 있다.
  • 하지만, 맞는 답을 틀리다고 하지는 않는다.
    • "이 사이트는 크롤링하지 않았습니다" = 진짜 크롤링한 적 없는 사이트이다.
• 장점 : 공간을 아주 적게 차지한다

하이퍼로그로그 HyperLogLog

• 역시 확률론적인 자료구조
• 집합에 있는 똑같은 원소의 개수를 대략적으로 셀 수 있다.
  • 정확한 값은 아니지만 꽤 근사한 값을 준다.
• 구글에서 사용자 검색내역 중 특정 검색어에 대한 검색횟수를 세고 싶다면?
  • 모든 검색 로그를 저장해야 하므로 어마어마한 저장공간이 필요..
  • 이럴 때 하이퍼로그로그를 대신 사용할 수 있다.

7. SHA 알고리즘

• 해시 테이블을 만들기 위한 해시 함수에 사용할 수 있다
• 해시 함수는 좋은 분포 특성을 가져야 한다.
• SHA알고리즘 (보안 해시 알고리즘 : Secure Hash Algorithm)
  • 해시 함수의 일종
  • 문자열을 받아 그 문자열에 대한 해시값을 반환
  • hello => 2cf24db.....
• SHA는 단방향 해시이다.
  • 문자열을 해시값으로 변환할 수 있지만, 해시값을 문자열로 되돌릴 수는 없다.
• SHA의 활용
  • 두 파일이 같은지 비교할 수 있다 : 두 파일의 SHA코드를 비교, 같다면 같은 파일
  • 패스워드 비교 : 패스워드에 대한 해시값만 저장해 두고, 사용자가 비밀번호 입력시 입력값의 해시값과 일치하는지 비교한다.
    • (실제 비밀번호를 저장하지 않는다)

8. 지역 민감 해싱, Simhash

• 원래 해시 함수는 입력 문자열에서 조금만 달라져도 출력 해시값이 크게 바뀐다.
• 하지만 반대로 문자열이 조금만 바뀌면 해시값도 조금만 바뀌어야 할 때도 있다.
  • 해시값만 보고도 두 문자열이 어느 정도 비슷한지 알 수 있다.
• 비슷한 항목을 찾아낼 때 유용하다.
• 이럴 때 지역 민감 해시 locality-sensitive hash인 Simhash를 사용!
• 사용 예
  • 구글 : 크롤링할 웹 페이지가 중복되었는지 판단함
  • 유사도검사 : 과제가 인터넷에서 배낀 것인지 알 수 있음

9. 디피-헬만 키 교환 Diffie-Hellman algorithm

• 암호화 알고리즘 중 하나.

  • 양쪽 모두 암호 해독 규칙을 가직 필요가 없다.
  • 암호화된 메시지를 해독하기 어렵다.

• 두 개의 키를 가진다.

  • 공개 키 public key : 누구에게나 공개되는 키 - 내게 보내진 메시지는 공개 키로 암호화되어 보내짐
  • 개인 키 private key : 나만 가지고 있는 키 - 암호화된 메시지를 해독하기 위해 필요

• 후속 알고리즘 - RSA

• 만약 암호학에 관심이 있다면 이 분야를 공부해 보기.

10. 선형 프로그래밍 linear programming

• 주어진 조건하에서 무언가를 최대화할 때 사용
• 그래프 알고리즘이 선형 프로그래밍의 한 경우에 해당함.
• 만약 최적화에 관심이 있다면 이 분야를 공부해 보기.