DataStructure And Algo
1.0.0
데이터 구조는 저장된 데이터에서보다 효율적으로 작업을 수행 할 수있는 방식으로 컴퓨터에서 데이터를 구성하고 저장하는 전문화 된 수단입니다. 데이터 구조는 컴퓨터 과학 및 소프트웨어 엔지니어링 분야에서 광범위하고 다양한 사용 범위를 가지고 있습니다. 데이터 구조는 개발 된 거의 모든 프로그램 또는 소프트웨어 시스템에서 사용되고 있습니다. 또한 데이터 구조는 컴퓨터 과학 및 소프트웨어 엔지니어링의 기초에 따라 나옵니다. 소프트웨어 엔지니어링 인터뷰 질문과 관련하여 핵심 주제입니다. 따라서 개발자로서 우리는 데이터 구조에 대한 좋은 지식이 있어야합니다.
배열 은 고정 크기의 구조로 동일한 데이터 유형의 항목을 유지할 수 있습니다. 정수 배열, 플로팅 포인트 숫자 배열, 문자열 배열 또는 배열 (예 : 2 차원 배열) 일 수 있습니다. 배열이 색인화되므로 임의의 액세스가 가능합니다.
배열에서 요소를 배열에 삽입하고 배열에서 요소를 삭제하는 것은 배열 크기가 고정되어 있으므로 바로 수행 할 수 없습니다. 배열에 요소를 삽입하려면 먼저 크기가 증가한 새 배열 (현재 크기 + 1)을 만들고 기존 요소를 복사하고 새 요소를 추가해야합니다. 감소 된 크기의 새로운 배열로 삭제하는 것도 마찬가지입니다.
연결된 목록은 서로 연결된 선형 순서의 일련의 항목으로 구성된 순차적 구조입니다. 따라서 데이터에 순차적으로 액세스해야하며 무작위 액세스가 불가능합니다. 링크 된 목록은 다이나믹 세트의 간단하고 유연한 표현을 제공합니다.
스택은 많은 프로그래밍 언어에서 일반적으로 찾을 수있는 Lifo (First in First Out - Mast에 배치 된 요소에 액세스 할 수 있음) 구조입니다. 이 구조는 실제 스택 (판 스택)과 비슷하기 때문에 "스택"이라고합니다.
표현 평가에 사용됩니다 (예 : 수학 표현을 구문 분석하고 평가하기위한 분로 된 야드 알고리즘). 재귀 프로그래밍에서 기능 호출을 구현하는 데 사용됩니다.
대기열은 FIFO (첫 번째로 첫 번째 - 처음에는 처음에 배치 된 요소에 액세스 할 수 있음) 구조로, 많은 프로그래밍 언어에서 일반적으로 찾을 수 있습니다. 이 구조는 실제 대기열과 비슷하기 때문에 "대기열"이라고합니다.
멀티 스레딩에서 스레드를 관리하는 데 사용됩니다. 대기열 시스템 (예 : 우선 순위)을 구현하는 데 사용됩니다.
해시 테이블은 각각과 관련된 키가있는 값을 저장하는 데이터 구조입니다. 또한 값과 관련된 키를 알고 있으면 조회를 효율적으로 지원합니다. 따라서 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적입니다.
직접 주소 지정은 테이블에 보관할 때 값과 키 사이의 일대일 매핑을 사용합니다. 그러나 많은 키 값 쌍이있을 때이 접근법에는 문제가 있습니다. 이 테이블은 너무 많은 레코드로 거대 할 것이며 일반적인 컴퓨터에서 사용할 수있는 메모리를 고려할 때 비현실적이거나 저장하기가 불가능할 수 있습니다. 이 문제를 피하기 위해 해시 테이블을 사용합니다.
해시 함수 (h)라는 특수 함수는 직접 주소 지정에서 위에서 언급 한 문제를 극복하는 데 사용됩니다. 직접 액세스 할 때 키 K가있는 값이 슬롯 k에 저장됩니다. 해시 함수를 사용하여 각 값이 진행되는 테이블 (슬롯)의 인덱스를 계산합니다. 주어진 키에 대해 해시 함수를 사용하여 계산 된 값을 해시 값이라고합니다.이 값은 값이 매핑되는 테이블의 인덱스를 나타냅니다.
트리는 데이터가 계층 적으로 구성되고 서로 연결되는 계층 구조입니다. 이 구조는 링크 된 목록과 다르지만 링크 된 목록에서 항목은 선형 순서로 연결됩니다. 특정 응용 분야에 적합하고 특정 제약 조건을 충족시키기 위해 지난 수십 년 동안 다양한 유형의 나무가 개발되었습니다. 몇 가지 예로는 이진 검색 트리, B 트리, Treap, Red-Black Tree, Splay Tree, AVL Tree 및 N-Ary 트리가 있습니다.
이름에서 알 수 있듯이 바이너리 검색 트리 (BST)는 데이터가 계층 구조로 구성되는 이진 트리입니다. 이 데이터 구조는 정렬 된 순서로 값을 저장합니다. 이진 검색 트리의 모든 노드는 다음 속성으로 구성됩니다.
이진 검색 트리는 다른 나무와 구별되는 독특한 속성을 나타냅니다. 이 속성은 ** 이진 검색 트리 속성 **로 알려져 있습니다.
힙은 부모 노드가 자녀와 비교되어 그에 따라 배열되는 이진 트리의 특별한 경우입니다.
힙은 2 가지 유형 일 수 있습니다.
그래프는 유한 한 정점 또는 노드 세트 와이 정점을 연결하는 가장자리 세트로 구성됩니다.
그래프의 순서는 그래프의 정점 수입니다. 그래프의 크기는 그래프의 가장자리 수입니다.
두 노드가 동일한 가장자리로 서로 연결되어 있으면 두 개의 노드가 인접 해 있다고합니다.
그래프 G는 모든 가장자리에 시작 정점이 무엇인지, 끝 꼭지점이 무엇인지를 나타내는 방향을 가지고 있다면 지시 된 그래프 라고합니다. 우리는 (u, v) 가 vertex u로부터 사건이거나 떠나며 정점 v. 자체 루프 : vertex에서 그 자체로 입사되거나 들어갑니다.
그래프 G는 모든 가장자리에 방향이 없으면 방향이없는 그래프 라고합니다. 두 정점 사이에서 두 가지 방법으로 갈 수 있습니다.
정점이 그래프의 다른 노드에 연결되어 있지 않으면 격리 된 것으로 알려져 있습니다.
트리는 노드가 알파벳의 문자를 저장하는 트리와 같은 정보 검색 데이터 구조입니다. 디지털 트리 또는 래디 딕스 트리 또는 접두사 트리라고도합니다.
TRIE 는 효율적인 정보 검색 데이터 구조입니다. Trie를 사용하면 검색 복잡성을 최적의 한계 (키 길이)로 가져올 수 있습니다. 이진 검색 트리에 키를 저장하면 균형이 잘 잡힌 BST는 m * log n에 비례하여 시간이 필요합니다. 여기서 m은 최대 문자열 길이이고 n은 트리의 키 수입니다. Trie를 사용하면 O (m) 시간으로 키를 검색 할 수 있습니다 .
1. 표준 트리 : 데이터 구조와 같은 순서 트리입니다.
2. 압축 트리 : 공간 최적화를 달성하는 데 사용됩니다. 압축 트리는 표준 트리의 고급 버전입니다.
3. 접미사 트리 : 접미사 트리는 압축 트리의 고급 버전입니다.
Trie를 사용하면 O (L) 시간에서 L이 단일 단어의 길이를 나타내는 현으로 문자열을 삽입하고 찾을 수 있습니다. 이것은 분명히 BST보다 빠릅니다. 이는 구현 방식으로 인해 해싱보다 빠릅니다. 해시 기능을 계산할 필요가 없습니다. 트리의 또 다른 장점은, 우리는 해싱으로 쉽게 불가능한 알파벳 순서로 모든 단어를 쉽게 인쇄 할 수 있다는 것입니다.
동적 프로그래밍은 문제를 하위 문제 로 나누고 결과를 다시 계산할 필요가 없도록 향후 목적으로 결과를 저장하는 기술입니다. 하위 문제는 전체 솔루션을 최적화하도록 최적화되어 최적의 하위 구조 특성이라고합니다. 동적 프로그래밍의 주요 사용은 최적화 문제를 해결하는 것입니다. 여기서 최적화 문제는 문제의 최소 또는 최대 솔루션을 찾으려고 할 때 의미합니다. 동적 프로그래밍은 솔루션이 존재하는 경우 문제의 최적 솔루션을 찾을 수 있습니다.
시간 복잡성 알고리즘 o (1) 배열에서 특정 요소를 찾는 것 : 예를 들어 : 인쇄 (my_array [97]) 배열의 크기에 상관없이 요소는 직접 조회 할 수 있으므로 한 번의 작업이 필요합니다. (이것은 실제로 알고리즘은 아니지만 시간 복잡성이 어떻게 작동하는지 이해하는 데 도움이 될 수 있습니다.)
o (n) 가장 낮은 값을 찾는 것. 알고리즘은 각 값을 한 번에 비교해야하기 때문에 알고리즘은 N 값이 가장 낮은 값을 가진 배열로 N 작업을 수행해야합니다.
O (n 2) 버블 정렬, 선택 정렬 및 삽입 정렬은이 시간 복잡성을 가진 알고리즘입니다. 시간 복잡성의 이유는 이러한 알고리즘의 페이지에 설명되어 있습니다.
큰 데이터 세트는 이러한 알고리즘을 크게 느리게합니다. N이 100에서 200 값으로 증가하면 운영 수가 30000까지 증가 할 수 있습니다!
o (n log n) QuickSort 알고리즘은 위에서 언급 한 세 가지 분류 알고리즘보다 평균적으로 더 빠르며 O (n log n)는 평균이지만 최악의 시간이 아닙니다. QuickSort의 최악의 시간은 O (N 2)이지만 QuickSort가 너무 흥미로운 평균 시간입니다. 우리는 나중에 QuickSort에 대해 배울 것입니다.
참조는이 링크에서 가져옵니다 -Sourav Saini?
