[자료구조] 1-1. 추상자료형 및 알고리즘의 성능 분석

## 자료구조

자료구조는 컴퓨터에 저장되는 데이터가 사용자가 어떻게 편하고 효율적으로 사용할 수 있을지 정리하는 것이다. 모든 자료마다 적합한 구조가 있다.

책장에 정리된 책의 모습이 있다면 그 책은 장르의 코드 별, 제목의 순서 별로 정리가 되어 있을 것이다. 그 책 속 또한 목차를 통해 정리가 되어 있다.

혹은 지하철 노선도가 사람들이 직관적으로 알아보기 편리한 형태인 선형으로 정리되는 것 등 이러한 것들을 통틀어 자료구조라고 일컫는다.

자료의 컴퓨터 저장

모든 데이터는 0과 1로 저장된다.

컴퓨터에서 단순 자료는 프로그래밍 언어의 데이터 형식에 해당하는 정수, 실수, 문자, 문자열 등으로 나눈다

• 정수: 0, 100, -10 등 (소수점이 없는 음수, 0, 양수, Int또는 Integer)
• 실수: 0.1, 3.14, 4.5 등 (소수점 있는 형태, float)
• 문자: “A’, ‘1’, ‘가’ (한 문자, char로 표현)
• 문자열: “서울”, “A123”, “나” 등 (한 문자 이상, string으로 표현, 주로 큰따옴표로 묶음)

선형(linear)자료구조

• 항목들을 순서적으로 나열하여 저장
• 항목 접근 방법
  • 리스트: 가장 자유로운 선형 자료 구조
  • 스택, 큐, 덱: 항목의 접근이 맨 앞이나 맨 뒤로 제안됨

비선형(Nonlinear) 자료구조

• 항목들이 보다 복잡한 연결 관계를 가짐
• 트리: 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조
• 그래프: 가장 복잡한 연결 관계를 표현

알고리즘

알고리즘이란 컴퓨터가 문제를 풀기 위한 단계적인 절차를 의미한다.

하나의 일을 컴퓨터가 이해할 수 있도록 정밀하게 컴퓨터가 이해할 수 있는 언어로 기술한 것

프로그램 = 자료구조 + 알고리즘

알고리즘의 조건

• 입력: 0개 이상의 입력이 존재해야 함
• 출력: 1개 이상의 출력이 존재해야 함
• 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 함
• 유한성: 한정된 수의 단계 후에는 반드시 종료되야 함
• 유효성: 각 명령어는 실행 가능한 연산이어야 함

알고리즘의 기술 방법

• 자연어
  • 일반적인 언어를 사용해 설명하듯 표현
  • 일반 사람이 이해하기 쉬우나 코드로 변경하기에는 어려움
  • 어떤 알고리즘을 사용해야 할지 아이디어가 떠올즤 않을 때 사용하면 무난
• 흐름도
  • 여러 종류의 상자와 상자를 이어 화살표를 이용해 명령
  • 간단한 알고리즘은 쉽게 표현하나 복잡한 알고리즘은 어려움
• 유사코드
  • 프로그래밍 언어보다 좀 더 인간의 언어에 가까움
  • 프로그램 코드와 일반 언어의 중간 형태
  • 프로그램 코드를 직접 코딩하는 것 보다 알고리즘을 좀더 명확하게 정립가능
• 특정언어
  • 실제로 사용하는 언어로 작성
  • 알고리즘 정확히 기술 가능
  • 구현시 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해

추상자료형

추상 자료형은 구체적이지 않은 데이터를 말한다.

• 데이터와 그 데이터에 대한 추상적인 연산들로 구성
  • 데이터나 연산이 무엇(what)인가를 정의함
  • 데이터나 연산을 어떻게(how) 구현할 것인지는 정의하지 않음

Bag의 추상 자료형

데이터: 중복된 항목을 허용하는 자료들의 저장소, 항목들은 특별한 순서가 없이 개별적으로 저장되지만 항목간 비교는 가능해야함

연산

1. Bag(): 빈 가방을 생성함
2. insert(e): 가방에 항목 e를 넣음
3. remove(e): 가방에 e가 있는지 검사하여 있으면 이 항목을 꺼냄
4. contians(e): e가 들어있으면 true, 없으면 false
5. count(): 가방 안에 들어있는 요소의 개수를 반환