전공/자료구조와 실습 (9) 썸네일형 리스트형 DP) Dynamic Programming optimization problen 문제를 해결하는 최적의 답 maximum, minimum을 구하는 문제 => 가장 빨리 도착하는 경로의 소요 시간?, 주식을 사고 팔 때 가장 높은 수익? 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 방법 큰 문제를 작은 문제를 여러 번 재사용한다는 특징을 이용함 이전의 작은 문제의 값을 기억하고 같은 문제가 나오면 저장해둔 결과를 가져옴 다이나믹 프로그래밍 2가지 조건 최적 부분 구조(Optimal Substructure): 작은 문제들의 해결 방법을 합치면 큰 문제 단, subproblems이 독립적이어야 함 중복되는 부분(Overlapping Subproblems): 문제를 작은 문제로 나누었을 때, 동일한 문제가 반복적으로 발생하는 경우 다이나믹 프.. Stack) Stack Stack 데이터를 입시 저장하기 위한 선형 자료구조 후입후출 'LIFO' (Last in First Out) 마지막에 들어온 요소가 가장 먼저 나감 Stack의 기본 연산 Push: 스택의 맨 위에 새로운 요소 추가 Pop: 스택의 맨 위 요소를 제거 Peek: 스택의 최상위 요소를 조회함 IsEmpty: 스택이 비어있는지 확인 import java.util.Stack; public class StackExample { public static void main(String[] args) { // 스택 생성 Stack stack = new Stack(); // Push 연산 예시 stack.push(1); // 스택에 1 추가 stack.push(2); // 스택에 2 추가 stack.push(3); .. Queue) Priority Queue Priority Queue 우선순위를 가진 Queue이다. 동일한 우선순위를 가진 요소는 FIFO 원칙이 적용된다. 활용 import java.util.PriorityQueue; PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.add(5); priorityQueue.add(1); priorityQueue.add(3); // 1이 가장 높은 우선순위를 가지므로, 1이 먼저 출력. System.out.println(priorityQueue.poll()); // 출력: 1 Deque 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 큐 양방향으로 처리가 가능 활용 import java.util.ArrayDeque; import java.util... Queue) Circular Queue Circular Queue 선형 큐에서 요소를 추가하고 제거하는 과정에서 생기는 앞 공간을 재사용할 수 없는 문제가 있음 이런 문제점을 해결하기 위해 고안됨 시작 인덱스와 끝 인덱스가 만나서 순환함 Modulo Operation Circular Queue 구현 front = (front + 1) % SIZE; rear = (rear + 1) % SIZE; public class CircularQueue { private int[] circularQueue; private int front; private int rear; private int size; public CircularQueue(int size) { this.size = size; circularQueue = new int[size]; fro.. Queue) Queue란? Queue 데이터를 순서대로 처리하기 위한 선형 자료구조 선입선출 (First In First Out, FIFO)임 은행 창구 서비스와 비슷함. 추가로 작업 스케줄링, 네트워크 트래픽 관리에서 활용 Queue의 주요 연산 enqueue: 큐의 뒤쪽에 요소를 추가함 큐가 가득 차지 않았다면, rear 포인터가 가리키는 위치에 요소를 추가하고, rear를 다음 위치로 이동 dequeue: 큐의 앞쪽에서 요소를 제거하고 반환 큐가 비어 있지 않다면, front 포인터가 가리키는 요소를 제거하고, front를 다음 요소로 이동. peek: 큐의 앞에 있는 요소를 조회함 큐가 비어 있지 않다면, front 포인터가 가리키는 요소를 반환 isEmpty: 큐가 비어 있는지 확인 front와 rear 포인터의 위치, .. Set) Hash set Set 데이터를 저장하는 ADT 순서를 보장하지 않음 데이터 중복을 허용하지 않음 데이터 조회가 List보다 빠름 => HashSet, LinkedHashSet, TreeSet import java.util.HashSet; import java.util.Set; public class Main { public static void main(String[] args) { // Set 생성 Set set = new HashSet(); // 데이터 추가 set.add("Apple"); set.add("Banana"); set.add("Cherry"); // 데이터 중복 추가 set.add("Apple"); // 데이터 출력 for (String s : set) { System.out.println(s); } .. Map) HashMap MAP key-value pair들을 저장하는 ADT 같은 key를 가지는 pair는 최대 한 개만 존재 => 키를 통해서 빠른 검색이 가능하다. (HashMap, TreeMap, LinkedHashMap) Hash table (Hash Map) 배열과 해시 함수를 사용하여 map을 구현한 자료구조 Hash function: 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수 "인터스텔라" > hash function > 123 (hash) 상수 시간으로 데이터에 접근하기 때문에 빠름 hash collision key는 다른데 hash가 같을 때 key도 hash도 다른데 hash%map_capa 결과가 같을 때 hash collision 해결 방법 open .. Search) Binary Search (이진탐색) Binary Search (이진탐색) 데이터 집합의 중앙값을 확인 중앙값이 찾는 값과 같다면 search 종료 찾는 값이 중앙값 보다 크다면, 중앙값의 오른쪽 부분에서 search 찾는 값이 중앙값보다 작다면, 중앙갑의 왼쪽 부분에서 search 반복 탐색 시간: log n 단점: 정렬되어 있는 데이터에만 사용 가능 public class BinarySearch { int binarySearch(int arr[], int target) { int low = 0, high = arr.length - 1; while (low 이전 1 2 다음
