초보자를 위한 13가지 흥미로운 데이터 구조 프로젝트 아이디어 및 주제 [2022]

컴퓨터 과학의 세계에서 데이터 구조는 데이터 값, 그 관계 및 데이터에 적용할 수 있는 기능의 모음을 포함하는 형식을 나타냅니다. 데이터 구조는 데이터를 정렬하여 특정 알고리즘으로 더 효과적으로 액세스하고 작업할 수 있도록 합니다. 이 기사에서는 배우고, 만들고, 혁신하는 데 도움이 되는 몇 가지 유용한 데이터 구조 프로젝트 를 나열합니다!

데이터 구조 기초

데이터 구조는 다음과 같은 기본 유형으로 분류할 수 있습니다.

• 배열
• 연결 목록
• 스택
• 대기열
• 나무
• 해시 테이블
• 그래프

데이터에 대한 적절한 설정을 선택하는 것은 프로그래밍 및 문제 해결 프로세스의 필수적인 부분입니다. 그리고 데이터 구조가 구체적인 구현에서 추상 데이터 유형을 구성한다는 것을 관찰할 수 있습니다. 그 결과를 얻기 위해 정렬, 검색 등과 같은 다양한 알고리즘을 사용합니다. 데이터 구조 학습은 데이터 과학 과정에서 중요한 부분 중 하나입니다.

빅 데이터 및 분석의 부상으로 이러한 기본 사항에 대한 학습은 데이터 과학자에게 거의 필수가 되었습니다. 교육은 일반적으로 실제 경험에서 지식을 종합할 수 있도록 다양한 데이터 구조 프로젝트 를 통합합니다. 다음은 시작하는 데 도움이 되는 주제 목록입니다!

데이터 구조 프로젝트 아이디어

1. 모호한 이진 탐색 트리

이름, 숫자 등과 같은 항목은 이진 검색 트리 또는 BST라고 하는 정렬된 순서로 메모리에 저장할 수 있습니다. 그리고 이러한 데이터 구조 중 일부는 임의의 항목이 삽입되거나 삭제될 때 자동으로 높이 균형을 맞출 수 있습니다. 따라서 자체 균형 BST라고 합니다. 또한 BTree, AVL 트리 및 red-black 트리와 같이 이 유형의 다른 구현이 있을 수 있습니다. 그러나 배울 수 있는 덜 알려진 실행이 많이 있습니다. 몇 가지 예에는 AA 나무, 2-3그루의 나무, 스플레이 나무, 희생양 나무 및 트레프가 있습니다.

이러한 대안을 기반으로 프로젝트를 진행하고 다양한 시나리오에서 널리 사용되는 다른 BST보다 성능이 우수한 방법을 탐색할 수 있습니다. 예를 들어, 스플레이 트리는 심각한 시간적 국소성의 조건에서 적흑 트리보다 더 빨리 증명될 수 있습니다.

2. 메모이제이션 알고리즘에 따른 BST

동적 프로그래밍과 관련된 메모이제이션. Reduction-memoizing BST에서 각 노드는 하위 트리의 기능을 메모할 수 있습니다. 연령별로 정렬된 BST의 예를 고려하십시오. 이제 자식 노드가 각 개인의 최대 수입을 저장하도록 합니다. 이 구조를 사용하면 "18.3세에서 25.3세 사이의 사람들의 최대 소득은 얼마입니까?"와 같은 질문에 답할 수 있습니다. 또한 로그 시간에 업데이트를 처리할 수도 있습니다.

게다가, 이러한 데이터 구조는 C 언어에서 쉽게 달성할 수 있습니다. Ruby 및 편리한 API로 바인딩을 시도할 수도 있습니다. '람다'를 주문 기능과 하위 트리 메모 기능으로 지정할 수 있는 인터페이스를 찾으십시오. 전반적으로 축소 메모 BST가 추가 부기 처리가 포함된 자체 균형 BST가 될 것으로 기대할 수 있습니다.

확인: 이진 트리의 유형

3. 힙 삽입 시간

데이터 구조 프로젝트 를 찾을 때 창의적인 접근 방식으로 해결되는 뚜렷한 문제에 직면하게 됩니다. 그러한 독특한 연구 질문 중 하나는 이진 힙 데이터 구조의 평균 케이스 삽입 시간에 관한 것입니다. 일부 온라인 소스에 따르면 일정 시간이며 다른 소스에서는 log(n) 시간이라고 암시합니다.

그러나 Bollobas와 Simon은 "우선순위 대기열에 무작위로 반복 삽입"이라는 제목의 논문에서 숫자로 뒷받침되는 답변을 제공합니다. 먼저 n개의 요소를 빈 힙에 삽입하려는 시나리오를 가정합니다. 'n!'이 있을 수 있습니다. 동일한 주문이 가능합니다. 그런 다음 삽입 시간이 상수 1.7645에 의해 제한됨을 증명하기 위해 평균 비용 접근 방식을 채택합니다.

4. 우선순위 변경 매개변수가 있는 최적의 트랩

Treap은 BST와 힙의 조합입니다. 이러한 무작위 데이터 구조에는 노드에 특정 우선 순위를 할당하는 작업이 포함됩니다. 다양한 설정에서 매개변수 세트를 최적화하는 프로젝트를 진행할 수 있습니다. 예를 들어, 다른 노드보다 더 자주 액세스하는 노드에 대해 더 높은 기본 설정을 지정할 수 있습니다. 여기에서 각 액세스는 두 가지 프로세스를 시작합니다.

• 난수 선택
• 노드가 이전 우선 순위보다 높은 것으로 확인되면 해당 번호로 노드의 우선 순위를 대체합니다.

이 수정의 결과로 나무는 임의의 모양을 잃게 됩니다. 자주 액세스하는 노드는 이제 트리의 루트 근처에 있으므로 더 빠른 검색을 제공할 수 있습니다. 따라서 이 데이터 구조를 실험하고 증거에 근거하여 주장을 펼치십시오.

프로젝트가 끝나면 독창적인 발견을 하거나 노드의 우선 순위를 변경해도 속도가 빠르지 않다는 결론을 내릴 수도 있습니다. 그럼에도 불구하고 그것은 적절하고 유용한 연습이 될 것입니다.

5. kd 나무 연구 프로젝트

K 차원 트리 또는 kd 트리는 공간 데이터를 구성하고 나타냅니다. 이러한 데이터 구조는 특히 최근접이웃 및 범위 검색과 같은 다차원 키 검색에서 여러 응용 프로그램이 있습니다. kd 트리가 작동하는 방식은 다음과 같습니다.

• 이진 트리의 모든 리프 노드는 k 차원 점입니다.
• 모든 비 잎 노드는 초평면(해당 차원에 수직)을 두 개의 반 공간으로 분할합니다.
• 특정 노드의 왼쪽 하위 트리는 초평면의 왼쪽에 있는 점을 나타냅니다. 마찬가지로 해당 노드의 오른쪽 하위 트리는 오른쪽 절반에 있는 점을 나타냅니다.

한 단계 더 나아가 각 리프 노드가 루트에서 동일한 거리를 갖는 자체 균형 kd 트리를 구성할 수 있습니다. 또한 이러한 균형 잡힌 트리가 특정 종류의 응용 프로그램에 최적인지 여부를 확인하기 위해 테스트할 수 있습니다.

이를 통해 연구하고 조사하고 시도할 수 있는 5가지 흥미로운 아이디어를 다루었습니다. 이제 데이터 구조 와 알고리즘 에 대한 몇 가지 프로젝트를 더 살펴보겠습니다 .

읽기 : 인도의 데이터 과학자 급여

6. 기사의 수고

이 프로젝트에서 우리는 BFS와 DFS의 두 가지 알고리즘을 이해할 것입니다. BFS는 Breadth-First Search의 약자이며 큐 데이터 구조를 사용하여 최단 경로를 찾습니다. 반면 DFS는 깊이 우선 검색을 참조 하고 스택 데이터 구조를 순회합니다.

우선 이진 트리와 유사한 데이터 구조가 필요합니다. 이제 표준 8 X 8 체스판이 있고 게임에서 기사의 움직임을 보여주고 싶다고 가정합니다. 아시다시피, 체스에서 기사의 기본 이동은 앞으로 두 걸음, 한 걸음 물러나는 것입니다. 어느 방향으로든 향하고 충분한 회전이 주어지면 보드의 모든 사각형에서 다른 사각형으로 이동할 수 있습니다.

기사가 2차원 설정에서 한 사각형(또는 노드)에서 다른 사각형으로 이동할 수 있는 가장 간단한 방법을 알고 싶다면 먼저 아래와 같은 함수를 만들어야 합니다.

• Knight_plays([0,0], [1,2]) == [[0,0], [1,2]]
• Knight_plays([0,0], [3,3]) == [[0,0], [1,2], [3,3]]
• Knight_plays([3,3], [0,0]) == [[3,3], [1,2], [0,0]]

또한 이 프로젝트에는 다음 작업이 필요합니다.

• 보드 게임과 밤을 위한 스크립트 만들기
• 기사의 모든 가능한 움직임을 트리 구조의 자식으로 취급
• 모든 움직임이 보드에서 벗어나지 않도록 보장
• 이 경우 최단 경로를 찾기 위한 검색 알고리즘 선택
• 적절한 검색 알고리즘을 적용하여 시작 사각형에서 끝 사각형까지 가능한 최상의 이동을 찾습니다.

7. 비 C 시스템 언어의 빠른 데이터 구조

프로그래머는 일반적으로 Ruby나 Python과 같은 고급 언어를 사용하여 빠르게 프로그램을 빌드하지만 데이터 구조는 C/C++로 구현합니다. 그리고 그들은 요소를 연결하는 바인딩 코드를 만듭니다. 그러나 C 언어는 오류가 발생하기 쉬우므로 보안 문제가 발생할 수도 있습니다. 여기에 흥미로운 프로젝트 아이디어가 있습니다.

Rust 또는 Go와 같은 최신 저급 언어로 데이터 구조를 구현한 다음 코드를 고급 언어에 바인딩할 수 있습니다. 이 프로젝트를 통해 새로운 것을 시도하고 바인딩이 어떻게 작동하는지 알아낼 수 있습니다. 당신의 노력이 성공한다면, 당신은 다른 사람들이 미래에 비슷한 운동을 하도록 영감을 줄 수도 있고 데이터 구조의 더 나은 성과 지향을 주도할 수도 있습니다.

읽어보기: 초보자를 위한 데이터 과학 프로젝트 아이디어

8. 데이터 구조 검색 엔진

이 소프트웨어는 주어진 API에 대한 데이터 구조 선택을 자동화하고 가속화하는 것을 목표로 합니다. 이 프로젝트는 다양한 데이터 구조를 표현하는 새로운 방법을 보여줄 뿐만 아니라 이에 대한 추론을 갖추기 위해 함수 세트를 최적화합니다. 아래에 요약을 정리했습니다.

• 데이터 구조 검색 엔진 프로젝트는 데이터 구조와 다양한 방법 간의 관계에 대한 지식이 필요합니다.
• 모든 방법에 대해 가능한 각 복합 데이터 구조에 걸리는 시간을 계산합니다.
• 마지막으로 특정 경우에 가장 적합한 데이터 구조를 선택합니다.

읽기: 데이터 마이닝 프로젝트 아이디어

9. 이중 연결 목록을 이용한 전화번호부 적용

이 프로젝트는 주소록 응용 프로그램의 작동을 시연하고 배열, 연결 목록, 스택 및 대기열과 같은 데이터 구조에 대해서도 가르칠 수 있습니다. 일반적으로 전화번호부 관리에는 검색, 정렬 및 삭제 작업이 포함됩니다. 여기에서 검색 쿼리의 독특한 기능은 사용자가 각 문자를 입력한 후 연락처 목록에서 제안을 볼 수 있다는 것입니다. 무료로 사용 가능한 프로젝트의 소스 코드를 읽고 이를 복제하여 기술을 개발할 수 있습니다.

10. 쿼드트리를 사용한 공간 인덱싱

쿼드트리 데이터 구조는 평평한 2차원 공간을 4개의 사분면으로 재귀적으로 나눌 수 있는 특수한 유형의 트리 구조입니다. 이 트리 구조의 각 계층 노드에는 0개 또는 4개의 자식이 있습니다. 희소 데이터 저장, 이미지 처리, 공간 인덱싱 등 다양한 용도로 사용할 수 있습니다.

공간 인덱싱은 지리 공간 응용 프로그램 설계의 필수적인 부분을 형성하는 선택된 기하학적 쿼리의 효율적인 실행에 관한 것입니다. 예를 들어, Ola 및 Uber와 같은 차량 공유 애플리케이션은 지리적 쿼리를 처리하여 택시의 위치를 ​​추적하고 사용자에게 업데이트를 제공합니다. Facebook의 Nearby Friends 기능도 비슷한 기능을 가지고 있습니다. 여기서 연관된 메타데이터는 테이블 형태로 저장되며, 객체 좌표와 별도로 공간 인덱스가 생성된다. 문제의 목적은 주어진 점에 가장 가까운 점을 찾는 것입니다.

매핑, 도시 계획 및 교통 계획에서 재난 관리 및 완화에 이르기까지 광범위한 분야에서 쿼드트리 데이터 구조 프로젝트 를 추구할 수 있습니다 . 문제 해결 및 분석 능력을 키울 수 있도록 간략한 개요를 제공했습니다.

목적: 다음 작업을 가능하게 하는 데이터 구조 생성

• 위치 또는 기하학적 공간 삽입
• 특정 위치의 좌표 검색
• 특정 인접 영역에 있는 데이터 구조의 위치 수를 계산합니다.

11. 데이터 구조에 대한 그래프 기반 프로젝트

그래프의 위상 정렬에 대한 프로젝트를 시작할 수 있습니다. 이를 위해서는 DFS 알고리즘에 대한 사전 지식이 필요합니다. 다음은 두 접근 방식의 주요 차이점입니다.

• 정점을 인쇄한 다음 DFS에서 인접 정점에 대한 알고리즘을 재귀적으로 호출합니다.
• 위상 정렬에서는 먼저 인접 정점에 대한 알고리즘을 재귀적으로 호출합니다. 그런 다음 인쇄를 위해 콘텐츠를 스택에 넣습니다.

따라서 토폴로지 정렬 알고리즘은 방향성 비순환 그래프 또는 DAG를 사용하여 노드 배열을 반환합니다.

팬케이크 레시피를 주문하는 간단한 예를 살펴보겠습니다. 팬케이크를 만들려면 계란, 우유, 밀가루 또는 팬케이크 믹스, 오일, 시럽 등과 같은 특정 재료 세트가 필요합니다. 이 정보는 수량 및 부분과 함께 그래프로 쉽게 나타낼 수 있습니다.

그러나 이러한 성분을 사용하는 정확한 순서를 아는 것도 마찬가지로 중요합니다. 여기에서 토폴로지 순서를 구현할 수 있습니다. 다른 예로는 데이터베이스 쿼리 및 소프트웨어 프로젝트 일정을 최적화하기 위한 우선 순위 차트를 만드는 것이 있습니다. 다음은 참조용 프로세스의 개요입니다.

• 정점의 완료 시간을 계산하기 위해 그래프 데이터 구조에 대한 DFS 알고리즘을 호출합니다.
• 내림차순 종료 시간 순서로 정점을 목록에 저장
• 위상 정렬을 실행하여 정렬된 목록을 반환합니다.

12. 랜덤 액세스 목록을 사용한 수치 표현

과거에 본 표현에서 수치 요소는 일반적으로 이항 힙에 보관됩니다. 그러나 이러한 패턴은 다른 데이터 구조에서도 구현할 수 있습니다. Okasaki는 이진 랜덤 액세스 목록을 사용하여 수치 표현 기법을 고안했습니다. 이러한 목록에는 많은 이점이 있습니다.

• 처음부터 삽입 및 제거 가능
• 특정 인덱스에서 액세스 및 업데이트를 허용합니다.

더 알아보기: R에서 가장 일반적으로 사용되는 6가지 데이터 구조

13. 스택 기반 텍스트 편집기

일반 텍스트 편집기에는 작성 또는 편집하는 동안 텍스트를 편집하고 저장하는 기능이 있습니다. 따라서 커서 위치에 여러 변경 사항이 있습니다. 높은 효율성을 달성하려면 삽입 및 수정을 위한 빠른 데이터 구조가 필요합니다. 그리고 일반 문자 배열은 문자열을 저장하는 데 시간이 걸립니다.

이러한 문제를 해결하기 위해 갭 버퍼 및 로프와 같은 다른 데이터 구조를 실험할 수 있습니다. 최종 목표는 더 작은 연속 메모리 공간을 차지하여 일반적인 문자열보다 더 빠른 연결을 달성하는 것입니다.

결론

데이터 구조 기술은 특히 오늘날의 디지털 생태계에서 대규모 데이터 집합을 관리할 때 소프트웨어 개발의 기반을 형성합니다. Adobe, Amazon 및 Google과 같은 선도 기업은 데이터 구조 및 알고리즘 영역에서 다양한 수익성 있는 직위를 위해 고용합니다. 그리고 면접에서 채용 담당자는 이론 지식뿐만 아니라 실무 능력도 테스트합니다. 따라서 위의 데이터 구조 프로젝트 를 연습하여 문에 발을 들여 놓으세요!

데이터 과학에 대해 자세히 알아보려면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크숍, 업계 전문가와의 멘토링, 1 - 업계 멘토와 일대일, 400시간 이상의 학습 및 최고의 기업과의 취업 지원.