검색 알고리즘을 체험해보자

1. 검색 알고리즘

• 일상에 있는 다양한 알고리즘 중 대표적인 것 중 하나

처리 속도와 하드웨어의 관계

• 입력받은 데이터를 알고리즘에 따라 유익한 정보로 변화 및 출력하는 것을 데이터 프로세싱이라하는데 컴퓨터가 프로그램으로 구현된 알고리즘에 따라 데이터를 처리하는 데이터 프로세싱 머신이다.
• 알고리즘의 유한성을 만족하려면 효율적인 알고리즘 만들거나 하드웨어의 성능을 더 좋게 해야함

무어의 법칙이 예언하는 미래

• 무어의 법칙은 반도체의 집적도가 18개월 마다 두배가 된다하여 이를 CPU의 속도와 메모리의 용량에도 적용 가능

빅데이터를 위한 처리 성능

• 빅데이터를 효율적으로 처리하기 위해 컴퓨터는 스케일 업 / 아웃으로 처리 성능 높임
  - 스케일 업은 컴퓨터 한대의 CPU나 메모리 보강해 처리 성능 올리는 것, 단 CPU 속도 높이고 메모리 높이는데 물리적 제한 존재
  - 스케일 아웃은 컴퓨터 자체의 대수를 늘려 처리 성능을 높이닌 기법, 물리적 제한 없음
• 스케일 아웃에는 클러스터링 기술 사용되는데 이는 파이버 채널 같은 고속네트워크로 여러대의 컴퓨터를 연결하여 마치 한 대의 컴퓨터처럼 사용하면서 빠르게 처리하는 기술
  - 처리 속도 향상은 물론 가용성 향상에도 기여

맵리듀스를 통한 분사처리

• 빅테이터를 처리하는 시스템, 맵리듀스는 클러스터링된 컴퓨터로 대량의 데이터를 분산 처리하고자 고안한 프로그래밍 모델
• 클러스터링된 컴퓨터를 병렬로 동작시켜 데이터베이스나 파일에 저장돼 있는 빅데이터 처리
  - 입력받은 데이터를 맵 페이즈에서 작은 단위로 쪼개 필요한 정보를 모음 => 결과를 리듀스 페이즈에 묶어 처리 결과를 출력
  • 맵과 리듀스 페이즈는 병렬 처리 가능해 클러스터링한 컴퓨터로 분산시켜 병렬로 실행해 빠른 처리 가능

2. 단순한 검색 알고리즘

1. 선형 검색

• 데이터 여러개에서 데이터가 나올 때까지 처음부터 차례로 검색하는 알고리즘, 리니어 서치라고도 함
• 단점은 데이터 양이 많아질수록 원하는 데이터를 찾기 까지 시간이 걸림
• 선형 검색에서 최악의 경우의 수(끝까지 발견 안되는 경우) 최대 검색 횟수라고 하는데 최대 검색 횟수를 N회로하면 평균 검색 횟수는 n/2회 검색량은 O(n)이 된다.

2. 이진 검색

• 바이너리 서치라고 부르며, 검색 범위를 반으로 나누어 원하는 데이터를 찾을 때까지 계속 검색
• 데이터는 어떤 기준에 따라 오름차순이나 내림차순으로 정렬되어 있어야 함
• 원하는 데이터를 찾을 때까지 검색할 데이터 범위를 반씩 줄여가며 찾는 알고리즘으로 선형 검색보다 효율적이ㅣ만 대소 관꼐를 이용하기에 정렬되지 않은 데이터는 검색 불가
• 이진 검색 최대 검색 횟수는 log2n + 1 회 평균 검색 횟수는 log2n회

3. 더욱 수준 높은 검색과 자료 구조

처리속도를 좌우하는 자료구조

• 선형 검색과 이진 검색이라 기본 검색 알고리즘을 알아보았며, 처리를 하려면 데이터를 저장하는 방법도 중요
• 데이터를 다루기 위해 일정한 형식에 맞춰 체계적으로 저장
  - 어떻게 데이터 저장하는지에 따라 처리 시 효율성이 크게 달라지기 때문
  • 이러한 데이터 저장 형식을 자료구조라 부름

3_1. 트리구조

• 나무 구조라고도 부르며 데이터가 나뭇가지처럼 서로 연결되어있는 구조
• 트리 구조 구성하는 요소는 노드라고 부르면 노드끼리 부모 자식 관계를 갖는다.
  - 부모 노드가 없는 맨 위 노드를 루트 노드, 자식 노드가 없는 가장 아래의 노드를 리프 도르가 부름
  • 부모 자식 관계에 있는 노드는 선으로 열결되며이 선을 엣지라고 하며 루트 노드부터 리프 노드까지 계층을 트리 높이라고
• 트리 구조는 루트 노드에서 여러 개의 엣지를 거쳐 노드를 경유하면서 리프 노드에 도달하는 자료 구조

트리 구조 종류

• 자식 노드의 개수가 2개로 제한된 트리 구조는 이진 트리, 자식 노드가 N개 이상인 트리 구조는 N항 트리라 부름
• 그리고 자식 노드가 3개 이상인 트리 구조를 총칭해서 다중 트리라고 부름

이진 트리 검색의 메커니즘

• 트리 구조가 검색에 어떻게 도움이 되는 지
• 이진 트리 중 왼쪽 자식 노드 값이 부모 노드 값 보다 작고, 오른쪽 자식 노드 값이 부모 노드 값 보다 크게 성 된 트리 구조를 가리켜 이진 탐색 트리라고 부름
• 이진 탐색 트리는 데이터를 크기에 따라 나눈 구조를 가져 이 형식을 활용하면 간단한 절차로 이진 검색 가능

  1. 루트 노드를 비교 대상으 노드로 정하고 검색 시작

2. 비교 대상 노드가 없으면 종료
3. 비교 대상 노드와 검색하려는 데이터 비교하여 값이 같으면 종료(발견)
4. 검색하고자 하는 데이터보다 비교 대상 노드 값이 크면 비교 대상 노드를 왼쪽 자식 노드로 지정하고 그렇지 않으면 비교 대상 노드를 오른쪽 노드로 지정
5. 다시 2로 돌아감

AVL 트리의 메커니즘

• 트리 구조 고안 시 주의해야 하는 사항 있는데 트리 구조 높이에 따라 효율이 달라진다는 점
• 실제 현장에서 트리 구조에 데이터 추가하거나 삭제해야 하는 상황이 자주 발생하는데 맹목적으로 데이터를 추가하거나 삭제하면 효율이 매우 나빠짐
• 높이가 일정하면 스텝의 개수는 줄지만 일정하지 않은 경우 선형을 이루게 되면서 스텝의 개수는 선형 검색과 같은 개수가 되어 효율이 매우 나빠짐
• 따라서 AVL (adelson-velskii and landis' tres)라는 자료구조를 기억해야하는데 AVL 트리는 한 노드를 중심으로 좌우 부분 트리의 높이 차가 1 이하인 이진 탐색 트리로 이진 탐색 트리의 성질을 해치지 않으며 데이터 추가 시 트리 높이가 변경되면 AVL 트리의 조건에 따라 트리를 다시 구성해 트리의 높이를 일정하게 유지 가능
• 이렇게 이진 탐색 트리의 조건을 해치지 않으면서 트리를 변형시키는 작업을 가리켜 트리 회전이라 부름

균형 트리와 B트리

• 루트 노드에서 가장 아래 있는 리프 노드까지 높이가 일정하도록 만들어진 트리 구조를 균형 트리라고 부름
• AVL 트리도 평균 트리며 이진 탐색 트리이기도 하므로 일종의 균형 이진 탐색 트리
• B 트리는 다중 트리이면서 균형 트리 구조를 가진 트리 구조로 노드 하나가 자식 노드(다중 트리) 3개 이상 가질 수 있으며 어떤 리프 노드에서도 트리의 높이가 거의 같다(평균 트리)는 특징 가짐
• 노드의 대소 관계는 이진 트리와 같아 왼쪽 자식 노드 값은 부모 노드 값보다 작고 오른쪽 자식 노드 값은 부모 노드 값보다 큼

데이터 개수가 늘어날수록 빨라지는 B트리

• B 트리의 또 다른 특징으로 데이터 개수가 늘어날수록 빨라진다는 점
• 저장하는 데이터 개수 m으로 하면 오더가 O(logmN)이 되어 B트리는 빠르게 검색할 수 있으므로 데이터베이스나 파일 시스템에 자주 이용

• 참고로 도메인 이름도 트리구조