728x90
반응형
📂 리스트
📌 정의
같은 종류의 데이터를 순차적으로 저장하는 자료구조
✔ 특징
➡ 장점
- 하나의 변수를 통해서 많은 데이터를 효율적 처리
- 빠른 접근 가능 (첫 데이터의 위치에서 상대적 위치로 데이터 접근)
➡ 단점
- 데이터 추가/삭제의 어려움 (미리 최대 길이 지정)
✔ 배열 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); // 배열에 아이템 변경 (인덱스 번호, 변경할 값)📌 완전 검색 (Exhaustive Search)
- 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;
}
}
}728x90
반응형
