IT 일반

자료구조와 알고리즘

자료구조의 정의

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

 

  • 자료구조 성능 비교

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

 

  • 자료구조의 분류

    • 배열

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

      • 연결리스트(Linked List) : 순차탐색
    • 트리

      • 이진트리: 이진탐색
    • 탐색트리

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

      • 이진트라이: 기수탐색
      • 패트리샤트리: 기수탐색
    • 사전구조(dictionary)

      • 해시
      • 요약파일
    • 집합

 

  • 알고리즘

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

 

  • 검색 알고리즘

    • 검색 알고리즘의 용도

      • 텍스트내에 발견되는 질의(정규식 표현)의 최초위치 탐색
      • 텍스트내에 발견되는 모든 질의의 위치 또는 회수 탐색
 
  • 여과(filtering) 알고리즘

    • 여과 알고리즘의 용도

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

      • 불용어목록(stoplist)

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

 

  • 색인 알고리즘

    • 색인 알고리즘의 용도

      • 빠른 탐색을 위한 자료구조를 만드는것.
    • 색인 알고리즘의 종류

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

댓글

댓글 본문
작성자
비밀번호
버전 관리
휴먼밸
현재 버전
선택 버전
graphittie 자세히 보기