본문 바로가기

전체 글27

우선순위 큐와 힙 우선순위 큐: 우선순위에 따라 요소를 제거하는 큐, 우선순위 기준은 프로그래머 마음대로.우선순위 큐의 각 요소는 우선순위를 가지고 이에 따라 오름차순으로 연결된다. 우선순위가 높을수록 빠르게 빠져나온다. 노드 삽입 연산: 우선순위 큐의 첫 요소부터 순차적으로 비교 한 뒤 알맞는 위치에 삽입한다. 노드 제거 연산: 전단만 제거해서 반환하면 된다. 힙: 자유저장소의 힙과는 관련 없는 힙 순서 속성을 만족하는 완전 이진트리(최고 깊이를 제외하고 모든 노드가 완전히 채워진 이진트리를 말한다. 이진 탐색은 불가능 힙에서 가장 작은 데이터는 뿌리노드이다. 힙 순서 속성: 트리 내 모든 노드가 부모보다 커야한다는 규칙. 자동메모리(스택)는 자료구조 스택을 바탕으로 구현한 메모리 구조이지만 자유저장소(힙)는 이름만 .. 2025. 4. 22.
탐색 알고리즘 {순차 탐색, 이진 탐색, 이진 탐색 트리, 레드 블랙 트리} 탐색 알고리즘이란 목적에 맞는 데이터를 찾아내기 위한 알고리즘이다. 순차 탐색: 처음부터 끝까지 차례대로 모든 요소를 비교해 원하는 데이터를 찾는 탐색 알고리즘으로,어느 한쪽 방향으로만 탐색할 수 있어 선형 탐색이라고 부르기도 한다. 성능은 좋지 않지만 정렬되지 않은 데이터에서원하는 항목을 찾을 수 있는 방법이며 구현이 간단해 버그를 만들 가능성이 적다는 장점이 있다. 자기 구성법: 순차탐색의 검색 효율을 끌어올리는 방법으로 자주 사용되는 항목을 데이터 앞쪽에 배치하는 방법.자주 사용되는 항목을 선별하는 방법에 따라 3가지로 나뉜다. 1. 전진 이동법 - 탐색된 항목을 데이터의 가장 앞으로 옮기는 방법. 한 번 탐색된 항목이 다음에 또다시 검색될 가능성이 높은데이터에 한해 사용해야 함. 2. 전위법 - .. 2025. 4. 21.
정렬 알고리즘 {버블 정렬, 삽입 정렬, 퀵 정렬} 정렬: 사전적 의미는 물건 등을 가지런히 늘어 세우다는 뜻이지만 정렬의 목적은 탐색에 있다.정렬 알고리즘은 정해진 기준에 따라 데이터를 순서대로, 체계적으로 정리하는 알고리즘으로 정렬 알고리즘 역시 데이터를 쉽고 빠르게 찾는 것이 목적이다. 버블 정렬: 자료구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬을 수행한다. 이웃 요소끼리 데이터를 비교하여 바른 순서로 위치해 있는지 확인하고 왼쪽이 크면 오른쪽 데이터와 교환, 왼쪽이 작으면 유지하는 것을 반복하며 비교와 교환을 한다. 제일 왼쪽부터 오른쪽에 이웃하는 요소와 데이터를 비교하고 제일 큰 수가 오른쪽에 정렬되면 다시 나머지 요소들을 처음부터 정렬한다. 버블 정렬의 성능: 자료구조를 순회할때마다 정렬해야 하는 자료구조의 범위가 하나씩 줄어들.. 2025. 4. 17.
트리 {이진트리, 수식트리, 분리 집합} 트리: 나무를 닮은 자료구조, 트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 3가지 요소로 이루어져 있음. 뿌리, 가지, 잎은 모두 똑같은 노드이다. 어디에 위치하는가에 따라 불리는 이름이 달라질 뿐. 뿌리 - 트리 자료구조의 가장 위에 있는 노드 , 가지 - 뿌리와 잎 사이에 있는 모든 노드잎 - 가지의 끝에 매달린 노드, 끝에 있다고 해서 단말 노드라고 부르기도 한다. B는 C와D의 부모(Parent), C와 D는 B의 자식(Children), 그리고 한 부모 밑에서 태어난 C와 D를 형제(Sibling)라고 함.B와 K는 아무 관계가 아니다. 경로: 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서 I노드에서 K노드 까지 찾아간다면, I, J, K를I에서 K까지의 경.. 2025. 4. 17.
큐 {순환 큐, 링크드 큐} 큐는 입력과 출력 창구가 따로 존재하고 먼저 들어간 데이터가 먼저 나오는 선입 선출(First In-First Out 구조) 자료구조, 큐는 Buffer로 많이 사용함, 큐의 가장 앞 요소를 전단, 가장 마지막 요소를 후단이라고 함.삽입(Enqueue) 연산은 후단, 제거(Dequeue) 연산은 전단에서 각각 수행됨.큐의 삽입: 후단에 노드를 덧붙여서 새로운 후단을 만드는 연산큐의 삭제: 전단의 노드를 없애서 전단 뒤에 있는 노드를 새로운 전단으로 만드는 연산 만약 배열을 이용해서 큐를 만든다면?제거 연산에서 나머지 요소들을 한 칸씩 당기는 비용이 상당하다 -> 전단을 가리키는 변수 도입으로 전단의 위치만 변경.후단도 후단을 가리키는 변수에 실제 후단 위치 +1을 한 값을 담아 후단이 가리키는 위치에 데.. 2025. 4. 16.
스택 {배열 기반 스택, 링크드 리스트 기반 스택} 스택은 데이터를 바닥에서부터 쌓아 올리는 구조. 스택에서의 입 / 출력은 오직 스택의 꼭대기에서만 이루어짐. 스택 맨 아래에 있는 데이터를 꺼내려면 그 위의 데이터를 모두 걷어내야 한다. Last In-First Out , First In- LastOut 스택의 주요 기능은 삽입(Push)과 제거(Pop) 나머지 연산은 두 연산을 위한 보조 연산. 삽입 연산: 스택 위에 새로운 노드 (요소)를 쌓는 일.제거 연산: 스택에서 최상위 노드를 걷어내는 것. 배열 기반의 스택: 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성. 최상위 노드의 위치를 가리키는 변수를 두고 삽입과 제거 연산을 수행. 배열 기반 스택의 노드 구조체: 데이터만 담는 구조체로 표현됨. 배열 기반의 스택 구조체: 용량과.. 2025. 4. 15.

티스토리툴바