728x90
최신 JAVA 구현 자료구조론
한정란 저자의 최신 JAVA 구현 자료구조론 도서를 읽고 학습한 내용 기록
출처 : 최신 JAVA 구현 자료구조론 - 한정란
학습 구성
- 자료(=data)의 특성마다 해당 자료에 맞는 자료 구조들이 존재
ex) 대기자 명단 자료, 동물 목록 자료, 아이디 비밀번호 자료, 괄호 개수 체크하는 자료(괄호라는 자료를 준다.) 등등 - 헤당 자료에 맞는 자료구조를 선택
ex) list, set, map, stack, queue, deck, linked, ... - 자료를 통해서 원하는 결과 도출
- 알고리즘 이용 : 명령문을 사용해서 결과를 도출
ex) for, if, while, 람다식, break문
- 알고리즘 이용 : 명령문을 사용해서 결과를 도출
- 결론
- 자료구조는 정형화된 틀이 존재. 알맞는 자료 구조를 사용해서 효율적으로 프로그램 성능을 높일 수 있다.
- 알고리즘은 행당 자료구조를 입맛에 맞게 재 가공 하는 과정으로 큰 정형화된 틀이 없다. - 물론 자주쓰는 것은 있을 수 있다.
자료 -> 자료구조 -> 명령문으로 되어있는 알고리즘
1. 알고리즘과 자료 구조 성능
- 자료 구조
- 처리할 자료들 사이에 관계를 고려하여 컴퓨터 내부에 표현하는 방법들을 총칭하는 말
- 자료
- 컴퓨터에서 변수를 사용해 자료 값을 저장
- 자료구조
- '자료형과 관련된 값'과' 저장될 변수'의 관계의 구조를 나타내는 것
- 여러방법으로 연결된 변수들의 집합
- 알고리즘
- 자료구조로 표현된 자료를 처리하는 절차들의 모임, 특정한 문제 해결을 위해 기술한 명령문
1.1 알고리즘
- 알고리즘을 흐름도라고 표현한다.
- flow chart
1.2 알고리즘 성능 분석 5가지
- 시간 복잡도
- 실행 시간으로 알고리즘을 구현한 프로글매을 컴퓨터에서 실행할 때 소요되는 CPU 시간
- 공간 복잡도
- 알고리즘에 사용한 자료를 저장하는 기억공간의 양
- 정확성
- 간결성
- 최적성
2. 순차 자료 구조
- 선형 리스트 형태
- 종류
- 배열
- 행렬 - 희소행렬, 희소배열
- 컬렉션 - vector
2.1. 행렬
- 희소 행렬
- 전체 원소 수에 비해 실제로 값을 사용하는 원소 수가 아주 적은 행렬
- 메모리 절략을 위해 원소 수가 있는 행과 열에 대한 정보를 별도로 구성하는 것이 효과적
- 희소 배열
- 희소 행렬의 메모리 절략을 위해 별도로 구성한 배열
- 한 행에 희소 행렬의 행, 열, 값을 작성 3x3 배열로 생성
2.2 배열의 표현
- 일차원 배열 L에서 각 원소를 저장하는데 필요한 셀의 크기를 s bite라 할 때 i 번째 놓인 원소의 물리적인 주소를 계산
- array L의 시작주소가 a일 때 L[i]의 주소는 a+ i*s 가 된다.
2.3 컬렉션
- java에선 vector, ArrayList, Stack Queue Map 등 자료구조 제공 -> 선형리스트를 벡터를 사용해 표현하면 편리
- 클래스 타입의 자료 저장
3. 연결 리스트
- 선형 리스트의 단점을 개선
- 종류
- 원형 연결 리스트
- 이중 연결 리스트
- 원형 이중 연결 리스트
이전에 만들었던 MyLinkedList와 동일: 2023.03.27 - [java/java 심화] - LinkedList 구현하기
4. 스택
- top: 삭제가 일어나는 곳
- push: 삽입 연산
- pop : 삭제 연산
- 순차 스택 생성 구조
- 스택 생성
- 공백 스택인지 확인하는 연산 isEmpty()
- 스택에 우너소를 삽입하는 연산
- 스택에서 원소를 삭제하는 연산
- 스택의 원소를 반환하는 연산
4.1. array stack
package study;
public class MyArrayStack {
private int top; //top 원소 가리키는 변수
private int size; // 배열의 크기
private int increment; // 배열 확장 단위
private Object[] itemStack; // 원소 저장하는 배열
private Object itemEmpty = "empty";
// 스택 멤버변수들 초기화
public MyArrayStack() {
top = -1;
size = 50;
increment = 10;
itemStack = new Object[size];
}
public boolean isEmpty() {
return top == -1; // 공백 스택
}
public void push(Object x){
if (top == size - 1) {
size += increment;
Object[] tempArray = new Object[size];
for (int i = 0; i < top; i++) tempArray[i] = itemStack[i];
itemStack = tempArray;
}
itemStack[++top] = x; // 원소 삽입
}
public Object pop() {
if (isEmpty()) {
System.out.println("Stack Empty");
return itemEmpty;
}
return itemStack[top--];
}
public Object peek() {
if (isEmpty()) {
System.out.println("Stack Empty");
return itemEmpty;
} else {
return itemStack[top];
}
}
public void print() {
for (int i = 0; i < top; i++) System.out.print(itemStack[i] + ",");
System.out.println(itemStack[top]);
System.out.println();
}
}
4.2. 연결 리스트를 사용해서 스택 구현
- 스택이 가득 차는 것을 의식할 필요가 없다.
package study;
public class MyLinkedStack {
StackNode top;
String itemEmpty = "StackEmpty";
// 추가
void push(String x) {
StackNode temp;
// stack이 공백인 경우
if (top == null) {
top = new StackNode();
top.data = x;
top.link = null;
} else {
temp = new StackNode();
temp.data = x;
temp.link = top;
top = temp;
}
}
void print() {
StackNode temp;
temp = top;
while (temp != null) {
System.out.println(temp.data + ",");
temp = temp.link;
}
System.out.println("null");
}
// 제일 top stackNode 출력
Object peek() {
if (top == null) {
System.out.println("null");
return itemEmpty;
}
return top.data;
}
// 제거
void pop() {
if (top == null) System.out.println("null");
else top = top.link;
}
}
class StackNode {
Object data;
StackNode link;
}
5. 큐
- FIFO 구조 : 삽입과 삭제가 서로 다른 곳에서 이뤄지는 리스트
- 작동 구조
- rear: 삽입
- front: 삭제
- 제일 먼저 들어온 값이 front로 고정
- 값이 들어올 때마다 rear위치가 뒤로 넘어간다.
- 생성 원리
- 핵심 연산
- (front +1 ) % size
- (rear +1 ) % size
- 공백 검사
- 큐에 원소 삽입 연산
- 배열 공간 늘리기
- front는 유지
- rear 늘리기
- 큐에 원소 삭제
- front를 늘린다.
- rear 유지
- 핵심 연산
5.1 arrayQueue
package study;
public class ArrayQueue {
private int front;
private int rear;
private int count;
int size;
private final int increment;
private Object[] itemQueue;
private final Object itemEmpty = "empty";
public ArrayQueue() {
front = 0; // 처음 큐
rear = 0; // 큐 저장 위치
count = 0; // 큐 개수
size = 5; // 큐 처음 크기
increment = 10; // 배열 확장 단위
itemQueue = new Object[size]; // 큐원소 저장 배열
}
public boolean isEmpty() {
return (count == 0);
}
public void insert(Object x) {
if (count == size) {
int oldSize = size;
size += increment;
Object[] tempArray = new Object[size];
System.out.println("front = " + front);
for (int i = 0; i < count; i++, front = (front + 1) % oldSize) { // i++과 front 계산은 제일 마지막에 수행
// System.out.println("f: " + front); // 0부터 채워 넣음
tempArray[i] = itemQueue[front];
}
itemQueue = tempArray;
front = 0;
rear = count;
}
itemQueue[rear] = x;
rear = (rear + 1) % size;
count++;
}
public Object delete() {
if (isEmpty()) {
System.out.println("empty");
}
Object tempItem = itemQueue[front];
front = (front + 1) % size;
count--;
return tempItem;
}
public Object peek() {
if (isEmpty()) {
System.out.println("empty");
return itemEmpty;
} else {
return itemQueue[front];
}
}
public void print() {
for (int i = front; i < rear; i++) {
System.out.println(itemQueue[i]);
}
System.out.println();
}
}
package study;
import static org.junit.jupiter.api.Assertions.*;
class ArrayQueueTest {
public static void main(String[] args) {
ArrayQueue q = new ArrayQueue();
q.insert(1);
q.insert(2);
q.insert(3);
q.print();
q.insert(4);
q.insert(5);
q.insert(6);
q.insert(7);
q.print();
q.delete();
q.delete();
q.delete();
q.delete();
q.delete();
q.print();
System.out.println("size: " + q.size);
}
}
5.2. LInkedlist queue
- 배열일 때 크기제한으로 인해서 확장 하는 단점 존재
- linkedList의 node를 이용해서 q를 연결
package study;
public class LinkedQueue {
QueueNode front, rear;
void insert(Object x) {
QueueNode temp;
if (rear == null) {
rear = new QueueNode();
rear.data = x;
front = rear;
} else {
temp = new QueueNode();
temp.data = x;
rear.link = temp;
rear = temp;
rear.link = null;
}
}
void delete() {
if (front == null) {
System.out.println("null");
} else {
front = front.link; // 삭제 전 front 참조변수를 변경
if (front == null) {
rear = null;
}
}
}
void print() {
QueueNode temp;
temp = front;
while (temp != null) {
System.out.println(temp.data);
temp = temp.link;
}
System.out.println("null");
}
}
class QueueNode {
Object data;
QueueNode link;
}
package study;
import static org.junit.jupiter.api.Assertions.*;
class LinkedQueueTest {
public static void main(String[] args) {
LinkedQueue q = new LinkedQueue();
QueueNode temp;
q.front = q.rear = null;
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
q.print();
q.delete();
q.print();
}
}
6. 덱
- 스택과 큐의 성질을 합한 선형 리스트
- 스택과 큐를 확장하여 삽입과 삭제를 리스트의 양끝에서 수행하는 자료 구조
- arrayDeque라고 Deque 인터페이스를 구현한 구현 클래스 존재
package study;
public class MyDeque {
private int front;
private int rear;
private int count;
int size;
private int increment;
private Object[] itemDeque;
private final Object itemEmpty = "empty";
public MyDeque() {
front = 0; // 처음 큐
rear = 0; // 큐 저장 위치
count = 0; // 큐 개수
size = 5; // 큐 처음 크기
increment = 10; // 배열 확장 단위
itemDeque = new Object[size]; // 큐원소 저장 배열
}
public boolean isEmpty() {
return (count == 0);
}
public void increaseArray() {
size += increment;
Object[] tempArray = new Object[size];
for (int i = 0; i < rear; i++) {
tempArray[i] = itemDeque[i];
}
itemDeque = tempArray;
}
public void insertLast(Object x) {
itemDeque[rear] = x; // 값 넣기
rear++; // rear 값 증가
if (rear == size) { // size 초과시 array 확장
increaseArray();
count++;
}
}
public void insertFirst(Object x) {
if (count != 0) {
for (int i = count; i > 0; i--) {
itemDeque[i] = itemDeque[i - 1];
itemDeque[0] = x;
count++;
rear = count;
if (rear == size) {
increaseArray();
}
}
}
}
public Object deleteFirst() {
if (isEmpty()) {
System.out.println("null");
return itemEmpty;
}
Object tempItem = itemDeque[0];
for (int i = 0; i < count; i++) {
itemDeque[i] = itemDeque[i + 1];
}
count--;
rear--;
return tempItem;
}
public Object deleteLast() {
if (isEmpty()) {
System.out.println("null");
return itemEmpty;
}
Object tempItem = itemDeque[rear - 1];
rear--;
count--;
return tempItem;
}
public Object First() {
if (isEmpty()) {
return itemEmpty;
} else return itemDeque[front];
}
public Object Last() {
if (isEmpty()) {
return itemEmpty;
} else return itemDeque[rear - 1];
}
public void print() {
if (isEmpty()) {
System.out.println("null");
} else
for (int i = 0; i < rear; i++)
System.out.println(itemDeque[i]);
}
}
7. 정렬과 탐색
- 버블 정렬이란 것이 존재하지만 성능이 너무 떨어지므로 생략
7.1. 선택정렬
- 가장 작은 값부터 차례대로 리스트의 앞으로 옮겨서 앞에서부터 뒤로 || 뒤에서부터 앞으로 정렬하는 직관적이고 가장 간단한 방법
- 알고리즘
- 최솟값을 찾아서 배열 맨 앞의 수와 교환
- 정렬된 첫번째 수 제외하고 최솟값 찾아서 교환
- 반복
- 핵심 로직
int temp = data[i];
data[i] = data[min];
data[min] = temp;
7.2. 삽입 정렬
- 정렬된 부분과 정렬되지 않은 부분을 나눈다.
- 정렬되지 않은 부분 중 첫 요소를 정렬된 부분의 적절한 위치에 삽입
- 정렬이 다 될때 까지 반복
- 양극화의 시간 복잡도를 가진다.
- 정렬이 된 경우 : 최상의 시간 복잡도
- 역순 정렬이 된 경우 : 최악의 시간 복잡도
- 핵심 로직
for (int i = 1; i < size; i++) {
int temp = data[i];
int j = i;
while ((j > 0) && (data[j - 1] > temp)) {
data[j] = data[j - 1];
j--;
}
data[j] = temp;
}
7.3. 쉘 정렬
- 삽입 정렬에 전처리과정을 추가한 것.
- 대충 작은 값을 앞으로 큰 값을 뒤로 보내는 전처리 과정을 진행
코드 생략
7.4. 큌 정렬
- 정렬 알고리즘 표준이 되고 가장 유명한 정렬 방법 이다.
- 기준이 되는 pivot을 선정하여 pivot을 기준으로 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 재배치하고 다시 분할하여 정렬하는 알고리즘
- 보통의 경우 데이터의 맨 왼쪽 원소나 중간에 위치한 값을 피벗으로 정해 수행
- 되게 복잡하다. 이해 필요....
public class QuickSort {
public static void quickSort(final int[] data, int start, int end) {
if (start < end) {
int low = start;
int high = end;
int pivot = data[(low + high) / 2];
while (low < high) {
while (data[low] < pivot) low++;
while (data[high] > pivot) high--;
if (low < high) {
int tmp = data[low];
data[low] = data[high];
data[high] = tmp;
}
}
System.out.println(Arrays.toString(data));
quickSort(data, start, low - 1);
quickSort(data, low + 1, end);
}
}
}
7.5. 합병 정렬
- 정렬할 리스트를 반으로 분할, 좌측과 우측 리스트를 계속하여 분할 하면서 합병하면서 정렬하는 방법
- 정렬 알고림즘 중에 비교적 간단해서 많이 쓰이고 있는 알고리즘 중하나이며 시간 복잡도는 최소를 보장
- 데이터 전체 크기만큼의 기억 공간이 더 필요
7.6. 힙 정렬
- 이진트리의 한 종류인 최ㅣ대 힙을 이용해 정렬하는 방법, 최대 힙의 각 노드는 자식 노드들보다 큰 값을 갖는 구조로 최대 힙의 루트가 최댓값이라는 점을 활용해 정렬 수행
7.7.탐색
- 종류
- 순차 탐색
- 이진 탐색
- 해시 탐색
나~~~~~중에 시간 있을 때 추가 필요!!!
https://bnzn2426.tistory.com/115
자료 구조(Data Structure) 개념 및 종류 정리
자료 구조란? 데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것. 예를 들어 한정된 크기의
bnzn2426.tistory.com