기록이 힘이다.

심볼 테이블(symbol table) 컴파일이나 인터프리터와 같은 언어 변환기에서 사용되는 자료구조 해싱 테이블(hashing table) 1. 데이터가 저장될 위치가 데이터의 값에 의해 결정되는 자료구조 2. 데이터가 저장되는 버킷(bucket)들의 배열로 만들어지며 한 버킷은 하나 이상의 레코드를 수용할 수 있음 3. 해싱 테이블에는 키(key)라는 인덱스로 자료를 접근하고 키와 배열 사이에서 해싱 함수를 이용하여 매핑(mapping)을 함 해싱 함수 1. 입력된 킷값을 해싱 테이블의 주소로 변환시켜주는 함수 2. 주어진 킷값으로부터 레코드가 저장되어 있는 주소를 직접 계산할 수 있도록 하는 수식 3. 키를 전달받아 키의 해시값을 반환하게 됨 4. 킷값을 해싱 함수에 넣어서 계산하면 해싱 테이블의 주..

1. 컴퓨터에 장한 자료 중에서 원하는 정보를 찾는 작업 2. 삽입이나 삭제 작업에서는 원소를 삽입하거나 삭제할 위치를 찾기 위해서 탐색을 수행 3. 효율적인 탐색을 위해 데어터를 빠르게 탐색할 수 있도록 잘 정리하고 분류하는 것도 중요 1. 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 2. 항목과 항목을 구별시켜주는 키 3. 탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것 1. 일렬로 나열된 데이터를 처음부터 마지막까지 순서대로 탐색하는 방법 2. 순서화되어 있지 않은 경우 사용 3. 탐색해야 하는 데이터의 양에 따라 효율이 달라지는데 데이터의 양이 많으면 탐색 시간이 증가 4. 선형 탐색이라고도 함 5. 데이터 비교 횟수는 찾..

1. 복잡한 작업 과정이나 구조를 시각적으로 표현하여 이해하기 쉽고 가시적으로 설명할 때 유용한 자료구조 2. 주어진 몇 개의 정점과 그 정점을 끝점으로 하는 선들로 이루어진 도형 3. 선형 자료구조로 표현하기 어려운 다대다 관계를 표현 가능 4. 서로 연결되어 있는 객체들 간의 관계를 표현할 수 있는 비선형 자료구조 무방향 그래프 1. 두 정점을 연결하는 간선의 방향이 없는 그래프 2. 정점 v1에서 정점 v2로 연결되는 간선은 (v1,v2)와 같이 표현 방향 그래프 1. 간선이 방향을 가지고 있는 그래프 2. 정점 v1에서 정점 v2로 연결되는 간선은 와 같이 표현 3. 방향 그래프에서 간선 와 은 서로 다른 간선 인접 1. 두 정점 vi와 vj를 연결하는 간선 (vi, vj)가 있을 때 두 정점 v..

1. 원소 간에 일대다 관계를 맺는 비선형 자료구조 2. 원소 간에 계층 관계를 맺는 계층형 자료구조 3. 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 4. 그래프 중에서 사이클을 포함하지 않는 연결 그래프 1. 노드 : 트리를 구성하는 원소들 2. 루트 노드: 트리의 시작 노드 3. 간선: 노드를 연결하는 선 4. 부모 노드: 어느 한 노드에 대하여 이 노드의 상위에 연결된 노드 5. 자식 노드: 현재 위치한 노드 아래에 연결된 노드 6. 형제 노드: 같은 부모를 같는 노드 7. 조상 노드: 서브 트리에 있는 하위 레벨의 노드들 8. 자손 노드: 서브 트리에 있는 하위 레벨의 노드들 9. 서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 10. 노드의 차수: 노..

1. 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식 2. 포인터로 자료를 순차적으로 연결함 3. 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조 연결 리스트 장점 1. 크기가 고정되지 않으며 기억 장소를 할당할 수 있는 한 계속 자료 삽입 가능 2. 중간에 데이터를 삽입하거나 삭제하는 연산이 용이함 3. 데이터 저장을 위한 기억 공간이 필요할 때마다 동적으로 만들어 쉽게 추가 가능 연결 리스트 단점 1. 구현이 복잡하고 어려움 2. 탐색 연산 비용 높음 단순 연결 리스트 1. 리스트의 각 노드에 다른 노드를 가리키는 포인터가 하나씩만 있는 것 2. 리스트를 구성하는 노드들이 한쪽 방향으로 연결된 구조 비사용 기억 공간 1. 연결 리스트를 사용하여 이미 생성된 노드들..

스택(stack) 1. 자료를 하나씩 쌓아 올린 형태로 가장 먼저 입력된 데이터는 맨 아래에 놓이고 그다음 입력되는 데이터가 그 위에 쌓이는 구조 2. 스택에서 입.출력이 이루어지는 부분을 상단(top)이라고 하고 반대쪽인 바닥 부분을 스택 하단(bottom)이라 함. 3. 가장 늦게 삽입한 원소가 가장 먼저 삭제되는 후입선출(LIFO: Last-In First-Out) 구조 4. 배열이나 연결 리스트로 구현 가능 5. 스택의 top에서 원소의 삽입과 삭제가 일어남. 6. 스택의 삽입 연산은 push, 삭제 연산은 pop 시스탬 스택 1. 수행 중인 프로그램의 함수나 서브 프로그램들의 복귀 주소와 관련 정보들을 저장 2. 프로그램에서의 호출과 복귀에 따른 수행 순서를 관리하기 위한 스택 3. 함수 호출시..

1. 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용 2. 배열의 원소를 구별하기 위해 번호(인덱스)를 사용 3. 인덱스가 주어지면 해당되는 원소가 대응되는 구조 4. 배열의 원소들은 순차적인 방법으로 기억 장소에 저장 5. 모든 자료형에 대해서 배열로 구성 가능 6. 구성 형태에 따라 1차원 배열, 2차원 배열, 3차원 배열, ... 등이 있음 인덱스 1. 배열의 원소를 간단히 구별하기 위해 사용하는 번호 2. C언어에서 배열의 인덱스는 항상 0부터 시작 배열이름(변수이름) 구칙 1. 영문자, 숫자, 밑줄을 사용함 2. 첫 글자는 숫자를 사용할 수 없음 3. 키워드나 예약어는 사용할 수 없음 리스트 1. 관련된 자료들이 일정한 순서를 이루어 나열되어 있는 구조 2. 비슷한 특성을 가진 자료들..

프로그램 = 자료구조 + 알고리즘 알고리즘이 특정한 목적을 달성하기 위한 절차라고 한다면 자료구조는 알고리즘에 필요한 자료의 집합이다. 동일한 알고리즘이라도 자료구조가 달라지면 전혀 다른 프로그램이 될 수 있기 때문에 자료에 알맞은 자료구조를 만드는 것이 매우 중요하다. 작성된 알고리즘은 다양한 자료구조들을 포함할 수 있다. 자료구조(data structure) 1. 데이터를 효율적으로 표현하고 저장하기 위해 구조화하는 것 2. 자료의 사용 방법이나 성격에 따라 효율적으로 사용하기 위하여 조직하고 저장하는 방법 자료의 형태에 따른 분류 1. 단순 구조: 정수, 실수, 문자, 문자열 2. 선형 구조: 리스트, 연결 리스트, 스택, 큐, 데크 3. 비선형 구조: 트리, 그래프 4. 파일 구조: 순차 파일, ..