본문 바로가기

분류 전체보기

 (271)
3. 이진 트리 이진 트리 모든 노드의 차수가 2이하인 트리. 완전 이진 트리 노드 수가 n개일 때 트리의 인덱스가 각각의 노드 인덱스와 일치 하는 트리. 쉽게 말하면 앞에서부터 순서대로 잘 채워진 이진 트리이다. 완전 이진 트리의 특성 - 부모의 인덱스 : i/2 - 좌측 자식의 인덱스 : 2*i, 우측 자식의 인덱스 2*i +1 - 1차원 배열로 표현 - 링크의 형태로 표현 ​ 순회 트리의 모든 노드를 방문하는 알고리즘 1. 전위 순회 root, left subtree, right subtree 순으로 탐색하는 알고리즘 2. 중위 순회 left subtree, root, right subtree 순으로 탐색하는 알고리즘 3. 후위 순회 left subtree, right subtree, root 순으로 탐색하는 알고..
4. 히프 트리(Heap Tree) 히프 트리 삽입은 일반적인 큐와 같이 맨 마지막에 삽입이 되고 삭제의 경우 우선순위 큐의 형태로 삭제되는 트리이다. 중요한 점은 부모는 항상 자식보다 크면 최대 힙, 자식보다 작으면 최 소힙이다. 히프트리는 완전 이진 트리로 배열로 구현한다. 최대히프의 삽입 먼저 가장 트리의 마지막 위치에 삽입한 뒤, 부모와 비교하며 올라간다. 최대히프의 삭제 우선순위가 가장 높은 루트를 삭제하고 가장 마지막 노드를 임시적으로 루트에 배치하여 좌우 자식과 비교하며 노드를 내린다. class heap{ private: int[] tree; int capacity; int size; public: heap(){ capacity=100; size=1; tree=new int[capacity]; } //최대 히프 트리의 삽입 ..
5. 이진 탐색 트리(BST, Binary Searching Tree) 이진 탐색 트리 이진 탐색 트리는 아래의 조건을 만족해야 한다. ①각 노드에서 왼쪽 자식은 부모의 값보다 작고, 오른쪽 자식은 부모의 값보다 크다. ②각 노드는 모두 고유한 값을 갖는다. 연결리스트로 구현된 이진 탐색 트리 코드 class BST; class Node{ friend BST; private: int key; Node *left; Node *right; public: Node(int k=0, Node *l=0, Node *r=0){ key = k; left = l; right = r; } }; class BST{ private: Node *root; public: BST(){root=0;} void insert(int x){} void remove(int x){} }; 이진 탐색 트리에서의 ..
6. 그래프 1. 그래프 표현법 - 무방향, 비가중치 인접행렬 희소그래프가 아닌 경우에 주로 사용된다. (희소 그래프일 경우 탐색에 불필요한 자원이 낭비된다.) 정점이 서로 연결된 경우 1로 표시하고 그렇지 않은 경우 0으로 표시한다. 장점으로는 구현이 간단하고 연결을 확인하는데에 O(1)의 시간복잡도만 필요하다. (1과 2의 연결확인은 length[1][2]의 값을 확인하면 됨.) 단점으로는 특정 노드에 연결된 모든 노드 n개를 방문하기 위해서 O(n)의 시간 복잡도가 필요하다. 그렇기에 위에서 말한 희소그래프가 아닌 경우에 주로 사용된다. 예를들어 노드가 1억개이고 간선이 두개 뿐인 희소그래프를 고려해보면, 특정 노드에 연결된 노드가 무엇인지 찾기 위해 1억번의 탐색이 필요하다. class Graph{ priva..
7. 탐색 1. 순차탐색 시간복잡도 : O(n) 특정 값을 순서대로 탐색하여 찾는 탐색 알고리즘. Template int SeqSearch(T*a, const int n, const T& k) // a[0:n-1]을 왼쪽에서 오른쪽으로 탐색한다. // a[i]의 키 값이 k 와 같은 가장 작은 i를 반환한다. // 그런 i가 없으면 -1을 반환한다 { int i; for (i=0; i= n) return -1; return i; } 프로그램 분석: 최선의 경우: 1, 최악의 경우: n, 평균의 경우: (n+1)/2 시간복잡도: O(n) 2. 이진 탐색 시간복잡도 : O(log n) 특정 값을 기준으로 두고 값을 찾는다. 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. template int BinarySearc..
8. 정렬(Sort) 1. 삽입 정렬 시간복잡도 : O(n²) template void Insert(const T& e, T *a, int i) {// e를 정렬된 리스트 a[1:i]에 삽입하여 결과 // 리스트 a[1: i+1]도 정렬되게 한다. // 배열 a는 적어도 i+2 원소를 포함할 공간을 가지고 있어야 한다. // a[0] = -∞; 가 저장되어 있음. while(e
9. Hashing(해싱) 해싱 해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. [이름, 속성] 쌍의 집합으로 되어 있다 해싱 함수(Hashing Function) 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 중간 제곱(mid-square) 함수 식별자를 제곱한 후에 그 결과의 중간에 적당한 수의 비트를 취하여 버켓주소로 한다. 비트 수는 버켓의 크기에 따라 결정된다. (r 비트는 2r 버켓 크기) ​ 제산(division) 함수 hD(x)= x % D 버켓의 범위는 0에서 (D-1)까지 이며, D는 20보다 작은 소수로 나누어지지 않으면 충분하다고 실험적으로 입증되었다. ​ 접지(folding) 함수 식별자 x를 여러 부분으로 나눈 후 나..
(소개) HEALTH-ER 운동인을 위한 앱 기능 소개 1. 운동법 : 각 운동별 수행 방법을 소개함 2. 알람 : 휴식시간을 설정하여 알람을 울림. 3. 운동 기록 : 사용자가 수행한 운동을 기록함. 4. 추천 프로그램 : 사용자를 위한 기본적인 프로그램 5. 커스텀 프로그램 : 사용자가 직접 프로그램을 구성함. 6. 1-RM 기록 : 사용자가 수행한 3대 운동 무게를 기록함. 7. 몸무게 기록: 사용자의 몸무게 변화를 기록함. 어플리케이션 다운로드 HEALTH-ER (헬서) 헬스인을 위한 앱 - Google Play 앱 운동하는 사람들을 위한 앱 HEALTH-ER 입니다. 1. 운동 방법 : 운동을 이미지와 함께 자세와 방법 TIP을 제공합니다. 2. 프로그램 : 무분할, 2분할,...,5분할 등 프로그램을 계획합니다. 3. 운동일지 : 수행한..

티스토리툴바