자료구조 출석수업 요점정리

자료구조 출석수업 요점정리

알고리즘의 개념 및 특성

• 특정 문제를 해결하기 위해 기술한 일련의 논리적 순서
• 입출력 - 입츨력이 가능해야 한다.
• 명확성 - 명령은 명확해야한다.
• 유한성 - 한정된 단계 실행후 종료되어야 한다.
• 유효성 - 컴퓨터 처리가능해야 한다.

순환의 개념 및 예

• 분할정복의 특성을 가진 문제에 적합
• 분할정복 - 어떤 복잡한 문제를 직접 간단하게 풀수 있는 작은 문제로 분할하여 해결하려는 방법
• 직접순환 - A -> A`
• 간접순환 - A -> B -> A

배열

• 순차적 메모리할당방식이다.
• 순차적 ,임의적으로 접근할 수 있는 선형 자료구조이며 접근방법은 직접접근 방법이다.
• <인덱스,원소> 쌍의 집합
• 원소들은 모두 같은 형(type) , 같은 크기를 갖는다.
• 표현이 간단하고 원소의 접근이 빠르지만 삽입/삭제의 효율이 떨어진다.

연결리스트

• 원소의 물리적 순서와 리스트의 논리적 순서가 같지 않은 비순차 표현이다.
• 원소를 저장할 때 이 원소의 다음원소에 대한 주소도 함께 저장해야 한다.
• 노드(<원소, 주소>쌍의 집합)의 저장구조를 갖는다.
• 각 노드는 자료필드와 다음노드의 주소 값을 가지는 링크필드로 구성되는 자료구조이다.
• 삽입/삭제시 원소 이동 발생이 없어 편리하다.

레코드

논리적으로 서로 연결되어있는 자료원소들의 집합체이며 각 필드마다 자료형과 크기가 다를 수 있다.

스택

• PUSH(삽입)/POP(삭제) 연산이 있으며 자료의 입력과 출력이 한쪽 끝에서만 이루어진다
• 후입선출 리스트이다.LIFO
• 1개의 인덱스인 TOP 포인터로 삽입과 삭제가 이루어지는 순서리스트이다.
• 응용분야로 시스템스텍, 서브루틴호출, 수식계산, 인터럽트처리, 컴파일러, 순환호출 등에 사용된다.

큐

• 한쪽 끝에서는 삭제, 다른 한쪽 끝에서는 삽입되는 1차원 배열의 선형리스트를 의미한다.
• 선입선출 리스트이다. FIFO
• 2개의 인덱스 front(삭제), rear(삽입)로 삽입/삭제가 이루어진다.
• 응용분야로 작업 스케줄링과 버퍼관리에 보편적으로 사용된다.

수식의 표기법 및 변환(중위 -> 후위, 전위)

(A+B)*B-C/(D-E) ->전위 : - *+ABB/C-DE
(A+B)*B-C/(D-E) ->후위 : AB+B*CDE-/-

단순 연결 리스트

• 자료를 저장하는 데이터필드와 다음 노드를 가리키는 포인터를 저장하는 링크필드로 구성된 노드(2개 필드)로 연결되어 있다.
• 다음 노드로의 이동은 쉽지만 삽입하거나 삭제할 때 선행노드를 알아야 하는 문제점이 있다.

이중연결 리스트

• 자료를 저장하는 데이터필드와 후속노드를 가리키는 포인터를 저장하는 RLIMK 필드, 선행노드를 가리키는 포인터를 저장하는 LLINK 필드로 구성된 노드 (3개 필드)로 연결되어 있다.
• 선행노드를 쉽게 찾을 수 있다.

이진트리

• 진출차수가 2 이하의 노드들이 끊김없이 연결되어 있으며 오른쪽 서브트리와 왼쪽 서브트리가 분명하게 구분된 트리
• 완전 이진트리 : 높이가 k인 이진트리에서 k-1레벨 까지는 포화 이진트리이고 k 레벨에서는 왼쪽부터 꽉차있는 이진트리

트리의 순회 방법

• 이진트리순회에서 L, D, R,이 각각 좌측으로 이동, 자료 인쇄, 우측으로 이동 이라는 3개의 작업을 나타낼 때 우측보다 좌측을 먼저 순회하는 방법으로는 가 있다 LDR, LRD, DLR
• 이 세 가지 순회를 각각 중위순회, 후위순회, 전위순회라하며 산술표기식 INFIX 표기, POSTFIX 표기, PREFIX 표기와 유사하다.
• 중위순회 (LDR): 좌측으로 이동, 자료의 인쇄, 우측으로 이동의 순서로 순회한다.
• 후위순회 (LRD): 좌측으로 이동, 우측으로 이동, 자료의 인쇄 순으로 순회한다.
• 전위순회 (DLR): 자료의 인쇄, 좌측으로 이동, 우측으로 이동의 순서로 순회한다.

3. 배열의 행우선과 열우선의 개념 및 주소 계산공식

1) 행우선

1. 2차원 배열을 먼저 행 별로 분할하여 이 행을 차례로 연결시켜

   하나의 가상적인 차원 배열로 만들어 사상하는 것이다. -> 열의 주소가 먼저 변함.

2.  2 차원 a[m, n]에서 a[0,0]의 주소가 k 라 할 때 임의의 원소 a[i, j]의

주소계산 공식은  k + i * n + j  가 된다.

즉 현재의 주소 + 임의원소 행의 값 *열의 총수 + 임의원소 열의 값이다.

2) 열우선

1. 2차원 배열을 먼저 열 별로 분할하여 이 열을 차례로 연결시켜

   하나의 가상적인 차원 배열로 만들어 사상하는 것이다 ->행의 주소가 먼저 변함.

2 주소계산 공식은  k + j * m + i 가 된다 .

즉 현재의 주소 + 임의원소 열의 값 * 행의 총수  +  임의원소 행의 값이다.

자료구조 출석수업 요점정리

알고리즘의 개념 및 특성

• 특정 문제를 해결하기 위해 기술한 일련의 논리적 순서
• 입출력 - 입츨력이 가능해야 한다.
• 명확성 - 명령은 명확해야한다.
• 유한성 - 한정된 단계 실행후 종료되어야 한다.
• 유효성 - 컴퓨터 처리가능해야 한다.

순환의 개념 및 예

• 분할정복의 특성을 가진 문제에 적합
• 분할정복 - 어떤 복잡한 문제를 직접 간단하게 풀수 있는 작은 문제로 분할하여 해결하려는 방법
• 직접순환 - A -> A`
• 간접순환 - A -> B -> A

배열

• 순차적 메모리할당방식이다.
• 순차적 ,임의적으로 접근할 수 있는 선형 자료구조이며 접근방법은 직접접근 방법이다.
• <인덱스,원소> 쌍의 집합
• 원소들은 모두 같은 형(type) , 같은 크기를 갖는다.
• 표현이 간단하고 원소의 접근이 빠르지만 삽입/삭제의 효율이 떨어진다.

연결리스트

• 원소의 물리적 순서와 리스트의 논리적 순서가 같지 않은 비순차 표현이다.
• 원소를 저장할 때 이 원소의 다음원소에 대한 주소도 함께 저장해야 한다.
• 노드(<원소, 주소>쌍의 집합)의 저장구조를 갖는다.
• 각 노드는 자료필드와 다음노드의 주소 값을 가지는 링크필드로 구성되는 자료구조이다.
• 삽입/삭제시 원소 이동 발생이 없어 편리하다.

레코드

논리적으로 서로 연결되어있는 자료원소들의 집합체이며 각 필드마다 자료형과 크기가 다를 수 있다.

스택

• PUSH(삽입)/POP(삭제) 연산이 있으며 자료의 입력과 출력이 한쪽 끝에서만 이루어진다
• 후입선출 리스트이다.LIFO
• 1개의 인덱스인 TOP 포인터로 삽입과 삭제가 이루어지는 순서리스트이다.
• 응용분야로 시스템스텍, 서브루틴호출, 수식계산, 인터럽트처리, 컴파일러, 순환호출 등에 사용된다.

큐

• 한쪽 끝에서는 삭제, 다른 한쪽 끝에서는 삽입되는 1차원 배열의 선형리스트를 의미한다.
• 선입선출 리스트이다. FIFO
• 2개의 인덱스 front(삭제), rear(삽입)로 삽입/삭제가 이루어진다.
• 응용분야로 작업 스케줄링과 버퍼관리에 보편적으로 사용된다.

수식의 표기법 및 변환(중위 -> 후위, 전위)

(A+B)*B-C/(D-E) ->전위 : - *+ABB/C-DE 
(A+B)*B-C/(D-E) ->후위 : AB+B*CDE-/-

단순 연결 리스트

• 자료를 저장하는 데이터필드와 다음 노드를 가리키는 포인터를 저장하는 링크필드로 구성된 노드(2개 필드)로 연결되어 있다.
• 다음 노드로의 이동은 쉽지만 삽입하거나 삭제할 때 선행노드를 알아야 하는 문제점이 있다.

이중연결 리스트

• 자료를 저장하는 데이터필드와 후속노드를 가리키는 포인터를 저장하는 RLIMK 필드, 선행노드를 가리키는 포인터를 저장하는 LLINK 필드로 구성된 노드 (3개 필드)로 연결되어 있다.
• 선행노드를 쉽게 찾을 수 있다.

이진트리

• 진출차수가 2 이하의 노드들이 끊김없이 연결되어 있으며 오른쪽 서브트리와 왼쪽 서브트리가 분명하게 구분된 트리
• 완전 이진트리 : 높이가 k인 이진트리에서 k-1레벨 까지는 포화 이진트리이고 k 레벨에서는 왼쪽부터 꽉차있는 이진트리

트리의 순회 방법

• 이진트리순회에서 L, D, R,이 각각 좌측으로 이동, 자료 인쇄, 우측으로 이동 이라는 3개의 작업을 나타낼 때 우측보다 좌측을 먼저 순회하는 방법으로는 가 있다 LDR, LRD, DLR
• 이 세 가지 순회를 각각 중위순회, 후위순회, 전위순회라하며 산술표기식 INFIX 표기, POSTFIX 표기, PREFIX 표기와 유사하다.
• 중위순회 (LDR): 좌측으로 이동, 자료의 인쇄, 우측으로 이동의 순서로 순회한다.
• 후위순회 (LRD): 좌측으로 이동, 우측으로 이동, 자료의 인쇄 순으로 순회한다.
• 전위순회 (DLR): 자료의 인쇄, 좌측으로 이동, 우측으로 이동의 순서로 순회한다.

3. 배열의 행우선과 열우선의 개념 및 주소 계산공식

1) 행우선

1. 2차원 배열을 먼저 행 별로 분할하여 이 행을 차례로 연결시켜

   하나의 가상적인 차원 배열로 만들어 사상하는 것이다. -> 열의 주소가 먼저 변함.

2.  2 차원 a[m, n]에서 a[0,0]의 주소가 k 라 할 때 임의의 원소 a[i, j]의

주소계산 공식은  k + i * n + j  가 된다.

즉 현재의 주소 + 임의원소 행의 값 *열의 총수 + 임의원소 열의 값이다.

2) 열우선

1. 2차원 배열을 먼저 열 별로 분할하여 이 열을 차례로 연결시켜

   하나의 가상적인 차원 배열로 만들어 사상하는 것이다 ->행의 주소가 먼저 변함.

2 주소계산 공식은  k + j * m + i 가 된다 .

즉 현재의 주소 + 임의원소 열의 값 * 행의 총수  +  임의원소 행의 값이다.