" /> 자료 구조론 3주차 - 데이터 구조와 알고리즘 그리고 String | BlackWerf's Blog
포스트

자료 구조론 3주차 - 데이터 구조와 알고리즘 그리고 String

게시
By Junhyuk Son 6 분읽는 시간

3주차

데이터 타입

정의

  • 컴퓨터 내부에 데이터를 저장하는 방식
  • 좋은 데이터 구조를 가진 프로그램은 효율적인 프로그램임


종류

  • Array
  • Record
  • Stack
  • Quee
  • List
  • Tree(General, Binary, Special(B, B*, B+))


기초 데이터 구조

  • 정수형
  • 문자형
  • 실수형
  • 논리형
  • 포인터형


데이터 구조의 분류

타입대상
단순형태String, Array, Record
복합(선형)Stack, Queue, List
복합(비선형)트리(일반, 이진, 특수), 그래프


파일 구조

Direct
  • 데이터를 저장장치에 물리적 순서대로 저장하는 방식
Sequential
  • 레코드의 키 값을 연산 루틴의 입력으로 받고, 연산 결과를 그 키 값을 갖는 레코드의 주소가 되도록 파일을 저장하는 방식
  • 해싱 필수
  • HF(레코드 키 값) -> 주소(Adress)
Indexed Sequential
  • 파일이 인덱스와 순차 데이터 영역으로 구성됨
  • 데이터에 대한 접근은 2가지 방식이 모두 가능함 1) 순차 접근 1) 인덱스를 통한 임의 접근
  • 정렬을 할 경우 이분법 이 가능하며 효율이 향상됨
    • 이분법: 데이터를 탐색영역 2개로 나누는 것


알고리즘

정의

  • 주어진 특정 문제를 해결하기 위한 유한 집합
    • 예시: 이름과 전화번호를 쌍으로 하는 리스트에서 이름을 받아 전화번호를 찾는 알고리즘

특징

  • 리스트의 저장 구조에 의존함

만족해야 할 조건

  • 입력과 출력
  • 명확성
    • 명령어의 모호성을 제거함
  • 유한성
  • 효과성
    • 실행이 가능해야 함

표현 방법

  • 자연어 표현
  • 플로우 차트
  • 슈도코드



기초 데이터 구조

수치 데이터

정수
실수

비수치 데이터

문자 데이터
ASCII(7bit)
EBCDIC(8bit)
논리 데이터
  • 논리 데이터 사용(True, False)


String

정의

  • 일련의 문자

용도

  • 프로그램의 기본 매개체
    • Label, Identifier, Reserved Word, User-Defined Word….
  • 문서의 기본 매개체

종류

순차 String(비압축)
정의
  • 연속된 문자들을 연속적인 Word에 표현하는 방식
  • 하나의 Word에 1개의 문자를 표현함
장점
  • 빠른 저장 속도
단점
  • 비압축 방식이므로, 기억 장소의 효율성 저하
예시

  • S = ‘DATA’

  • 표현 방식:

    1

    oooDoooAoooToooA
고정길이 순차 String
압축 String
  • String을 연속적인 word에 표현하는 방식
  • 하나의 워드에 2개 이상의 문자를 표현함
    • 효율적인 메모리 활용이 가능함

  • 예시

    • S=”DATA”

      1

      |D|A|T|A|/| | | | | | | | | | | |
연결 리스트

  • 연결된 블록을 사용함

    • 각 블록은 문자들을 포함하고 있음

  • 하나의 블록은 2 영역으로 구분이 가능함

    • 데이터 영역: 문자(들)을 포함함
    • 링크 영역: 다음 문자를 포함하는 블록의 주소를 포함

  • 비연속적 기억 장소인 블록들에 문자들을 저장함

  • 포인터 사용으로 인해 메모리 사용량이 저하됨

  • String의 길이 변화 연산에 매우 유용함

    • 예시) 삽입, 삭제, 서브 String

  • 예시) S=”DATASTRUCT”

    Image Alt 텍스트

가변길이 String
  • String 길이가 가변적임
관련 연산
  • 결합
    • 2개의 String을 연속적으로 연결한 하나의 합성된 String을 생성함
  • 삽입
    • String을 구성하는 2개의 문자 사이에 새로운 String을 추가
  • 삭제
    • String을 구성하는 문자들 중 하나 이상의 문자를 제거
  • 교체
    • String을 구성하는 문자를 다른 문자로 변경함
  • 서브 String
    • String을 구성하는 연속된 문자들 중에서 일부를 찾아 새로운 String을 생성함
  • 인덱싱
    • String 내에서 어떤 문자나 서브 String의 위치를 정수로 반환함
    • 해당되는 문자가 없을 경우 0을 출력함
    • 여러개가 존재 할 경우 최초의 값을 출력함
  • 패턴 매칭 연산
    • String 중 지정된 서브 String을 탐색함
      • 값이 존재하면 True, 없으면 False를 반환함


  • 모두 연속된 Word라는 공통점이 존재함
  • 처리시간, 메모리 효율, 작업의 편리성 등을 고려해 사용함
학교 공부, 자료 구조론
23-2 자료구조론
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.