본문 바로가기

🖋️ 자료구조와 알고리즘26

이전 1 2 3 4 다음

[트리] 색인과 이진검색트리 색인 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 가장 중요한 주제 이 작업을 위함 핵심 인프라는 색인임 색인은 개체의 레코드를 검색하기 위한 것. 레코드에 빨리 접근하기 위한 것 내장 색인 : 메인 메모리에 올려놓고 쓰는 색인 외장색인 : 메모리 바깥에 놓고 쓰는 색인 ex) B-트리 색인의 추상 데이터 타입 ADT 색인에 키 X를 삽입 색인에서 키 X를 검색 색인에서 키 X를 삭제 색인이 비어 있는지 확인 색인을 깨끗이 비우기 이진 검색 트리 각 노드는 최대 2개까지 가지를 칠 수 있음 맨 위에 있는 노드를 루트라고 함 특성 각 노드는 키값을 하나씩 가짐, 각 노드의 키값은 모두 다름 최상위 레벨의 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 가짐 임의 노드의 키값은 자신의 왼쪽 아.. 2023. 11. 27.

[정렬] 특수 정렬 알고리즘(계수/기수/버킷) 계수 정렬, 기수 정렬, 버킷 정렬은 각각 특정한 상황에서 빛을 발하는 정렬 알고리즘 이들 알고리즘의 효율성은 데이터의 특성과 분포에 크게 의존함 계수 정렬 (Counting Sort) 특수한 사용 상황: 정수와 작은 범위: 계수 정렬은 정수 데이터에 최적화. 특히 정수 값의 범위가 제한적일 때 매우 효율적 동일한 값의 빈번한 반복: 동일한 값이 데이터셋 내에 빈번하게 반복되는 경우에도 계수 정렬이 유리 데이터의 범위가 작고, 데이터 양이 많은 경우: 예를 들어, 점수나 나이와 같이 특정 범위 내에 있는 정수를 정렬할 때 유용 기수 정렬 (Radix Sort) 특수한 사용 상황: 긴 정수나 문자열 정렬: 긴 정수나 문자열과 같은 데이터를 정렬할 때 기수 정렬은 효과적 (자릿수별로 정렬하기 때문) 비교 기.. 2023. 11. 21.

[정렬] 고급 정렬 알고리즘(병합/퀵/힙/셀) 병합 정렬 (Merge Sort) 병합 정렬은 분할 정복 방법을 사용하는 정렬 방법 작동 원리: 배열을 반으로 나눕니다. 각 부분을 재귀적으로 정렬합니다. 정렬된 두 부분을 병합하여 완전한 정렬된 배열을 만듭니다. 시간 복잡도: 최선, 평균, 최악 모두 O(nlogn) 공간 복잡도: O(n) (추가 배열을 사용하기 때문) 약점: 추가 메모리가 필요합니다. 자주 사용되는 클래스나 컬렉션: 배열(int[], Integer[], String[] 등), ArrayList, LinkedList 퀵 정렬 (Quick Sort) 퀵 정렬도 분할 정복 전략을 사용하지만, 병합 정렬과는 다르게 작동 작동 원리: 피벗(pivot) 요소를 선택합니다. 피벗을 기준으로 배열을 두 부분으로 나눕니다: 피벗보다 작은 요소와 피벗.. 2023. 11. 21.

[정렬] 기본 정렬 알고리즘(선택/버블/삽입) 정렬이란? 원소들을 순서대로 배열하는 것 수행시간에 따라 나눈 정렬 알고리즘 선택 정렬 (Selection Sort) 전체 배열에서 최솟값(또는 최댓값)을 찾습니다. 이 최솟값을 배열의 맨 앞에 위치시킵니다. 맨 앞의 요소를 정렬된 부분으로 간주하고, 나머지 부분에 대해 같은 과정을 반복합니다. 특징: 시간 복잡도: O(n2) 공간 복잡도: (1)O(1) (제자리 정렬) 불안정 정렬: 동일한 값의 원소가 원래 순서를 유지하지 않을 수 있음 버블 정렬 (Bubble Sort) 배열을 순회하면서 인접한 요소를 비교합니다. 만약 순서가 잘못되어 있다면, 인접한 요소를 교환합니다. 이 과정을 배열이 정렬될 때까지 반복합니다. 특징: 시간 복잡도: O(n2) 공간 복잡도: O(1) (제자리 정렬) 안정 정렬: 동.. 2023. 11. 21.

[힙] 우선순위 큐 : 힙 힙 (Heap) 대표적인 우선순위 큐 완전 이진 트리 구조 사용 힙에서는 모든 부모 노드가 자식 노드보다 크거나(최대 힙) 혹은 작음(최소 힙) 원소를 검색할 수 있는 기능은 필요없고, 우선순위가 가장 높은 것을 알려주고 삭제할 수 있으면 됨 사용 예시 : 운영 체제에서 프로세스 스케줄링, 네트워크 트래픽 관리, 시뮬레이션 시스템 등 힙과 이진 트리는 모두 계층적 데이터를 저장하고 처리하는 데 유용한 자료구조 힙은 주로 우선 순위에 따른 데이터 처리에, 이진 트리(특히 이진 탐색 트리)는 정렬된 데이터의 효율적인 탐색에 사용 우선순위 큐 ADT [핵심 작업] 원소를 삽입한다 최대 원소를 알려주면서 삭제한다 최대 원소를 알려준다 [공통] 우선순위 큐가 비어 있는지 확인한다 우선순위 큐를 깨끗이 비운다 주요.. 2023. 11. 21.

[큐] 배열 기반 큐와 연결리스트 기반 큐 생활 속 큐의 예시 은행 대기열: 고객들이 차례로 도착하고, 도착한 순서대로 서비스를 받습니다. 프린터 작업: 문서들이 프린터 대기열에 차례로 추가되며, 추가된 순서대로 인쇄됩니다. 콜센터 전화 대기열: 전화가 순서대로 대기열에 들어가고, 차례로 연결됩니다. 온라인 티켓 예매: 사용자들이 서버에 접속해 대기열에 들어가고, 순서에 따라 티켓을 구매할 수 있습니다. 큐 자료구조의 ADT(추상 데이터 타입) Enqueue: 큐의 끝에 새로운 요소를 추가합니다. Dequeue: 큐의 시작에서 요소를 제거하고 반환합니다. Peek / Front: 큐의 시작에 있는 요소를 조회하지만 제거하지 않습니다. IsEmpty: 큐가 비어있는지 확인합니다. Size: 큐에 저장된 요소의 개수를 반환합니다. 배열 기반 큐(원형.. 2023. 11. 21.

[스택] 배열 기반 스택과 연결 리스트 기반 스택 Stack 스택은 후입선출이라는 규칙에 따라 데이터를 저장하고 접근하는 선형 자료구조 사용 예시 : 웹 브라우저의 뒤로 가기 기능, 문자열 역순, 괄호 검사, 실행 취소 기능, 재귀 함수 호출 스택의 개념 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 원칙에 따라 작동하는 자료구조 이 원칙은 가장 마지막에 삽입된 요소가 가장 먼저 제거된다는 것을 의미함 스택 자료구조의 ADT(추상 데이터 타입) Push : 스택의 맨 위에 요소를 추가합니다. Pop : 스택의 맨 위에서 요소를 제거하고, 그 요소를 반환합니다. Peek : 스택의 맨 위 요소를 반환하지만, 제거하지 않습니다. IsEmpty : 스택이 비어 있는지 확인합니다. 배열 기반 스택 (Sta.. 2023. 11. 21.

이전 1 2 3 4 다음

티스토리툴바