전공/자료구조와 실습 (11) 썸네일형 리스트형 Sort) Quick Sort, Merge Sort, Heap Sort 1. 퀵 정렬 (Quick Sort): O(n log n) ~ O(n²) def quick_sort(arr): if len(arr) pivot] return quick_sort(left) + middle + quick_sort(right) 2. 병합 정렬 (Merge Sort): O(n log n) def merge_sort(arr): if len(arr) 3. 힙 정렬 (Heap Sort): O(n log n)import heapqdef heap_sort(arr): heapq.heapify(arr) # 리스트를 힙으로 변환 return [heapq.heappop(arr) for _ in range(len(arr))] Sort) Bubble Sort, Selection Sort, Insertion Sort 1. 버블 정렬 (Bubble Sort): O(n²)def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr 2. 선택 정렬 (Selection Sort): O(n²) def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] 3. 삽입 정렬 .. 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); } .. 이전 1 2 다음