CS40 [자료구조] 힙(Heap) 🟡 힙(Heap) - 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 자료구조 - 다음과 같은 힙 속성을 만족해야 한다. A가 B의 부모노드이면, A의 key값과 B의 key값 사이에는 대소관계가 성립한다. 🟡 힙의 종류 ① 최대 힙 - 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙 ② 최소 힙 - 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙 * 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 🟡 힙의 시간 복잡도 - 힙에서의 데이터 삽입과 삭제에 대한 시간 복잡도는 O(log n) 🟡 힙의 연산 ① 삽입 - 새로운 요소를 힙에 추가한다. - 일반적으로 맨 마지막 위치에 요소를 추가한 후, 부모노드와 비교하여 위.. 2023. 8. 25. [알고리즘] 매개변수 탐색(Parametric Search) 🟡 매개변수 탐색(Parametric Search) - 어떤 조건을 만족하는 함수나 값 중에서 특정한 값을 찾거나 최적화 하는 알고리즘 - 주로 수치 계산 문제나 최적화 문제에서 사용된다. 🟡 매개변수 탐색이 사용되는 상황 ① 조건을 만족하는 값 찾기 - 어떤 함수나 조건식이 주어졌을 때, 이 조건을 만족하는 특정 값을 찾기 위해 사용한다. - 예를들어, 어떤 함수 f(x)의 값이 특정 값 k와 같아지는 x를 찾는 문제 ② 최적화 문제 - 주어진 함수나 목적 함수를 최대화 또는 최소화하는 변수 값을 찾는 문제에도 적용될 수 있다. - 함수 값의 변화를 추적하며 최적 값에 접근한다. 🟡 매개변수 탐색 수행 단계 ① 매개변수 범위 정의 - 매개변수 탐색에 사용될 매개변수의 범위를 정의한다. ② 이분 탐색 -.. 2023. 8. 25. [자료구조] 우선순위 큐(Priority Queue) 🟡 우선순위 큐(Priority Queue) - 원소들이 우선순위를 가지고 있을 때 사용되는 자료구조 - 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. - 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다. - 작업 스케줄링, 그래프 알고리즘 등 다양한 분야에서 활용된다. 🟡 우선순위 큐의 연산 ① 삽입: 하나의 원소를 우선순위를 지정하여 큐에 추가한다. ② 삭제: 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다. 🟡 우선순위 큐의 구현 - 우선순위 큐는 추상적인 개념이다. 그러므로 다양한 방법들을 이용해 구현될 수 있다. - 대표적인 방법들 ① 힙: 가장 많이 사용되는 방법. 이진 트리 자료구조의 일종이다. O(logN)의 .. 2023. 8. 24. [알고리즘] 분할정복을 사용한 거듭제곱 계산 알고리즘 🟡 분할 정복을 사용한 거듭제곱 연산법 - x^n을 다음과 같이 쪼갤 수 있다. 1) n이 짝수인 경우 x^n = x^(n/2) * x^(n/2) 2) n이 홀수인 경우 x^n = x^(n-1/2) * x^(n-1/2) * x 🟡 시간 복잡도 - 일반적인 방법으로 x^n을 계산하려면 시간복잡도는 O(n)이다. - 그러나 분할정복을 사용하여 계산하면 시간복잡도는 O(log n)이다. 2023. 8. 23. [알고리즘] 분할 정복 알고리즘(Divide and Conquer) 🟡 분할 정복 알고리즘(Divide and Conquer) - 큰 문제를 작은 부분 문제로 분할하여 해결하는 알고리즘이다. - 주어진 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제를 재귀적으로 해결한 후, 그 해답을 결합하여 원래 문제의 해답을 얻는 방법이다. 🟡 분할 정복 알고리즘의 단계 ① 분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할한다. ② 정복(Conquer): 작은 부분 문제들을 재귀적으로 해결한다. ③ 결합(Combine): 작은 부분 문제들의 해답을 결합하여 원래 문제의 해답을 얻는다. 🟡 분할정복 알고리즘 예시 ① 병합 정렬(Merge Sort) ② 퀵 정렬(Quick Sort) ③ 이진 검색(Binary Search) ④ 카라츠바 곱셈 알고리즘(Karatsuba) 2023. 8. 18. [알고리즘] 그래프 표현방법 3가지 🟡 그래프 표현방법 3가지 ① 에지 리스트(Edge List) ② 인접 행렬(Adjacency Matrix) ③ 인접 리스트(Adjacency List) 🟡 에지 리스트 - 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 이 경우 배열의 열은 2개면 된다. - 혹은 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.이 경우 배열의 열은 3개를 사용한다. - 에지 중심으로 표현한 것이라, 이를 사용하여 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다. - 에지 리스트는 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다. 🟡 인접 행렬 - 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. - 노드 중심으로 그래프를 표현한다. -.. 2023. 8. 14. 이전 1 2 3 4 ··· 7 다음
