컴퓨터가 발명된 이후 사람들은 ''라는 용어를 사용해 왔습니다. 데이터 '는 전송되거나 저장된 컴퓨터 정보를 나타냅니다. 그러나 주문 유형에도 존재하는 데이터가 있습니다. 데이터는 종이에 적힌 숫자나 텍스트일 수 있으며, 전자 장치의 메모리 내부에 저장된 비트와 바이트 형태일 수도 있고, 사람의 마음 속에 저장된 사실일 수도 있습니다. 세계가 현대화되기 시작하면서 이 데이터는 모든 사람의 일상 생활에서 중요한 부분이 되었고, 다양한 구현을 통해 데이터를 다르게 저장할 수 있었습니다.
데이터 사실과 수치의 모음, 또는 단일 항목 값 세트를 참조하는 특정 형식의 값 또는 값 세트입니다. 그런 다음 데이터 항목은 항목의 단순한 기본 형태로 알려지지 않은 항목 그룹인 하위 항목으로 분류됩니다.
직원 이름이 이름, 중간, 성의 세 가지 하위 항목으로 분류될 수 있는 예를 고려해 보겠습니다. 그러나 직원에게 부여된 ID는 일반적으로 단일 항목으로 간주됩니다.
그림 1: 데이터 항목의 표현
위에서 언급한 예에서는 ID, Age, Gender, First, Middle, Last, Street, Locality 등과 같은 항목이 기본 데이터 항목입니다. 반면 이름과 주소는 그룹 데이터 항목입니다.
데이터 구조란 무엇입니까?
데이터 구조 컴퓨터 과학의 한 분야입니다. 데이터 구조를 연구하면 프로세스나 프로그램의 효율성을 높이기 위해 데이터 구성과 데이터 흐름 관리를 이해할 수 있습니다. 데이터 구조는 컴퓨터 메모리에 데이터를 저장하고 구성하여 나중에 필요할 때 이러한 데이터를 쉽게 검색하고 효율적으로 활용할 수 있도록 하는 특별한 방법입니다. 데이터는 특정 데이터 구성에 대한 논리적 또는 수학적 모델을 데이터 구조라고 하는 것처럼 다양한 방식으로 관리할 수 있습니다.
특정 데이터 모델의 범위는 다음 두 가지 요소에 따라 달라집니다.
- 첫째, 데이터와 실제 객체의 명확한 상관관계를 반영할 수 있을 만큼 구조에 충분히 로드되어야 합니다.
- 둘째, 필요할 때마다 효율적으로 데이터를 처리할 수 있도록 구성이 매우 간단해야 합니다.
데이터 구조의 예로는 배열, 연결된 목록, 스택, 큐, 트리 등이 있습니다. 데이터 구조는 컴퓨터 과학의 거의 모든 측면(예: 컴파일러 디자인, 운영 체제, 그래픽, 인공 지능 등)에서 널리 사용됩니다.
데이터 구조는 프로그래머가 데이터를 효과적인 방식으로 관리할 수 있도록 해주는 많은 컴퓨터 과학 알고리즘의 주요 부분입니다. 소프트웨어의 주요 목적은 사용자의 데이터를 최대한 빨리 저장하고 검색하는 것이므로 프로그램이나 소프트웨어의 성능을 향상시키는 데 중요한 역할을 합니다.
ymail이 뭐야?
데이터 구조와 관련된 기본 용어
데이터 구조는 모든 소프트웨어나 프로그램의 구성 요소입니다. 프로그램에 적합한 데이터 구조를 선택하는 것은 프로그래머에게 매우 어려운 작업입니다.
다음은 데이터 구조가 포함될 때마다 사용되는 몇 가지 기본 용어입니다.
| 속성 | ID | 이름 | 성별 | 직위 |
|---|---|---|---|---|
| 가치 | 1234 | 스테이시 M. 힐 | 여성 | 소프트웨어 개발자 |
유사한 속성을 가진 엔터티는 엔터티 세트 . 엔터티 집합의 각 속성에는 특정 속성에 할당될 수 있는 모든 가능한 값의 집합인 값의 범위가 있습니다.
'정보'라는 용어는 의미 있는 데이터 또는 처리된 데이터의 특정 속성을 가진 데이터에 사용되는 경우가 있습니다.
데이터 구조의 필요성 이해
애플리케이션이 더욱 복잡해지고 데이터 양이 매일 증가함에 따라 데이터 검색, 처리 속도, 다중 요청 처리 등에 문제가 발생할 수 있습니다. 데이터 구조는 데이터를 효율적으로 구성, 관리 및 저장하는 다양한 방법을 지원합니다. 데이터 구조의 도움으로 데이터 항목을 쉽게 탐색할 수 있습니다. 데이터 구조는 효율성, 재사용성 및 추상화를 제공합니다.
왜 데이터 구조를 배워야 할까요?
- 데이터 구조와 알고리즘은 컴퓨터 과학의 두 가지 주요 측면입니다.
- 데이터 구조를 사용하면 데이터를 구성하고 저장할 수 있는 반면, 알고리즘을 사용하면 해당 데이터를 의미 있게 처리할 수 있습니다.
- 데이터 구조와 알고리즘을 배우는 것은 우리가 더 나은 프로그래머가 되는 데 도움이 될 것입니다.
- 우리는 더욱 효과적이고 신뢰할 수 있는 코드를 작성할 수 있게 될 것입니다.
- 또한 문제를 보다 빠르고 효율적으로 해결할 수 있을 것입니다.
데이터 구조의 목적 이해
데이터 구조는 두 가지 보완적인 목표를 충족합니다.
데이터 구조의 몇 가지 주요 기능 이해
데이터 구조의 중요한 특징 중 일부는 다음과 같습니다.
데이터 구조의 분류
데이터 구조는 다양한 방식으로 서로 관련된 구조화된 변수 세트를 제공합니다. 이는 데이터 요소 간의 관계를 나타내고 프로그래머가 데이터를 효율적으로 처리할 수 있도록 하는 프로그래밍 도구의 기초를 형성합니다.
데이터 구조를 두 가지 범주로 분류할 수 있습니다.
- 원시 데이터 구조
- 비기본 데이터 구조
다음 그림은 데이터 구조의 다양한 분류를 보여줍니다.
그림 2: 데이터 구조의 분류
원시 데이터 구조
- 이러한 데이터 구조는 기계 수준 명령어로 직접 조작하거나 작동할 수 있습니다.
- 다음과 같은 기본 데이터 유형 정수, 부동 소수점, 문자 , 그리고 부울 기본 데이터 구조에 속합니다.
- 이러한 데이터 유형이라고도 합니다. 단순 데이터 유형 , 더 이상 나눌 수 없는 문자가 포함되어 있기 때문입니다.
비원시적 데이터 구조
- 이러한 데이터 구조는 기계 수준 명령어로 직접 조작하거나 작동할 수 없습니다.
- 이러한 데이터 구조의 초점은 다음 중 하나인 데이터 요소 집합을 형성하는 것입니다. 동종의 (동일한 데이터 유형) 또는 이질적인 (다른 데이터 유형).
- 데이터의 구조와 배열에 따라 이러한 데이터 구조를 두 가지 하위 범주로 나눌 수 있습니다.
- 선형 데이터 구조
- 비선형 데이터 구조
선형 데이터 구조
데이터 요소 간의 선형 연결을 유지하는 데이터 구조를 선형 데이터 구조라고 합니다. 데이터 배열은 선형적으로 이루어지며 각 요소는 첫 번째와 마지막 데이터 요소를 제외한 후속 요소와 선행 요소로 구성됩니다. 그러나 메모리의 경우 배열이 순차적이지 않을 수 있으므로 반드시 그런 것은 아닙니다.
메모리 할당에 따라 선형 데이터 구조는 두 가지 유형으로 더 분류됩니다.
그만큼 정렬 고정된 크기를 가지며 해당 데이터는 나중에 수정될 수 있으므로 정적 데이터 구조의 가장 좋은 예입니다.
연결리스트, 스택 , 그리고 꼬리 동적 데이터 구조의 일반적인 예입니다.
선형 데이터 구조의 유형
우리가 일반적으로 사용하는 선형자료구조의 목록은 다음과 같습니다.
1. 배열
안 정렬 동일한 데이터 유형의 여러 데이터 요소를 하나의 변수로 수집하는 데 사용되는 데이터 구조입니다. 동일한 데이터 유형의 여러 값을 별도의 변수 이름에 저장하는 대신 모든 값을 하나의 변수에 함께 저장할 수 있습니다. 이 진술은 모든 프로그램에서 동일한 데이터 유형의 모든 값을 해당 데이터 유형의 하나의 배열로 통합해야 함을 의미하지는 않습니다. 그러나 동일한 데이터 유형의 일부 특정 변수가 모두 배열에 적합한 방식으로 서로 관련되는 경우가 종종 있습니다.
호환성 테스트
배열은 각 요소가 목록에서 고유한 위치를 갖는 요소 목록입니다. 배열의 데이터 요소는 동일한 변수 이름을 공유합니다. 그러나 각각은 아래 첨자라고 하는 서로 다른 색인 번호를 갖습니다. 목록의 위치를 사용하여 목록의 모든 데이터 요소에 액세스할 수 있습니다. 따라서 이해해야 할 배열의 주요 특징은 데이터가 인접한 메모리 위치에 저장되어 사용자가 해당 인덱스를 사용하여 배열의 데이터 요소를 탐색할 수 있다는 것입니다.
그림 3. 배열
배열은 다양한 유형으로 분류될 수 있습니다.
어레이의 일부 응용 분야:
- 동일한 데이터 유형에 속하는 데이터 요소 목록을 저장할 수 있습니다.
- 배열은 다른 데이터 구조의 보조 저장소 역할을 합니다.
- 배열은 또한 고정 개수의 이진 트리의 데이터 요소를 저장하는 데 도움이 됩니다.
- 배열은 행렬을 저장하는 역할도 합니다.
2. 연결리스트
ㅏ 연결리스트 데이터 요소 모음을 동적으로 저장하는 데 사용되는 선형 데이터 구조의 또 다른 예입니다. 이 데이터 구조의 데이터 요소는 링크나 포인터를 사용하여 연결된 노드로 표시됩니다. 각 노드에는 두 개의 필드가 포함되어 있으며 정보 필드는 실제 데이터로 구성되고 포인터 필드는 목록에 있는 후속 노드의 주소로 구성됩니다. 연결된 목록의 마지막 노드에 대한 포인터는 아무것도 가리키지 않으므로 널 포인터로 구성됩니다. 배열과 달리 사용자는 요구 사항에 따라 연결 목록의 크기를 동적으로 조정할 수 있습니다.
그림 4. 연결리스트
연결 목록은 여러 유형으로 분류될 수 있습니다.
연결 목록의 일부 응용 프로그램:
- 연결된 목록은 미리 정의된 크기의 스택, 큐, 이진 트리 및 그래프를 구현하는 데 도움이 됩니다.
- 동적 메모리 관리를 위해 운영 체제의 기능을 구현할 수도 있습니다.
- 연결된 목록을 사용하면 수학 연산에 대한 다항식 구현도 가능합니다.
- 순환 연결 목록을 사용하여 작업을 라운드 로빈으로 실행하는 운영 체제나 응용 프로그램 기능을 구현할 수 있습니다.
- 순환 연결 목록은 마지막 슬라이드가 표시된 후 사용자가 첫 번째 슬라이드로 돌아가야 하는 슬라이드 쇼에도 유용합니다.
- 이중 연결 목록은 웹 사이트의 열린 페이지에서 앞뒤로 이동하기 위해 브라우저에서 앞으로 및 뒤로 버튼을 구현하는 데 사용됩니다.
3. 스택
ㅏ 스택 다음을 따르는 선형 데이터 구조입니다. LIFO Stack의 한쪽 끝(Top)에서 삽입, 삭제 등의 작업을 수행할 수 있는 Last In, First Out(Last In, First Out) 원리입니다. 스택은 연속 메모리인 배열과 비연속 메모리인 연결 목록을 사용하여 구현할 수 있습니다. 스택의 실제 예로는 책 더미, 카드 더미, 돈 더미 등이 있습니다.
그림 5. 스택의 실제 예
위 그림은 스택 상단에서 새 책을 삽입하고 제거하는 것과 같이 작업이 한쪽 끝에서만 수행되는 스택의 실제 예를 나타냅니다. 이는 스택의 삽입 및 삭제가 스택의 최상위에서만 수행될 수 있음을 의미합니다. 우리는 주어진 시간에 스택의 상단에만 접근할 수 있습니다.
dbms의 데이터베이스 디자인
스택의 주요 작업은 다음과 같습니다.
그림 6. 스택
스택의 일부 응용 분야:
- 스택은 재귀 작업을 위한 임시 저장 구조로 사용됩니다.
- 스택은 함수 호출, 중첩 작업, 지연/연기된 함수를 위한 보조 저장 구조로도 활용됩니다.
- 스택을 사용하여 함수 호출을 관리할 수 있습니다.
- 스택은 다양한 프로그래밍 언어의 산술 표현식을 평가하는 데에도 사용됩니다.
- 스택은 중위 표현식을 후위 표현식으로 변환하는 데에도 유용합니다.
- 스택을 사용하면 프로그래밍 환경에서 표현식의 구문을 확인할 수 있습니다.
- 스택을 사용하여 괄호를 일치시킬 수 있습니다.
- 스택을 사용하여 문자열을 뒤집을 수 있습니다.
- 스택은 역추적을 기반으로 문제를 해결하는 데 도움이 됩니다.
- 그래프 및 트리 순회에서 깊이 우선 검색에 스택을 사용할 수 있습니다.
- 스택은 운영 체제 기능에도 사용됩니다.
- 스택은 편집 시 UNDO 및 REDO 기능에도 사용됩니다.
4. 꼬리
ㅏ 대기줄 요소 삽입 및 삭제에 대한 일부 제한이 있는 스택과 유사한 선형 데이터 구조입니다. 대기열의 요소 삽입은 한쪽 끝에서 수행되고 제거는 다른 끝 또는 반대쪽 끝에서 수행됩니다. 따라서 큐 데이터 구조는 데이터 요소를 조작하기 위해 FIFO(선입선출) 원칙을 따른다는 결론을 내릴 수 있습니다. 대기열 구현은 배열, 연결 목록 또는 스택을 사용하여 수행할 수 있습니다. 대기열의 실제 예로는 매표소의 줄, 에스컬레이터, 세차장 등이 있습니다.
그림 7. 대기열의 실제 예
위 이미지는 항상 먼저 온 고객이 먼저 서빙되는 Queue를 이해하는 데 도움이 되는 영화 매표소의 실제 일러스트입니다. 마지막에 도착하는 고객은 의심할 여지없이 가장 마지막에 서비스를 받을 것입니다. 대기열의 양쪽 끝은 열려 있으며 서로 다른 작업을 실행할 수 있습니다. 또 다른 예는 고객이 요청한 서비스를 제공한 후 앞쪽 끝에서 제거되고 뒤쪽 끝에서 고객이 삽입되는 푸드 코트 라인입니다.
다음은 대기열의 주요 작업입니다.
그림 8. 대기줄
대기열의 일부 응용 프로그램:
- 대기열은 일반적으로 그래프의 범위 검색 작업에 사용됩니다.
- 큐는 사용자가 누른 키를 저장하는 키보드 버퍼 큐와 프린터에서 인쇄된 문서를 저장하는 인쇄 버퍼 큐와 같이 운영 체제의 작업 스케줄러 작업에도 사용됩니다.
- 대기열은 CPU 예약, 작업 예약 및 디스크 예약을 담당합니다.
- 우선순위 대기열은 브라우저에서 파일을 다운로드하는 작업에 활용됩니다.
- 큐는 주변 장치와 CPU 간에 데이터를 전송하는 데에도 사용됩니다.
- 큐는 또한 CPU에 대한 사용자 애플리케이션에 의해 생성된 인터럽트를 처리하는 역할도 합니다.
비선형 데이터 구조
비선형 데이터 구조는 데이터 요소가 순차적으로 배열되지 않은 데이터 구조입니다. 여기서는 데이터의 삽입과 제거가 선형 방식으로 가능하지 않습니다. 개별 데이터 항목 간에는 계층적 관계가 존재합니다.
비선형 데이터 구조의 유형
다음은 우리가 일반적으로 사용하는 비선형 데이터 구조 목록입니다.
JSON 파일
1. 나무
트리는 비선형 데이터 구조이며 트리의 각 노드가 값과 다른 노드('자식')에 대한 참조 목록을 저장하는 노드 컬렉션을 포함하는 계층 구조입니다.
트리(Tree) 데이터 구조는 데이터를 컴퓨터에 배열하고 수집하여 보다 효율적으로 활용하기 위한 특화된 방법입니다. 여기에는 중앙 노드, 구조 노드 및 가장자리를 통해 연결된 하위 노드가 포함됩니다. 트리 데이터 구조는 뿌리, 가지, 잎이 연결되어 구성되어 있다고 말할 수도 있습니다.
그림 9. 나무
나무는 여러 유형으로 분류될 수 있습니다.
나무의 일부 응용:
- 트리는 디렉토리 및 파일 시스템과 같은 컴퓨터 시스템에서 계층 구조를 구현합니다.
- 트리는 웹 사이트의 탐색 구조를 구현하는 데에도 사용됩니다.
- Trees를 사용하면 Huffman의 코드와 같은 코드를 생성할 수 있습니다.
- 트리는 게임 애플리케이션의 의사 결정에도 도움이 됩니다.
- 트리는 우선순위 기반 OS 스케줄링 기능을 위한 우선순위 큐 구현을 담당합니다.
- 트리는 또한 다양한 프로그래밍 언어의 컴파일러에서 표현식과 명령문을 구문 분석하는 역할을 담당합니다.
- 트리를 사용하여 데이터베이스 관리 시스템(DBMS)의 인덱싱을 위한 데이터 키를 저장할 수 있습니다.
- 스패닝 트리를 사용하면 컴퓨터 및 통신 네트워크에서 의사결정을 라우팅할 수 있습니다.
- 트리는 인공지능(AI), 로봇 공학, 비디오 게임 애플리케이션에서 구현되는 경로 찾기 알고리즘에도 사용됩니다.
2. 그래프
그래프는 유한한 수의 노드 또는 정점과 이를 연결하는 가장자리로 구성된 비선형 데이터 구조의 또 다른 예입니다. 그래프는 문제 영역을 소셜 네트워크, 회선 네트워크, 전화 네트워크와 같은 네트워크로 표시하여 현실 세계의 문제를 해결하는 데 활용됩니다. 예를 들어, 그래프의 노드나 정점은 전화 네트워크의 단일 사용자를 나타낼 수 있고 가장자리는 전화를 통한 사용자 간의 링크를 나타낼 수 있습니다.
그래프 데이터 구조 G는 아래와 같이 정점 세트 V와 모서리 세트 E로 구성된 수학적 구조로 간주됩니다.
G = (V,E)
그림 10. 그래프
위 그림은 7개의 정점 A, B, C, D, E, F, G와 10개의 모서리 [A, B], [A, C], [B, C], [B, D]를 갖는 그래프를 나타냅니다. [B, E], [C, D], [D, E], [D, F], [E, F] 및 [E, G].
자바 int를 char로
정점과 가장자리의 위치에 따라 그래프는 여러 유형으로 분류될 수 있습니다.
그래프의 일부 응용:
- 그래프는 교통, 여행, 통신 애플리케이션에서 경로와 네트워크를 나타내는 데 도움이 됩니다.
- 그래프는 GPS에서 경로를 표시하는 데 사용됩니다.
- 그래프는 또한 소셜 네트워크 및 기타 네트워크 기반 애플리케이션의 상호 연결을 나타내는 데 도움이 됩니다.
- 그래프는 매핑 애플리케이션에 활용됩니다.
- 그래프는 전자상거래 애플리케이션에서 사용자 선호도를 나타내는 역할을 합니다.
- 그래프는 지역 또는 지방 기업에 제기된 문제를 식별하기 위해 유틸리티 네트워크에서도 사용됩니다.
- 그래프는 조직 내 리소스의 활용도와 가용성을 관리하는 데도 도움이 됩니다.
- 그래프는 하이퍼링크를 통해 페이지 간의 연결을 표시하기 위해 웹 사이트의 문서 링크 맵을 만드는 데에도 사용됩니다.
- 그래프는 로봇 동작과 신경망에도 사용됩니다.
데이터 구조의 기본 작업
다음 섹션에서는 모든 데이터 구조에서 데이터를 조작하기 위해 수행할 수 있는 다양한 유형의 작업에 대해 설명합니다.
- 컴파일 타임
- 실행 시간
예를 들어, malloc() 함수는 C 언어에서 데이터 구조를 만드는 데 사용됩니다.
추상 데이터 유형 이해
에 따라 국립표준기술연구소(NIST) 에서 데이터 구조는 더 나은 알고리즘 효율성을 위해 일반적으로 메모리에 정보를 배열하는 것입니다. 데이터 구조에는 연결된 목록, 스택, 큐, 트리 및 사전이 포함됩니다. 또한 사람의 이름이나 주소와 같은 이론적 실체일 수도 있습니다.
위에서 언급한 정의에서 데이터 구조의 작업에는 다음이 포함된다는 결론을 내릴 수 있습니다.
- 목록에서 항목을 추가하거나 삭제하는 것과 같은 높은 수준의 추상화입니다.
- 목록의 항목을 검색하고 정렬합니다.
- 목록에서 우선순위가 가장 높은 항목에 액세스합니다.
데이터 구조가 그러한 작업을 수행할 때마다 이를 데이터 구조라고 합니다. ADT(추상 데이터 유형) .
데이터에 대한 작업과 함께 데이터 요소 집합으로 정의할 수 있습니다. '추상'이라는 용어는 데이터와 여기에 정의된 기본 작업이 구현과 별개로 연구되고 있다는 사실을 의미합니다. 여기에는 데이터를 사용하여 무엇을 할 수 있는지가 포함되며, 데이터를 어떻게 수행할 수 있는지가 포함되지 않습니다.
ADI 구현에는 기본 작업을 위한 데이터 요소와 알고리즘을 저장하기 위한 저장 구조가 포함되어 있습니다. 배열, 연결리스트, 큐, 스택 등과 같은 모든 데이터 구조는 ADT의 예입니다.
ADT 사용의 이점 이해
현실 세계에서 프로그램은 새로운 제약이나 요구 사항의 결과로 발전하므로 프로그램을 수정하려면 일반적으로 하나 이상의 데이터 구조를 변경해야 합니다. 예를 들어, 각 직원에 대한 자세한 정보를 추적하기 위해 직원의 기록에 새 필드를 삽입한다고 가정해 보겠습니다. 이 경우 Array를 Linked 구조로 대체하여 프로그램의 효율성을 향상시킬 수 있습니다. 이러한 상황에서 수정된 구조를 활용하는 모든 프로시저를 다시 작성하는 것은 적합하지 않습니다. 따라서 더 나은 대안은 데이터 구조를 구현 정보에서 분리하는 것입니다. 이것이 ADT(추상 데이터 유형) 사용의 기본 원칙입니다.
데이터 구조의 일부 응용
다음은 데이터 구조의 일부 응용 프로그램입니다.
- 데이터 구조는 컴퓨터 메모리의 데이터를 구성하는 데 도움이 됩니다.
- 데이터 구조는 데이터베이스의 정보를 표현하는 데도 도움이 됩니다.
- 데이터 구조를 사용하면 데이터를 검색하는 알고리즘을 구현할 수 있습니다(예: 검색 엔진).
- 데이터 구조를 사용하여 데이터를 조작하는 알고리즘을 구현할 수 있습니다(예: 워드 프로세서).
- 데이터 구조(예: 데이터 마이너)를 사용하여 데이터를 분석하는 알고리즘을 구현할 수도 있습니다.
- 데이터 구조는 데이터를 생성하는 알고리즘을 지원합니다(예: 난수 생성기).
- 데이터 구조는 데이터를 압축하고 압축을 푸는 알고리즘도 지원합니다(예: zip 유틸리티).
- 또한 데이터 구조를 사용하여 데이터를 암호화하고 해독하는 알고리즘을 구현할 수도 있습니다(예: 보안 시스템).
- 데이터 구조의 도움으로 파일과 디렉터리를 관리할 수 있는 소프트웨어(예: 파일 관리자)를 구축할 수 있습니다.
- 또한 데이터 구조를 사용하여 그래픽을 렌더링할 수 있는 소프트웨어를 개발할 수도 있습니다. (예: 웹 브라우저 또는 3D 렌더링 소프트웨어)
그 외에도 앞서 언급한 것처럼 원하는 소프트웨어를 구축하는 데 도움이 될 수 있는 데이터 구조의 다른 응용 프로그램이 많이 있습니다.