자료구조 1-7주차

본문 바로가기

Tags more

Archives

Today

Total

250x250

관리 메뉴

Archive

자료구조 1-7주차 본문

데이터분석/CS 기초

자료구조 1-7주차

neonii 2025. 2. 21. 09:54

728x90

자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것
이론적으로 이해하고 효율성을 평가하며 실제 문제 해결에 적용할 수 있어야 함

자료의 단위

컴퓨터는 자료를 표현하기 위해 0과 1의 조합으로 구성되는 2진수 코드를 사용함
(i.e. 비트 단위로 저장됨)
- 비트 bit는 디지털 시스템에서 자료를 표현하는 최소 단위
  4bit = 1nibble, 8bit = 1byte

자료구조 형태에 따른 분류

단순 구조
- 기본 형태
- e.g. 정수, 실수, 문자, 문자열
선형 구조
- 자료들 사이의 관계가 1:1
- e.g. 순차 리스트: 데이터가 연속된 공간에 저장되어, 순서대로 배치된 리스트
  연결 리스트: 데이터가 여러 위치에 흩어져 있지만 포인터를 통해 순서를 연결해두는 구조
  스택, 큐, 데크 리스트: 어떤 순서로 넣고 빼야 하는 규칙이 있는 리스트
비선형 구조
- 자료들 사이의 관계가 1:다 또는 다:다
- e.g. 계층 구조나 망 구조를 갖는 트리, 그래프
파일 구조
- 보조 기억 장치에 실제로 저장되는 형태
- e.g. 순차 파일, 색인 파일, 직접 파일

추상화

자료 추상화 data abstraction: 데이터의 복잡한 내부 구현을 숨기고, 중요한 부분만 사용자에게 보여주는 것

자료형 data type	구체적	데이터가 메모리에 어떻게 저장되고 처리되는지까지 정의되어 있음	프로그램 구현	e.g. int: 4바이트 크기의 정수를 저장하며, 덧셈/뺄셈과 같은 연산이 가능함
추상 자료형 abstract data type	추상적	동작 방식만 강조함	알고리즘 정의	e.g. stack: 데이터를 추가하거나 제거할 수 있음

단순 구조

수치 자료

short 2byte, int 4byte, long 4byte
자료형에 대한 메모리 할당 크기는 컴퓨터 CPU 성능에 따라 다를 수 있으므로, sizeof()를 통해 확인하는 것도 방법
10진수
- 존 zone 형식
- 팩 pack 형식: 존 형식에서 부호를 표시하는 존 영역을 제외한 나머지 존 영역이 항상 1111을 저장하면서 기억 공간을 낭비한다는 문제를 보완
2진수
- 정수
  - 부호 절댓값
    - 최상위 1bit를 부호 표시하는 데에 사용
    - 0을 00000000, 10000000 두 가지로 표현할 수 있게 되면서 논리적으로 일관성 없다는 단점 있음
  - 1의 보수 1' complement
    - 0을 00000000, 11111111 두 가지로 표현할 수 있게 되면서 논리적으로 일관성 없다는 단점 있음
  - 2의 보수 2' complement
- 실수
  - 고정 소수점: 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어 있는 것으로 취급
    (e.g. 00010101은 곧 0.00010101)
  - 부동 소수점: 과학적 표기 방식 활용
    - 고정 소수점 형식보다 표현 가능한 값의 범위가 넓음
    - 정규화: 정수부가 1이 되도록 소수점 이동
      부호: 양수는 0, 음수는 1
      가수부: 정수부는 항상 1이므로 소수부만 저장
      지수부: 정규화에서 구한 지수와 바이어스를 더한 값을 저장

문자 자료

char 1byte
binary coded decimal BCD 코드
extended binary coded decimal interchange EBCDIC 코드
american standard code for information interchange ASCII 코드
유니코드: 전세계 언어를 통일된 방법으로 표현할 수 있도록 정의한 국제 표준코드 ISO/IEC 10646 활용, 2바이트를 조합하여 하나의 글자 표현

논리 자료

1bit로 표현할 수도 있지만, 컴퓨터가 처리할 수 있는 최소 단위는 byte이기 때문에, 일반적으로 1byte나 1word로 표현
- 참: 00000001 / 거짓: 00000000
- 참: 11111111 / 거짓: 00000000
- 참: 하나 이상의 비트를 1로 표시 / 거짓: 0000000

포인터 자료

자료형에 상관없이 2byte 사용

문자열 자료

포인터

포인터 관련 연산자
- 주소 연산자 &: 변수 앞에 주소 연산자를 사용하면 그 변수의 주소에 접근 가능
- 참조 연산자 *: 포인터 앞에 참조 연산자를 사용하면 참조하고 있는 주소에 저장된 값에 접근 가능
포인터 변수: 메모리의 주소 값을 저장하는 특별한 변수
- 자료형에 따라 메모리 접근 범위가 달라지기 때문에 변수와 포인터는 같은 자료형으로 선언되어야 함

포인터 초기화

// 주소 연산자를 이용
int i;
int *ptr = &i;

// 동적 메모리를 할당하고 그 시작 주소를 포인터 값으로 지정
// 100byte 크기의 메모리를 빌려와 char로 쓰겠다고 선언하고 그 시작주소를 ptr에 저장하는 것
char *ptr = (char *) malloc(100);

// 문자열을 이용
char *ptr = "Korea";

// 배열 이름을 이용
// 문자열 자료형 및 배열 자료형은 일반 자료형과 다르게 지정 만으로 그 시작 주소를 전달할 수 있음
char A[100];
char *ptr = A;

// 배열의 첫 번째 요소의 주소를 이용
char A[100];
char *ptr = &A[0];

이중 포인터: 포인터를 가리키고 있는 포인터

char *ptrArray[2];
char **ptrptr;

ptrArray[0] = "Korea";
ptrArray[1] = "Seoul";
ptrptr = ptrArray;

선형 구조

순차 자료구조

메모리 저장 방식: 필요한 전체 메모리 크기를 계산하여 할당하고, 할당된 메모리의 시작 위치부터 빈자리 없이 저장
연산 특징: 삽입, 삭제 연산 후에도 빈자리 없이 자료가 순서대로 연속 저장되어, 변경된 논리적인 순서와 저장된 물리적인 순서가 일치함
프로그램 기법: 배열을 이용해 구현
- 배열: 같은 자료형을 가진 자료들을 나열하고 메모리에 연속으로 저장하여 만든 자료
  - 모든 자료형은 배열로 구성 가능
  - 배열 선언 형식 int A[3];
  - 배열 초기화 형식 int A[3] = {1, 2, 3};
    - 배열 크기보다 초깃값을 적게 지정하면, 나머지는 기본값 0이 할당됨
    - 배열 크기보다 초깃값을 많이 지정하면, 배열 영역 밖의 값들은 무시함
  - 다차원 배열: 실제로 메모리에 저장될 때는 1차원 구조로 저장됨
    - 2차원 배열
      - 행 우선 순서 방법 row major order
        A[i][j]의 원소 위치는 (2차원 배열의 시작주소) + (i × 열의 개수 + j) × (원소의 길이)
      - 열 우선 순서 방법 column major order
        A[i][j]의 원소 위치는 (2차원 배열의 시작주소) + (j × 행의 개수 + i) × (원소의 길이)
    - 3차원 배열
      - 면 우선 순서 방법
        A[i][j][k]의 원소 위치는
        (3차원 배열의 시작주소) + {(i × 행의 개수 × 열의 개수) + (j × 열의 개수) + k} × (원소의 길이)
      - 열 우선 순서 방법
        A[i][j][k]의 원소 위치는
        (3차원 배열의 시작주소) + {(k × 행의 개수 × 면의 개수) + (j × 면의 개수) + i} × (원소의 길이)
    - 행렬
      - 정방 행렬: m×n 행렬 중에서 m과 n이 같은 행렬
      - 전치 행렬: 행렬의 행과 열을 서로 바꿔 구성한 행렬
      - 희소 행렬 sparse matrix: 많은 원소가 0으로 구성된 행렬
        
        기억 공간을 좀 더 효율적으로 사용하려면 0이 아닌 값만 따로 배열로 구성하는 방법을 사용할 수 있음: 0이 아닌 원소만 추출해 <행 번호, 열 번호, 원소> 쌍으로 배열에 저장
  - 문자 배열
    - 더보기
      
      // 문자열은 문자열의 끝을 나타내는 \0(null)이 마지막에 추가되기 때문에, // 문자열을 저장할 메모리 크기는 실제 문자열 크기보다 1byte 커야 함 char s1[10] = "String"; char s2[10] = {'S', 't', 'r', 'i', 'n', 'g'}; char c[3][20] = {"Hong Gil Dong", "Computer Department", "Seoul Korea"}; strcpy(c[0], "Kim Chul Su"); // 문자열 배열은 바로 대입 불가능
- 원소 삽입: 물리적으로 삽입할 자리를 만든 후에 원소 삽입
  이때 원소 이동 횟수는 (배열의 길이) - (새 원소를 삽입하려는 위치의 인덱스)
- 원소 삭제: 삭제 후 그 이후의 원소들을 한 자리씩 앞으로 이동시킴
  이때 원소 이동 횟수는 (배열의 길이) - (삭제한 원소의 인덱스 + 1)
- 장점: 원소를 위치로 찾아 접근하기 쉬움
- 단점:
  삽입 연산이나 삭제 연산 후에 원소들을 이동시키는 추가 작업과 시간이 소요됨
  배열을 이용해 구현하기 때문에 메모리 할당을 연속적으로 잡아야한다는 메모리 사용의 비효율성 문제가 존재함

(비순차) 연결 자료구조

메모리 저장 방식: 노드 단위로 메모리가 할당되며, 저장 위치의 순서와 상관없이 링크 필드에 다음 자료의 주소를 저장함

노드 node <원소, 주소> 는 구조체로 정의

typedef struct Node {
	char data[4]; // 값을 저장할 데이터 필드
    struct Node *link; // 포인터 변수를 사용해 주소를 저장할 링크 필드, 노드와 같은 구조체 타입
} ListNode; // 별명을 붙임

연산 특징: 삽입, 삭제 연산 후 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적 위치는 변경되지 않음

프로그램 기법: 포인터를 이용한 구현

단순 연결 리스트 singly linked list

삽입

// 첫 번째 노드로 삽입
insertFirstNode(L, x) {
	new = getNode(); // 삽입할 노드 준비
    new.data = x; // 새 노드의 데이터 필드값 저장
    new.link = L; // 새 노드의 링크 필드값 저장
    L = new; // 리스트의 앞 노드에 새 노드 연결
}

// 중간 노드로 삽입
insertMiddleNode(L, pre, x) {
	new = getNode();
    new.data = x;
    if (L == NULL) {
    	L = new;
        new.link = NULL;
    } // 공백 리스트인 경우
    else {
    	new.link = pre.link; // 새 노드의 링크 필드값 저장
        pre.link = new; // 리스트의 앞 노드에 새 노드 연결
   	}
}

// 마지막 노드로 삽입
insertLastNode(L, x) {
	new = getNode();
    new.data = x;
    new.link = NULL; // 새 노드의 링크 필드값 저장
    if (L == NULL) {
    	L = new;
        return;
    }
    temp = L;
    while (temp.link != NULL) {
    	temp = temp.link;
    }
    temp.link = new;
}

삭제

deleteNode(L, pre) {
	if (L == NULL) error; // 공백 리스트인 경우
    else {
    	old = pre.link; // 포인터 old가 삭제할 노드를 가리키도록
        if (old == NULL) return; // 만약 pre가 마지막 노드였다면 삭제할 노드가 없다는 의미이므로, 삭제 연산 수행하지 않고 반환
        pre.link = old.link;
        returnNode(old);
    }
}

탐색

searchNode(L, x) {
	temp = L; // temp의 시작 위치 지정
    while (temp != NULL) {
    	if (temp.data == x) return temp;
        else temp = temp.link;
    }
    return temp; // 탐색 실패했을 경우 NULL 반환
}

역순으로 변경

typedef struct ListNode {
	char data[4];
    struct ListNode *link;
} listNode;

typedef struct {
	listNode *head;
} linkedList_h;

void reverse(linkedList_h *L) {
	listNode *p; listNode *q; listNode *r;
    p = L; // 포인터 p를 첫 번째 노드에 설정
    q = NULL; r = NULL;
    while (p != NULL) {
    	r = q; // 포인터 r을 포인터 q가 가리키는 현재 노드에 연결
        q = p; // 포인터 q를 포인터 p가 가리키는 현재 노드에 연결
        p = p.link; // 포인터 p는 링크를 따라 다음 노드로 이동
        q.link = r;
    }
    L = q;
}

원형 연결 리스트: 단순 연결 리스트의 마지막 노드를 링크 필드에 첫 번째 노드의 주소를 저장하여 구성

삽입

// 첫 번째 노드로 삽입
insertFirstNode(CL, x) {
	new = getNode();
    new.data = x;
    if (CL == NULL) {
    	CL = new;
        new.link = new; // new가 자기자신을 가리키게 함으로써 첫 번째 노드이자 마지막 노드가 되도록
    } else {
    	temp = CL;
        while (temp.link != CL) {
        	temp = temp.link;
        } // 마지막 노드까지 이동
        new.link = temp.link;
        temp.link = new;
        CL = new;
    }
}

// 중간 노드로 삽입
insertMiddleNode(CL, pre, x) {
	new = getNode();
    new.data = x;
    if (CL == NULL) {
    	CL = new;
        new.link = new;
    } else {
    	new.link = pre.link
        pre.link = new;
    }
}

삭제

deleteNode(CL, pre) {
	if (CL == NULL) error;
    else {
    	old = pre.link;
        pre.link = old.link;
        if (old == CL) CL = old.link;
        return Node(old);
    }
}

이중 연결 리스트: 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

노드 구조

typedef struct Dnode {
	struct Dnode *llink;
	char data[5];
	struct Dnode *rlink;
}

삽입

insertNode(DL, pre, x) {
	new = getNode();
	new.data = x;
	new.rlink = pre.rlink;
	pre.rlink = new;
	new.llink = pre;
	new.rlink.llink = new;
}

삭제

deleteNode(DL, old) {
	old.llink.rlink = old.rlink;
	old.rlink.llink = old.llink;
	returnNode(old);
}

이중 원형 연결 리스트: 이중 연결 리스트를 원형으로 구성

장점:
물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
크기 변경이 유연하고 더 효율적으로 메모리를 사용할 수 있음

스택 stack

후입선출 구조, Last-In-First-Out LIFO
순차 자료구조(1차원 배열)를 이용해 구현
- 인덱스 0번: 스택의 첫 번째 원소 ~ 인덱스 n-1번: 스택의 n번째 원소
- 공백 상태: top = -1
  포화 상태: top = n-1
- 장점: 쉽게 구현 가능
- 단점: 스택의 크기 변경 어려운 등 순차 자료 구조의 단점을 그대로 가짐

연결 자료구조(단순 연결 리스트)를 이용해 구현

공백 상태: top = null

typedef int element; // 별명 추가

typedef struct stackNode {
	element data;
	struct stackNode *link;
} stackNode; // 노드 정의

stackNode *top; // 포인터 top 선언

int isEmpty() {
	if (top == NULL) return 1;
	else return 0;
} // 스택이 공백 상태인지 확인하는 연산

void push(element item) {
	stackNode *temp = (stackNode *)malloc(sizeof(stackNode)); // 공백 스택 생성
	temp.data = item;
	temp.link = top; // 삽입 노드를 top 위에 연결
	top = temp; // top 위치를 삽입 노드로 이동
}

element pop() {
	element item;
	stackNode *temp = top;
	if (top == NULL) return 0; // 스택이 공백 리스트인 경우
	else {
		item = temp.data;
		top = temp.link; // top 위치를 삭제 노드 아래로 이동
		free(temp); // 삭제된 노드의 메모리 반환
		return item; // 삭제된 원소 반환
	}
}

void printStack() {
	stackNode *p = top;
	while (p) {
		printf("%d", p.data); // 스택 원소 출력
		p = p.link; // 링크 필드 따라 아래 노드로 이동
	}
}

응용1. 역순 문자열 만들기
응용2. 프로그램 호출: 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 구조

응용3. 괄호 검사

testPair() {
	while (true) {
		symbol = getSymbol(exp);
		case {
			symbol == "(" | "[" | "{":
				push(Stack, symbol);
			symbol == ")":
				open_pair = pop(Stack);
				if (open_pair != "(") return false;
			symbol == "]":
				open_pair = pop(Stack);
				if (open_pair != "[") return false;
			symbol == "}":
				open_pair = pop(Stack);
				if (open_pair != "{") return false;
			symbol == NULL:
				if (isEmpty(Stack)) return true;
				else return false;
			else:
		}
	}
}

응용4. 후위 표기

수식의 표기법
- 전위 표기법 prefix notation: 연산자를 피연산자 앞에 표기하는 방법
- 중위 표기법 infix notation: 연산자를 피연산자 가운데에 표기하는 방법
- 후위 표기법 postfix notation: 연산자를 피연산자 뒤에 표기하는 방법

중위 표기식의 후위 표기식 변환 방법

infix_to_postfix(exp) {
	while (true) {
		symbol = getSymbol(exp);
		case {
			symbol == operand: // 피연산자 처리: 출력
				print(symbol);
			symbol == operator: // 연산자 처리: 스택에 push
				push(stack, symbol);
			symbol == ")": // 오른쪽 괄호 처리: 스택을 pop하여 출력
				print(pop(stack)); 
			symbol == NULL: // 수식의 끝 처리
				while (top > -1) print(pop(stack));
			else:
		}
	}
}

후위 표기식 계산하는 방법

evalPostfix(exp) {
	while (true) {
		symbol = getSymbol(exp);
		case {
			symbol == operand: // 피연산자 처리
				push(Stack, symbol);
			symbol == operator: // 연산자 처리
				opr2 = pop(Stack);
				opr1 = pop(Stack);
				// 스택에서 꺼낸 피연산자들을 연산자로 연산
				result = opr1 op(symbol) opr2;
				push(Stack, result);
			symbol == NULL:
				print(pop(Stack));
		}
	}
}

단순 연결 리스트를 이용한 다항식 표현

노드 구조

typedef struct Node {
	float coef;
	int expo;
	struct Node *link;
}

삽입

appendTerm(PL, coef, expo, last) {
	new = getNode(); // 삽입할 노드 준비
	new.expo = expo; // 새 노드의 데이터 필드값 저장
	new.coef = coef; 
	new.link = NULL; 
	if (PL == NULL) {
		PL = new;
		last = new;
	} // 공백 리스트인 경우
	else {
		last.link = new;
		last = new;
	}
}

다항식끼리 덧셈 연산

// 단순 연결 리스트로 표현된 다항식 A와 B를 더해 새로운 다항식 C를 반환
addPoly(A, B) {
	p = A; q = B;
	C = NULL;
	r = NULL;
	while (p != NULL && q != NULL) {
		case {
			p.expo == q.expo:
				sum = p.coef + q.coef;
				if (sum != 0) appendTerm(C, sum, p.expo, r);
				p = p.link;
				q = q.link;
			p.expo < q.expo:
				appendTerm(C, q.coef, q.expo, r);
				q = q.link;
			else:
				appendTerm(C, p.coef, p.expo, r);
				p = p.link;
		}
	}
	while (p != NULL) {
		appendTerm(C, p.coef, p.expo, r);
		p = p.link;
	}
	while (q != NULL) {
		appendTerm(C, q.coef, q.expo, r);
		q = q.link;
	}
	return C;
}

728x90

'데이터분석 > CS 기초' 카테고리의 다른 글

컴퓨터구조 9-14주차 (0)	2025.10.18
컴퓨터구조 1-7주차 (2)	2025.08.29
이산수학 1-7주차 (2)	2025.08.29
알고리즘 1-7주차 (1)	2025.02.21
C언어(1) 1-7주차 (1)	2024.12.27

'데이터분석/CS 기초' Related Articles

more

티스토리툴바