본 피드는 '쉽게 배우는 자료구조 with Java'를 읽고 요약한 글입니다.
자료구조란?
자료구조는 자료(데이터)에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 관한 이론이다.
알고리즘은 문제 해결작업을 수행하기 위해 입력을 받아 출력을 만들어 내는 과정을 기술한 것을 의미한다.
자료구조는 이 과정에서 부품과 같은 역할을 한다.
자료구조 관련 클래스 (Collection Package)
자바에서는 다양한 자료구조를 가져다 쓰기 쉽게 자료구조와 관련된 클래스들을 모아놓은 패기지가 있다.
우리는 이 패키지를 컬랙션 패키지라고 부른다.
이 책에서 다루는 자료구조는 리스트, 스택, 큐, 검색트리(이진 검색트리, 균형 검색트리), 힙, 해시 테이블, 그래프이다.
알고리즘의 표기법
1. 자연어를 이용한 서술적 표현
알고리즘을 사람이 쓰는 자연어(언어)로 표현하는 방법이다.
자연어는 서술적일 뿐 아니라 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어렵다.
따라서 누구라도 쉽게 이해하고 쓸 수 있어야 하는 알고리즘을 표현하는 데 한계가 있다.
2. 순서도를 이용한 도식화
알고리즘을 순서도(Flow Chart)를 작성하는 규칙에 따른 도식화 방법이다.
순서도를 이용하면 명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는데 한계가 있다.
3. 프로그래밍 언어를 이용한 구체화
알고리즘을 프로그래밍 언어를 사용해 표현하는 방법이다.
이 방법을 사용하면 알고리즘 자체가 구체화 되므로 추가로 구체화 할 필요가 없다.
하지만 특정한 프로그래밍 언어로 작성하기 때문에 해당 언어를 모르면 이해하기 어렵다.
다른 프로그래밍 언어로 프로그램을 개발하는 경우 다른 언어로 변환해야 하므로 범용성이 떨어진다.
4. 가상코드(Pseudo-Code)를 이용한 추상화
알고리즘을 프로그래밍 언어로 표현했을 때 생기는 단점을 보완한 방법이다.
특정 프로그래밍 언어는 아니지만 언어의 형태를 갖춘 가상코드(Pseudo-Code)로 알고리즘을 표현한다.
가상 코드는 프로그래밍 언어가 아니므로 직접 실행할 수 없지만 일반적인 프로그래밍 언어와 형태가 유사하므로 원하는 특정 프로그래밍 언어로 구체화하기 쉽다.
자료구조의 추상 데이터 타입
추상이란?
'추상적이다.'라고 하면 흔히 '애매하다'나 '난해하다'라는 의미로 사용하지만,
사고의 수준이 높다는 의미로 '추상의 레벨이 높다'고 표현하기도 한다.
여기서 필자가 생각하는 추상의 정의는 '관점이 계층화되어 상승한 것'이라고 한다.
즉, 계층화는 단계가 높으면 추상화의 레벨이 높은 것이다.
프로젝트나 문제 해결 과정에서는 새로운 의미 단위를 분리하고 계층화 작업이 반복되는데, 객체 지향 언어의 클래스가 대표적인 예이다.
의미의 단위를 흔히 모듈(Module)이라고 한다.
통상적으로 모듈은 먼저 추상적인 레벨에서 설계되고, 후에 구체화된다.
모듈을 추상화한다는 것은 세부 사항을 생략하고 가장 중요한 기능만을 드러내는 것을 말한다.
추상화의 2가지 방법
Top-down
큰 그림을 먼저 그리고 점차 작은 모듈로 나누어가는 과정
Bottom-Up
최하부 단위들을 준비하고 거기서 부터 선택과 조합을 통해 상위 레벨의 그림을 만들어 내는 과정
추상 데이터 타입 : ADT
자바의 8가지 기초 데이터 타입
정수 타입은 byte(1바이트), short(2바이트), int(4바이트), long(8바이트)를 사용하고,
실수 타입은 float(4바이트), double(8바이트)를 사용한다.
논리 타입 boolean(1비트)은 true(참), false(거짓)을 표현하고,
문자 타입은 char(2바이트)를 사용한다.
추상 데이터 타입
세부 사항에서 벗어나 추상적으로 정의한 데이터 타입이다.
즉, 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것이다.
자료구조에서는 어떤 대상이 지원하는 '작업을 나열해 표현'하는 것을 '추상적으로 표현한다' 라고 하며, 대상을 그렇게 표현한 것을 추상 데이터 타입이라고 한다.
이때 대상이 포함하는 데이터 속성에 제한이 있으면 데이터의 속성을 같이 서술해도 좋다.
자바에서 8가지 기초 데이터 타입을 제외한 나머지는 추상 데이터 타입이고 추상 데이터 타입은 대략 하나의 클래스에 대응된다.
클래스는 자신의 규칙을 따르는 객체를 만들기 위한 틀이다.
클래스는 그런 객체들의 집합을 의미하기도 해서 하나의 데이터 타입이라고 부르기도 한다.
자바에서 클래스의 상위 개념인 인터페이스(interface) 기능이 ADT에 잘 대응되는 개념이다.
ADT에서 사용자 프로그램까지 (예제: 리스트)
// ADT Design
ADT '리스트'
작업:
i번째 자료에 새 원소 넣기
원소 x 찾기
i 번째 자료에 원소 삭제하기// Interface Design
public interface ListInterface {
public void add(int i, Object x);
public Object get(int i);
public void remove(int i);
}// Class Design
public class LinkedList implements ListInterface {
//TODO: Code
}// User Program
LinkedList a = new LinkedList();
...
a.add(1,x);
a.remove(3);