[박혜웅] 자료구조(data structure) 및 알고리즘(algorithm)의 종류

• 자료구조의 정의

  • 자료원소들 간의 논리적 관계를 기술
  • 자료 값에 대한 연산을 효율적으로 처리할 수 있도록 조직적(체계적)으로 구성한 것

 

• 자료구조 비교

  • 탐색
  • 삽입/삭제
  •  순회

 

• 자료구조의 분류

  • 배열

    • 배열: 순차탐색
    • 정렬된 배열: 이진탐색

  • 리스트

    • 연결리스트: 순차탐색

  • 트리

    • 이진트리: 이진탐색

  • 탐색트리

    • B트리: 이진탐색 또는 다중탐색
    • B+트리: 이진탐색 또는 다중탐색
    • B*트리 : 이진탐색 또는 다중탐색

  • 디지털트리

    • 이진트라이: 기수탐색
    • 패트리샤트리: 기수탐색

  • 사전구조(dictionary)

    • 해시
    • 요약파일
  • 집합

 

• 알고리즘

  • 어떤 문제를 해결하기 위해 기술해 놓은 명확한 절차, 일련의 명령(instruction 또는 step) 집합을 의미

 

• 검색 알고리즘

  • 검색 알고리즘의 용도

    • 텍스트내에 발견되는 질의(정규식)의 최초위치 탐색
    • 텍스트내에 발견되는 모든 질의의 위치 또는 회수 탐색

• • 검색 알고리즘의 종류

  • • 색인을 사용하지 않는 경우

      • 문자열 탐색

    • 색인을 사용하는 경우

    • • 역파일, 요약파일

 

 

• 여과(filtering) 알고리즘

  • 여과 알고리즘의 용도

    • 색인 알고리즘 전에 사용
    • 텍스트를 표준화 시켜 텍스트의 크기를 줄이거나 탐색을 단순화함.

  • 여과 알고리즘의 종류

    • 불용어목록(stoplist)

      • 불용어를 제거함=일반적인 단어만 남김
    • 대소문자변환
    • 특수기호/연속공백 제거
    • 숫자/날짜 표준화
    • 스테밍= 접두사(접미사) 제거

 

• 색인 알고리즘

  • 색인 알고리즘의 용도

    • 빠른 탐색을 위한 자료구조를 만드는것.

  • 색인 알고리즘의 종류

    • 역파일
    • 요약파일
    • 트리