JAVA - 자료구조

수현·2022년 12월 18일
0

Lesson

목록 보기
1/9
post-thumbnail

📂 리스트

📌 정의

같은 종류의 데이터를 순차적으로 저장하는 자료구조

✔ 특징

➡ 장점

  • 하나의 변수를 통해서 많은 데이터를 효율적 처리
  • 빠른 접근 가능 (첫 데이터의 위치에서 상대적 위치로 데이터 접근)

➡ 단점

  • 데이터 추가/삭제의 어려움 (미리 최대 길이 지정)

✔ 배열 vs 리스트

배열리스트
데이터같은 타입의 데이터만 저장다양한 데이터를 저장할 수 있음
크기처음 저장한 후 변경X가변적으로 변경 가능

📌 문법

✔ 초기화

Integer data_list[] = new integer[10]; //선언
Integer[] data_list = new integer[10]; //가능

data_list[0] = 1 // 할당
Integer data_list[] = {1, 2, 3, 4, 5}; //초기화
System.out.println(data_list[2]); // 출력

✔ ArrayList 클래스

ArrayList 클래스는 가변 길이의 배열 자료구조를 다룰 수 있는 기능 제공

import java.util.ArrayList;

ArrayList<Integer> list1 = new ArrayList<Integer>(); // 선언

list1.add(1); // 배열에 아이템 추가 (추가할 값)
list1.get(0); // 배열에 아이템 읽기 (인덱스 번호)
list1.set(0, 5); // 배열에 아이템 변경 (인덱스 번호, 변경할 값)
  • Brute-force 혹은 Generate-and-Test 기법이라고도 불림
  • 문제의 해법으로 생각할 수 있는 모든 경우의 수를 테스트
  • 장점 : 해답을 찾아내지 못할 확률이 적음
  • 단점 : 모든 경우의 수를 테스트해서 수행 속도 느림

📌 순열 (Permutation)

  • 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열
  • nPr : n (n-1) ... * (n-r+1)
  • nPn = n!

📌 탐욕 알고리즘 (Greedy Algorithm)

  • 여러 경우 중 하나를 결정할 때, 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
  • 수행 과정
    • 1) 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 부분 해 집합에 추가
    • 2) 실행 가능성 검사 : 부분 해 집합이 문제의 제약 조건을 위반하지 않는 지를 검사
    • 3) 해 검사 : 부분 해 집합이 문제의 해가 되는 지를 확인

📌 정렬 (Sort)

  • 특정 기준에 의해 오름차순/내림차순 순서대로 재배열 하는 것

  • 종류

    • 버블 정렬 : 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 ➡ O(n²)
    def BubbleSort(a):
      for i in range(len(a)-1),0,-1):
          for j in range(0,i):
              if a[j] > a[j+1]:
                  a[j],a[j+1] = a[j+1],a[j]
    • 카운팅 정렬 : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬 ➡ O(n+k)

    • 선택 정렬 ➡ O(n²)

    • 퀵 정렬 ➡ [평균]O(nlogn) [최악] O(n²)

    • 삽입 정렬 ➡ O(n²)

    • 병합 정렬 ➡ O(nlogn)

📂 스택

📌 정의

한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
➡ LIFO 방식 (Last In First Out)

✔ 특징

➡ push : 데이터를 스택에 넣기
➡ pop : 데이터를 스택에서 꺼내기

📌 연산

✔ 문법

Import java.util.Stack;

Stack<Integer> stack_int = new Stack<Integer>(); // 정수형 선언


stack_int.push(1); // 데이터 추가
stack_int.push(2);
stack_int.pop();  // 데이터 추출

✔ Stack 클래스

Import java.util.ArrayList;

public class MyStack<T> {
	private ArrayList<T> stack = new ArrayList<T>();
    
    public void push(T item) {
    	stack.add(item);
    }
    
    public T pop() {
    	if (stack.isEmpty()) {
        	return null;
        }
        return stack.remove(stack.size() - 1);
    }
    
    public boolean isEmpty() {
    	return stack.isEmpty();
    }
    
    public static void main(String[] args) {
    	MyStack<Integer> ms = new MyStack<Integer>();
        ms.push(1);
        ms.push(2);
        System.out.println(ms.pop());
        System.out.println(ms.pop());
    }
}

📂 큐

📌 정의

가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
➡ FIFO 방식 (First In First Out)

✔ 특징

➡ Enqueue : 큐에 데이터를 넣는 기능
➡ Dequeue : 큐에서 데이터를 꺼내는 기능

➡ 사용

  • 멀티 태스킹을 위한 프로세스 스케줄링 방식 구현

📌 연산

✔ 문법

  • Enqueue : add(value) / offer(value)
  • Dequeue : poll() / remove()
import java.util.LinkedList; // 큐 사용 위해 필요 
import java.util.Queue;

Queue<Integer> queue_int = new LinkedList<Integer>(); // 정수형 선언
Queue<String> queue_str = new LinkedList<String>(); // 문자형 선언


queue_int.add(1); // 삽입 성공 여부 return (true/false)
queue_int.offer(2); 

queue_int.poll(); // 삭제한 값 return 
queue_int.remove();

✔ Queue 클래스

public class MyQueue<T> {
	private ArrayList<T> queue = new ArrayList<T>();
    
    public void enqueue(T item) {
    	queue.add(item);
    }
    
    public T dequeue() {
    	if (queue.isEmpty()) {
        	return null;
        }
        return queue.remove(0); // 첫번째 인덱스 삭제 
    }
    
    public boolean isEmpty() {
    	return queue.isEmpty();
    {
    
    public static void main(String[] args) {
    	MyQueue<Integer> mq = new Myqueue<Integer>();
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);
        System.out.println(mq.dequeue());
        System.out.println(mq.dequeue());
        System.out.println(mq.dequeue());
    }
}

📌 종류

1. 선형 큐

✔ 특징

➡ 리스트로 구현
➡ 큐의 크기 = 리스트의 크기
➡ 삽입 위치 : rear = rear+1
➡ 삭제 위치 : front = front+1

✔ 상태

➡ 초기 상태 : front = rear = -1
➡ 공백 상태 : front = rear
➡ 포화 상태 : rear = n-1

📌 구현

  • 생성 : createQueue()
    • 크기 n인 1차원 리스트 생성
    • front, rear=-1 초기화

  • 삽입 : enQueue(item)
    • rear+=1 증가시켜 새로운 원소 삽입할 자리 마련
    • 그 인덱스에 해당하는 리스트원소 Q[rear]에 item 저장

  • 삭제 : deQueue()
    • front+=1 증가시켜 큐에 남아있는 첫 번째 원소로 이동
    • 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능을 함

  • 공백/포화상태 검사 : isEmpty(), isFull()
    • 공백상태 : front == rear
    • 포화상태 : rear = len(Q)-1

  • 검색 : Qpeek()
    • 가장 앞에 있는 원소를 검색하여 반환하는 연산
    • front+1에 있는 원소를 반환

2. 원형 큐

✔ 특징

➡ 리스트로 구현
➡ 리스트의 처음과 끝이 연결된 원형 형태의 큐
➡ 삽입 위치 : rear = (rear+1) % n
➡ 삭제 위치 : front = (front+1) % n

✔ 상태

➡ 초기 상태 : front = rear = 0
➡ 공백 상태 : front = rear
➡ 포화 상태 : rear+1 = front

3. 연결 큐

✔ 특징

➡ 연결 리스르토 구현
➡ 노드의 연결 순서는 링크로 연결

✔ 상태

➡ 초기 상태 : front = rear = None
➡ 공백 상태 : front = rear = None
➡ 포화 상태 :

📌 구현

  • 생성 : createLinkedQueue()
    • 리스트 노드 없이 포인트 변수만 생성함
    • front, rear=None 초기화

  • 삽입 : enQueue(item)
    • 새로운 노드 생성 후 데이터 필드에 item 저장
    • 연결 큐가 공백/아닌 경우에 따라 front, rear 변수 지정

  • 삭제 : deQueue()
    • old가 지울 노드를 가리키게 하고, front 재설정
    • 삭제 후 공백 큐가 되는 경우, rear도 None로 설정
    • old가 가리키는 노드를 삭제하고 메모리 반환

  • 공백 검사 : isEmpty()
    • 공백상태 : front = rear = None

📂 연결리스트

📌 정의

✔ 특징

➡ 장점

  • 데이터 공간을 미리 할당하지 않아도 됨

➡ 단점

  • 연결을 위한 별도 데이터 공간이 필요함
  • 연결 정보를 찾는 시간이 필요하여 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

📌 연산

✔ Linked List 클래스

public class Node<T> {
	T data;
    Node<T> next = null;
    
    public Node(T data) {
    	this.data = data;
    }
}

// Node 인스턴스간 연결
Node<Integer>node1 = new Node<Integer>(1);
Node<Integer>node2 = new Node<Integer>(2);

node1.next = node2;
Node head = node1;

// 연결 리스트에 데이터 추가
public class SingleLinkedList<T> {
	public Node<T> head = null;
    
    public clss Node<T> {
    	T data;
        Node<T> next = null;
        
        public Node(T data) {
        	this.data = data;
        }
     }
     
     public void addNode(T data) {
     	if (head == null) {
        	head = new Node<T>(data);
        }
        else {
        	Node<T> node = this.head;
            while (node.next != null) {
            	node = node.next;
            }
            node.next = new Node<T>(data);
        }
     }
}

SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<integer>();
MyLinkedListaddNode(1);
MyLinkedList.head.data;

MyLinkedList.addNode(2);
MyLinkedList.head.next.data;

1. 이중 연결 리스트 (더블 링크드 리스트)

✔ 특징

➡ 양방향으로 연결 (노드 탐색 양쪽으로 모두 가능)

✔ Double Linked List 클래스

public class DoubleLinkedList<T> {
	public Node<T> head = null;
    public Node<T> tail = null;
    
    public class Node<T> {
    	T data;
        Node<T> prev = null;
        Node<T> next = next;
        
        public Node(T data) {
        	this.data = data;
        }
    }
    
    public void addNode(T data) {
    	if (this.head == null) {
        	this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
        	Node<T> node = this.head;
            while (node.next != null) {
            	node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    }
    
    public void printAll() {
    	if (this.head != null) {
        	Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
            	node = node.next;
                System.out.println(node.data);
            }
        }
    }
	// head부터 검색

	public T searchFromHead(T isData) {
		if(this.head == null) {
    		return null;
    	} else {
    		Node<T> node = this.head;
     	   while (node != null) {
        		if (node.data == isData) {
        	    	return node.data;
       	   	    } else {
        	    	node = node.next;
            	}
     	   }
    	    return null;
     	 }
	}
	// tail부터 검색

	public T searchFromTail(T isData) {
		if (this.head == null) {
  	  		return null;
    	} else {
    		Node<T> node = this.tail;
        	while (node != null) {
        		if (node.data == isData) {
            		return node.data;
            	} else {
            		node = node.prev;
            	}
        	}
    	}
	}
}

DoubleLinkedList<Integer> MyLinkedList = new DoubleLinkedList<Integer>();

MyLinkedList.add.Node(2);
MyLinkedList.add.Node(3);
MyLinkedList.printAll();

📂 해쉬

📌 정의

➡ 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조
➡ 해쉬 함수를 통해 배열에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
➡ 해쉬 함수 : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수
➡ 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

✔ 특징

➡ Key를 통해 저장 및 탐색 속도가 획기적으로 빨라짐
➡ 주소(인덱스 번호)에 대한 공간을 배열로 미리 할당한 후, 키에 따른 데이터 저장 및 탐색 지원

✔ HashTable 클래스

public class MyHash {
	public Slot[] hastTable;
    
    public MyHash(Integer size) {
    	this.hashTable = new Slot[size];
    }
    
    public clas Slot {
    	String value;
        Slot(String value) {
        	this.value = value;
        }
    }
}

📂 트리

📌 정의

📝 예제 1.

문제

코드

해설

📝 예제 2.

문제

코드

해설

📂 힙

📌 정의

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 이진 트리

✔ 특징

➡ 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같음 (최대힙의 경우)
➡ 완전이진트리 형태를 가짐

✔ 힙 vs 이진탐색트리

➡ 힙 : 각 노드의 값이 자식 노드보다 크거나 같음
➡ 이진탐색트리 : 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽

📝 예제 1.

문제

코드

해설

📝 예제 2.

문제

코드

해설

📖출처📖

SWEA - Programming Intermediate
Fastcampus

profile
Notion으로 이동

0개의 댓글