1) 자료구조 소개
1-1) 정의
자료를 효율적으로 관리하기 위한 구조
- 관리 → 저장, 삭제, 탐색, …
목적에 맞게 사용한 좋은 자료구조는, 실행시간 단축 or/and 메모리 용량 절감 효과가 있음
1-2) 자료구조의 분류
선형 자료구조
- 배열
- 연결리스트
- 스택, 큐, 데크
- 해시 테이블
비선형 자료구조
- 트리
- 그래프
- 힙 / 우선순위 큐
- 트라이
1-3) 자료구조의 구현
추상 자료형 (Abstract Data Type; ADT) - 자료 형태와 자료에 대한 연산을 정의한 것
- 구체적인 구현 방법은 명시하지 않음
대부분의 자료구조는 자바에서 클래스로 제공
- 이해를 한 후 알맞은 함수를 사용
실습에서는 가급적 처음부터 구현 진행
- 자료 형태, 사이즈, 각 기능에 대해 구현
2) 선형 자료구조 - 배열
2-1) 배열 정의
많은 수의 데이터를 다룰 때 사용하는 자료구조
각 데이터를 인덱스와 1:1 대응하도록 구성
데이터가 메모리 상에 연속적으로 저장됨
2-2) 장점
인덱스를 이용하여 데이터에 빠르게 접근 가능
2-3) 단점
데이터의 추가/삭제가 번거로운 편
- 미리 최대 길이를 정해서 생성해야 함
- 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성
- 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간 유지
3) 연결 리스트
3-1) 정의
데이터를 링크로 연결해서 관리하는 자료구조
자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음
3-2) 장점
데이터 공간을 미리 할당할 필요 없음
즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이
3-3) 단점
연결구조를 위한 별도 데이터 공간 필요
연결 정보를 찾는 시간이 필요 (접근 속도가 상대적으로 느림)
데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요
3-4) 연결 리스트 기본 구조
노드 (Node)
- 데이터 저장 단위로, 값과 포인터로 구성
포인터 (Pointer): 다음 노드나 이전 노드의 연결 정보
3-5) 연결 리스트 기본 연산
데이터 추가
- 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요
데이터 삭제
- 데이터 삭제 위치(head, 중간, tail)에 따른 연결 작업 필요
4) 스택
4-1) 정의
후입선출 (Last In First Out; LIFO) 자료구조
- 마지막에 들어온 데이터가 먼저 나가는 구조
데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용
- ex) 함수 콜 스택, 수식 계산, 인터럽트 처리 등
4-2) 기본 구조
후입 선출 구조
기본적으로 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어짐
4-3) 스택 기본 연산
데이터 추가 (Push)
- 스택의 가장 마지막 위치에 데이터 추가
데이터 꺼내기 (Pop)
- 스택의 가장 마지막 위치에서 데이터 꺼냄
5) 해시 테이블 (Hash Table) = 해시 맵, 해시 표
5-1) 정의
키 (Key), 값 (Value)을 대응시켜 저장하는 데이터 구조
- 키를 통해 해당 데이터에 빠르게 접근 가능
해싱
- 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
5-2) 해시 테이블 구조
- 키: 해시 테이블 접근을 위한 입력 값
- 해시 함수: 키를 해시 값으로 매핑하는 연산
- 해시 값: 해시 테이블의 인덱스
- 해시 테이블: 키-값을 연관시켜 저장하는 데이터 구조
5-3) 해시 충돌
해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
- 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우
해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법 이 있음
해시 충돌 해결 방법 (1) 개방 주소법 (Open Address)
- 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
- hash와 value가 1:1 관계 유지
- 비어 있는 공간 탐색 방법에 따라 분류
- 선형 탐사법, 제곱 탐사법, 이중 해싱
개방 주소법 – 선형 탐사법
- Linear Probing
- 빈 공간을 순차적으로 탐사하는 방법
- 충돌 발생 지점 부터 이후의 빈 공간을 순서대로 탐사
- 일차 군집화 문제 발생
- 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생
개방 주소법 – 제곱 탐사법
- Quadratic Probing
- 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
- 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사
- 일차 군집화 문제 일부 보완
- 이차 군집화 문제 발생 가능성
개방 주소법 – 이중 해싱
- Double Hashing
- 해싱 함수를 이중으로 사용
- 해시 함수 1: 최초 해시를 구할 때 사용
- 해시 함수 2: 충돌 발생 시, 탐사 이동 간격을 구할 때 사용
- 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨
해시 충돌 해결 방법 (2) 분리 연결법 (Separate Chaining)
- 해시 테이블을 연결 리스트로 구성
- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결
6) 데크
6-1) 정의
양쪽에서 삽입과 삭제가 모두 가능한 자료구조
- Deque: Doubly-ended Queue
- Stack과 Queue 를 합친 형태
6-2) 기본 구조
- 데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조
- 일부 기능을 제한하여 용도에 맞게 변형 가능
6-3) 입력제한 데크 (Scroll)
한 쪽의 입력을 제한한 데크
6-4) 출력제한 데크 (Shelf)
한 쪽의 출력을 제한한 데크
7) 큐
7-1) 정의
선입선출 (First In First Out; FIFO) 자료구조
- 먼저 들어온 데이터가 먼저 나가는 구조
입력 순서대로 데이터 처리가 필요할 때 사용
- 프린터 출력 대기열, BFS (Breath-First Search) 등
7-2) 큐 기본 구조
- 선입선출 구조를 따름
- 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐
7-3) 큐 기본 연산
데이터 추가 (Enqueue)
- 큐에 데이터 추가
데이터 꺼내기 (Dequeue)
- 큐에서 데이터 꺼내기
