:)

Chapter 7.1-7.7Time ComplexityInsertion SortSelection SortMerge SortQuick SortHeap Sort예제 14 풀이합병정렬 알고리즘에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2n log n이 됨을 증명하기알고리즘 2.2문제) n개의 원소를 비내림차순으로 정렬입력) 양의 정수 n, 배열 S (인덱스는 1부터 n까지)출력) 원소를 비내림차순으로 정렬한 배열 Svoid mergesort ( int n, keytype S[] ) { if ( n > 1 ) { const int h = └n/2┘, m = n - h; keytype U[1...h], V[1...m]; copy S[1] through..

linear median finding algorithm시간복잡도가 Θ(n)임을 보여주기n T(n) ≤ c T(n) = Θ(n)hashing function에서 계수 a가 0이 아니어야 하는 이유계수 a가 0일 경우 데이터의 key값이 없어지기 때문에 0이 아니어야 한다.예제 8.1 풀이만약 n개의 키가 m개의 바구니에 균일하게 분포되어 있고, 각 키가 검색 키가 될 확률이 거의 같다고 하면, 성공한 검색의 평균 비교 횟수는 다음과 같다.n/2m + 1/2만약 키가 균일하게 분포되어 있고 n=2m이라면, 실패한 검색은 각각 2m/m = 2번의 비교만 필요하고, 성공한 검색은 평균 비교 횟수가 다음과 같다.2m/2m + 1/2 = 3/2만약 모두 같은 바구니에 분포되어 있을 경우 순차검색과 유사하나 같은..

1. n개의 노드에서 트리의 가장 작은 높이가 Ω(log n) = - 1 + log(n+1)임을 증명하기트리의 기본적인 특징: n개의 노드를 가진 트리는 n-1개의 간선을 갖는다.: 높이가 h인 이진트리가 가질 수 있는 최대 노드 개수는 2^(h+1)-1모든 레벨에 노드가 완전히 차있게 하여 높이를 가장 작게 만들기 위해서는 가장 많은 노드 개수를 가져야 한다.n n + 1 log(n+1) -1 + log(n+1) -> Ω(log n) = - 1 + log(n+1)2. direct access arrays의 공간을 축소할 때 linked list 자료구조를 사용할 수 있습니다. linked list를 사용할 경우 발생할 문제를 시간 복잡성과 함께 설명하기array와 linked list 비교locatio..

개념 요약Sorting algorithm: 배열의 요소를 특정 순서로 정렬하는 알고리즘1) Permutation sort (순열 정렬): 정렬된 입력을 찾을 때까지 순열을 생성한다.2) Selection sort (선택 정렬): 정렬되지 않은 배열에서 가장 작은 요소를 선택하고 해당 요소를 정렬되지 않은 배열의 시작에 배치한다.3) Insertion sort (삽입 정렬): 배열에서 정렬되지 않은 부분의 값이 선택되어 정렬된 부분의 올바른 위치에 배치된다.4) Merge sort (합병 정렬): 배열을 반으로 분할하여 각각 따로 정렬한 뒤 합병하여 정렬한다.ch.1 34번 문제풀이문제 : 아래 중첩 루프의 시간 복잡도 T(n) 구하기(어떤 양의 정수 k에 대해서 n이 2의 거듭제곱이라고 가정)i = n;..

생일 문제(Birthday Problem): 임의로 모인 사람들 중 생일이 같은 두 명이 존재할 확률을 구하는 문제Algorithms - Birthday Data.csv: 학생들의 이름, 서로 식별 가능한 ID, 생일 날짜 저장사용 언어 : Python생일이 같은 두 사람을 수동으로 결정하기 위해 pseudo code 작성bd_problem 함수를 만듦def bd_problem(총 모인 사람의 인원수): n_p 변수 정의 for문 시작 for i in range(n_p, 365): p 변수 정의 n_p와 p간의 관계 최종적인 확률을 probability 변수에 저장 임의로 모인 사람들의 총 인원수와 그 중 2명 이상의 생일이 겹칠 확률..

📖 벨만포드(Bellman-Ford) 알고리즘벨만포드(Bellman-Ford) 알고리즘이란?: 최단 경로(shortest path)를 찾는 알고리즘 중 하나다익스트라(Dijkstra) 알고리즘과 차이점: 다익스트라는 음의 가중치가 있는 그래프에서 작동하지 않으며 벨만포드는 이러한 그래프에서 작동한다.: 벨만포드는 다익스트라보다 단순하며 분산 시스템에 적합하다.: 다익스트라 알고리즘은 Greedy 알고리즘이며 시간 복잡도는 O((V+E)LogV)이다. 벨만포드의 시간 복잡도는 O(V * E)로 다익스트라보다 더 크다.벨만포드 알고리즘 예시↓위에 제시된 예시의 벨만포드 알고리즘 과정을 그림으로 표현↓벨만포드 알고리즘 코드#include using namespace std;struct Edge { int ..

📖 그래프 표현 방법그래프 표현 방법으로는 인접 행렬과 인접 리스트가 존재한다.인접 행렬(예시)(코드)-그래프 형태는 무방향 그래프라고 가정한다.#includeusing namespace std;int vertArr[20][20];int count = 0;void displayMatrix(int v) { int i, j; for(i = 0; i 인접 리스트(예시)(코드)-그래프 형태는 무방향 그래프라고 가정한다.#include#include#includeusing namespace std;void displayAdjList(list adj_list[], int v) { for(int i = 0; i "; list :: iterator it; for(it = adj_list[i]...

📖 그래프정의: Vertices와 Edges로 구성된 비선형 데이터 구조: 그래프(G)는 정점(V)와 간선(E)로 표현 -> G=(V,E)관련 용어정점(또는 노드)여러 가지 특성을 가질 수 있는 객체V(G) : 그래프 G의 정점들의 집합간선(또는 링크)- 정점들 간의 관계- E(G) : 그래프 G의 간선들의 집합📖 그래프 탐색 과정그래프 탐색: 하나의 정점에서 시작하여 모든 정점들을 차례대로 한번씩 방문하는 것그래프 탐색 과정은 BFS와 DFS 알고리즘을 바탕으로 이루어진다.📍 BFS (Breadth-First Search)정의 : 너비 우선 탐색아래 예시로 제시된 그래프를 활용한 탐색 과정은 다음과 같다.(예시)(탐색 과정)-> b부터 탐색 시작-> d와 a 방문 (이때 d,a는 큐로 enqueu..

📖 Data structures augmentation데이터 구조가 효율적으로 구현될 수 있도록 기존 데이터 구조에 추가 정보 추가하는 것이진 탐색 트리 노드에 서브 트리 노드 개수 정보 추가: root에서 내려와 해당 value보다 작거나 같으면 1을 더하고 왼쪽에 있는 서브 트리 개수를 더해준다.📖 Rank이진 탐색 트리에서 노드의 Rank는 왼쪽 서브트리의 노드 수가 중요하다.-코드int getRank(Node* root, int x){ if (root->data == x) return root->leftSize; if (x data) { if (!root->left) return -1; else retur..

📖스케줄링 문제에 접근하는 이진 탐색 트리정의 : 이진트리 기반의 탐색을 위한 자료구조이진트리 : 모든 노드가 2개의 subtree를 갖는 트리모든 노드의 차수는 2 이하 -> 최대 2개까지의 자식노드를 가질 수 있다left subtree와 right subtree는 반드시 구별되어야 한다탐색 : 컴퓨터, 자료구조에서의 핵심적인 응용 분야특징nearly complete X왼쪽 노드 키 각각의 노드가 2개이하의 노드를 갖고 있어야한다모든 노드 x에 대해 if y가 x의 left subtree에 있다면 key(y) if y가 right subtree에 있다면 key(y) >= key(x)balanced가 되기 위해서는 left(h)와 right(h)가 비슷해야한다연산insert(n): 이진 탐색 트리의 특..