[자료구조] - 자료구조 소개

👋 본 글은 "C로 배우는 쉬운 자료구조" 책을 읽고 요약, 정리한 글입니다.

---

책 구매 링크에서 책을 확인하실 수 있습니다.

 

🎯 1. 자료구조의 이해

---

1 - 1. 자료구조의 개념

자료구조란? : 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것

배워야 하는 이유 : 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 함 (자료구조에 대한 개념과 활용 능력 필요)

 

1 - 2. 자료구조의 분류

표현할 자료의 특성과 주된 사용 방법, 수행하는 연산의 특성, 구현에 필요한 저장 공간 용량과 실행 소요 시간 등을 고려하여 가장 효율적인 자료구조를 선택해야 한다.

• 단순 구조
  • 정수, 실수, 문자, 문자열 등의 기본 자료형 (Data Type)
• 선형 구조
  • 자료들 사이의 관계가 1 : 1 관계
  • 순차 리스트, 연결 리스트, 스택, 큐, 데크 등
• 비선형 구조
  • 자료들 사이의 관계가 1 : 다, 또는 다 : 다 관계
  • 트리, 그래프 등
• 파일 구조
  • 서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조
  • 순차 파일, 색인 파일, 직접 파일 등

🎯 2. 자료의 표현

---

2 - 1. 컴퓨터에서의 자료 표현

컴퓨터에서의 자료 표현 : 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료를 2진수 코드로 표현하여 저장 및 처리

2진수 코드란?

• 1과 0, On과 Off, 참(True)과 거짓(False)의 조합
• 비트 -> 니블 (4비트) -> 바이트 (8비트) 

2 - 2. 수치 자료의 표현

10진수의 표현 1 : 존(ZONE) 형식 표현

 

존 영역 + 수치 영역 = 1바이트 (8비트)

존 영역에는 항상 1111을 표시하고, 수치 영역에는 4비트의 2진수 (0000 ~ 1001)로 10진수 0 ~ 9를 표현

10에서 15까지 (1010 ~ 1111)는 A ~ F로 표현하기도 함

4비트의 2진수 (0000 ~ 1111)로 10진수 0 ~ 15를 표현

 

부호는 최하위 바이트의 존 영역에 C(1100), D(1101)를 표시 (C는 +, D는 -를 나타냄)

예)

+213

1111(F)

0010(2)

1111(F)

0001(1)

1100(C(+))

0011(3)

-213

1111(F)

0010(2)

1111(F)

0001(1)

1101(D(-))

0011(3)

 

10진수의 표현 : 2 팩 형식 표현

존 형식은 최하위 바이트의 존 영역을 제외한 나머지 존 영역은 항상 "1111"을 저장해야 하니 공간이 낭비되고 처리가 지연됨

팩 형식에서는 1바이트에 10진수 2자리 (존 형식은 1바이트에 1111 + 10진수 1자리) 표현

부호는 최하위 바이트의 하위 4비트에 표시

예)

+213

0010(2)

0001(1)

0011(3)

1100(C(+))

-213

0010(2)

0001(1)

0011(3)

1100(D(-))

 

2진수의 정수 표현

• 2진수는 일정한 길이의 n비트로 표현
• 최상위 비트인 첫 번째 비트는 부호표시
• 나머지 비트는 2진수 값 표현
• 부호를 어떻게 표현하느냐에 따라 부호와 절댓값 형식, 1의 보수 형식, 2의 보수 형식으로 나뉨

2진수의 정수 표현 : 부호와 절댓값 형식

부호를 최상위 비트에 표시하고 나머지 비트에는 2진수의 절댓값 표시

예)

+21

0

0

0

1

0

1

0

1

-21

1

0

0

1

0

1

0

1

첫 비트 0(+), 1(-)는 부호, 0010101은 21의 절댓값을 나타냄

 

2진수의 정수 표현 : 1의 보수 형식

• 양수는 부호와 절댓값 형식과 같은 방법으로 표현
• 음수는 2진수를 1의 보수로 변환하여 표현

1의 보수란? 어떤 값 X의 절댓값을 n비트의 2진수로 변환한 뒤, 0을 1로, 1을 0으로 변환시켜 표현 ((2ⁿ - 1) - | X |)

예)

21, -21의 절댓값은 00010101이므로 21의 1의 보수는 11101010

따라서 +21은

0

0

0

1

0

1

0

1

-21은

1

1

1

0

1

0

1

0

 

2진수의 정수 표현 : 2의 보수 형식

• 양수는 부호와 절댓값 형식과 같은 방법으로 표현
• 음수는 2진수를 2의 보수로 변환하여 표현

2의 보수란? 어떤 값 X을 n비트의 2진수로 변환 (2ⁿ - | X |) (1의 보수 표현에 1을 더함)

예)

21의 1의 보수인 11101010에 2진수 1을 더함 -> 11101011

따라서 +21은

0

0

0

1

0

1

0

1

-21은

1

1

1

0

1

0

1

1

 

따라서 양수는 모두 부호와 절댓값 형식으로 표현하고 음수는 부호와 절댓값 형식, 1의 보수 형식, 2의 보수 형식을 사용함

부호와 절댓값 형식은 -127 ~ +127을 표현할 수 있는데, -0과 +0이 존재함

1의 보수 형식은 -127 ~ +127을 표현할 수 있는데, -0과 +이 존재함

2의 보수 형식은 -128 ~ +127을 표현할 수 있음 (-0 대신 -128 표현)

현재 컴퓨터 시스템에서는 2의 보수 형식 사용

 

2진수의 실수 표현

• 컴퓨터는 2진수만으로 실수를 표현해야하므로 소수점을 직접 표현하지 못하고 정수부와 실수부의 위치를 정의하여 실수를 표현

2진수의 실수 표현 : 고정소수점 표현 방식

소수점이 항상 최상위 비트의 왼쪽 밖, 최하위 비트의 오른쪽 밖에 고정되어 있다고 취급

따라서 소수점이 왼쪽 밖일 때는 00010101은 0.00010101을 의미,

소수점이 오른쪽 밖일 때는 00010101.0을 의미

결국 정수 표현과 같음

 

2진수의 실수 표현 : 부동소수점 표현 방식

과학적 표기 방식의 실수를 사용 (213 = 0.213 X 10³)

고정소수점 표현 방식에 비해 아주 작은 값이나 아주 큰 값을 표현할 수 있음

현재 컴퓨터에서는 부동소수점 표현 형식을 사용

부동소수점 표현 형식으로 실수를 표현하려면 부호, 지수, 가수의 세 영역을 사용

 

부동소수점의 표현 범위에 따라 4바이트(32비트)의 단정도, 8바이트(64비트의) 배정도로 나뉨

100010.101을 부동소수점으로 표현하려면 다음 단계를 따른다.

1. 정규화 : 정수부가 1이 되도록 소수점을 이동하여 과학적 표기로 변환 (1.00010101 X 2⁵)
2. 부호 : 양수는 0, 음수는 1을 부호 영역에 저장
3. 가수부 : 정규화하면 정수부는 항상 1이 되므로, 정수부를 생략하고 소수부(00010101)만 저장
4. 지수부 : 정규화해서 구한 지수와 바이어스를 더한 값을 저장

바이어스 : 지수의 부호를 표현하기 위해 사용하는 값으로, 단정도에서는 127, 배정도에서는 1023을 사용하여

단정도 (5 + 127 = 132 = 10000100), 배정도 (5 + 1023 = 1028 = 10000000100)을 저장

따라서 단정도에서는

0	10000100	00010101000000000000000
1비트(부호)	8비트(지수부)	23비트(가수부)

배정도에서는

0	10000000100	0001010100000000000000000000000000000000000000000000
1비트(부호)	11비트(지수부)	52비트(가수부)

 

2 - 3. 문자 자료의 표현

문자 자료의 표현 : BCD 코드

• 6비트를 사용하며, 상위 2비트의 존비트와 하위 4비트의 숫자 비트로 구성됨
• 0 ~ 9까지 10진수 숫자와 영어 대문자, 특수문자 표현 가능

문자 자료의 표현 : EBCDIC 코드

• 8비트를 사용하며, 상위 4비트의 존 비트와 하위 4비트의 숫자 비트로 구성됨
• 0 ~ 9까지의 10진수 숫자와 영어 대소문자, 특수문자 표현 가능

표에서 열은 존 비트, 행은 숫자 비트를 나타냄

문자 자료의 표현 : ASCII 코드

• 7비트를 사용하며, 상위 3비트의 존 비트와 하위 4비트의 숫자 비트로 수정됨
• 0 ~ 9까지의 10진수 숫자와 영어 대소문자, 특수문자 표현 가능
• ASCII 코드를 데이터 통신용으로 사용할 때는 최상위 비트에 패리티 비트를 추가하여 8비트 형식으로 사용
• C 프로그램에서 문자 코드로 사용

표에서 열은 존 비트, 행은 숫자 비트를 나타냄

문자 자료의 표현 : 유니코드

• EBCDIC 코드나 ASCII 코드는 영어만 표현할 수 있으므로 세계 여러 나라의 언어를 통일된 방법으로 표현하기 위해 유니코드 탄생
• 유니코드는 2바이트를 조합하여 한 글자를 표현
• 표는 https://www.unicode.org/에서 확인할 수 있음
• XML, Java, CORBA 3.0, WNL 등 인터넷 기반 프로그램과 제품에 사용

2 - 4. 논리 자료의 표현

논리값(True, False)을 표현하기 위한 자료 형식

일반적으로 컴퓨터 내부에서 1바이트 (8비트), 1워드 (16, 32, 64 (CPU에 따라 다름))를 논리값의 단위로 사용

표현 방법으로는 다음 세 가지가 있다

• 참 : 00000001, 거짓 : 00000000
• 참 : 11111111, 거짓 : 00000000
• 참 : 하나 이상의 비트를 1로 표시, 거짓 : 00000000

2 - 5. 포인터 자료의 표현

• 메모리 주소를 표현하기 위한 자료 형식
• 변수나 특정 위치의 메모리 주소를 저장

 

2 - 6. 문자열 자료의 표현

• 한 글자만 표현할 수 있는 문자 자료와 달리 여러 글자로 이루어진 문자 그룹을 하나의 자료로 취급
• 메모리에 글자를 연속적으로 저장
• 문자열 하나는 부분 문자열을 여러 개 포함할 수 있음

부분 문자열을 포함하는 문자열 자료를 메모리에 저장하는 방법에는 다음 세 가지가 있음

	메모리 이용률	부분 문자열 탐색 시간
부분 문자열 사이에 구분자를 사용	문자열 길이 + 구분자 길이 ➡️ 효율적	문자 비교 연산 시간 + 구분자 식별 시간 ➡️ 비효율적
가장 긴 문자열의 길이에 맞춰 고정 길이로 저장	가장 긴 부분 문자열 길이 X 부분 문자열의 개수 ➡️ 비효율적	문자 비교 연산 시간 ➡️ 효율적
부분 문자열을 연속하여 저장하고 각 부분 문자열에 대한 포인터 사용	문자열 길이 + 포인터 저장 공간 ➡️ 효율적	문자 비교 연산 시간 + 포인터 주소 연산 시간 ➡️ 효율적

 

🎯 3. 자료의 추상화

---

추상화 작업 : 자세하고 복잡한 것 대신 필수적으로 중요한 특징만 골라서 단순화시키는 작업

컴퓨터를 이용한 문제해결에서의 추상화 : 크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법

 

자료 추상화 : 처리할 자료, 연산, 자료형에 대한 추상화 표현

자료 추상화에 이용하는 기본 개념 아래 세 가지와 같다

• 자료 : 프로그램의 처리 대상이 되는 모든 것
• 연산 : 어떤 일을 처리하는 과정으로 연산자를 이용하여 수행됨
• 자료형 : 처리할 자료의 집합과 자료에 대해 수행할 수 있는 연산자의 집합
  • 예 ) 정수 자료형
    자료 : 정수의 집합{..., -1, 0, 1, ...}
    연산자 : 정수에 대한 연산자 집합{+, -, x, /, mod}

추상 자료형 : 자료형에 대한 자료의 특선, 연산자, 연산자가 무엇을 수행하는지 등을 논리적으로 정의한 자료형

추상 자료형은 구체적인 구현을 포함하지 않기 때문에 알고리즘 개발이 단순해지고 원하는 프로그래밍 언어를 사용하여 프로그램으로 구체화하여 실행

 

추상화 : 무엇인가?(What)를 논리적으로 정의

구체화 : 어떻게 할 것인가?(How)를 실제적으로 표현

 

	자료	연산
추상화	추상 자료형	알고리즘 정의
구체화	자료형	프로그램 구현

 

🎯 4. 알고리즘의 이해

---

알고리즘 : 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

 

알고리즘의 조건

• 입력 : 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다
• 출력 : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다
• 명확성 : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다
• 유한성 : 알고리즘은 수행 뒤에 반드시 종료되어야 한다
• 효과성 : 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다

🎯 5. 알고리즘의 표현 방법

---

5 - 1. 알고리즘 표현 방법의 종류

• 자연어를 이용한 서술적 표현 방법
  • 사람이 쓰는 언어로 표현
  • 서술적이며, 일관성이나 명확성을 유지하기 어려움
  • 알고리즘을 표현하는 데 한계
• 순서도를 이용한 도식화 표현 방법
  • 순서도를 작성하는 규칙에 따라 도식화
  • 복잡한 알고리즘을 표현하는 데 한계
• 프로그래밍 언어를 이용한 구체화 방법
  • 알고리즘 자체가 구체화되므로 구체화 작업을 할 필요가 없음
  • 특정 프로그래밍 언어로 작성하기 때문에 특정 언어를 모르면 이해하기 어려움
  • 프로그래밍 언어로 변환해야 하므로 비효율적
• 가상코드를 이용한 추상화 방법
  • 특정 프로그래밍 언어는 아니지만 프로그래밍 언어의 형태를 갖춘 가상코드를 사용
  • 직접 실행할 수는 없지만 일반적인 프로그래밍 언어와 유사하기 때문에 특정 프로그래밍 언어로 변환이 쉬움

 

5 - 2. 순서도를 이용한 도식화

특정 기호를 사용하여 알고리즘의 실행 단계를 표현

 

5 - 3. 가상코드를 이용한 추상화

기본 요소

• 기호 : 문자나 숫자를 조합한 것으로 첫 글자는 반드시 영문자 (변수, 자료형, 프로그램의 이름 등)
• 자료형 : 정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형을 사용할 수 있음
• 연산자 : 산술 연산자, 관계 연산자, 논리 연산자

 

아래 그림들은 가상 코드와 순서도의 예시

지정문

조건문

다단계조건문

case문

for문

while문

do while문

함수문

 

🎯 6. 알고리즘의 성능 분석

---

6 - 1. 알고리즘 성능 분석 기준

• 정확성 : 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
• 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가
• 수행량 : 일반적인 연산 제외, 알고리즘 특성 나타내는 중요 연산 모두 분석
• 메모리 사용량
• 최적성 : 알고리즘이 얼마만큼 효율적으로 수행되느냐

 

6 - 2. 알고리즘 성능 분석 방법

• 공간 복잡도
  • 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양
  • 공간 복잡도 = 고정 공간 + 가변 공간
• 시간 복잡도
  • 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간
  • 시간 복잡도 = 컴파일 시간 + 실행시간
    • 컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요
    • 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간보다는 명령문의 실행 빈도수에 따라 계산
  • 실행 빈도수의 계산
    • 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차의 거의 없으므로 하나의 단위시간을 갖는 기본 명령문으로 취급

 

시간 복잡도 예) 피보나치수열 알고리즘 빈도수

 

6 - 3. 알고리즘 성능 분석 표기법

n의 증가에 따라 증가율이 가장 큰 하나의 항에 대해서 차수 표기법으로 시간 복잡도를 표기

표기법에는 다음 세 가지가 있음

• 빅 - 오 표기법 : 시간의 상한 값 (최악의 성능일 때 걸리는 시간) (~시간 안에는 완료됨)
• 빅 - 오메가 표기법 : 시간의 하한 값 (최고의 성능일 때 걸리는 시간) (~시간이 걸림)
• 빅 - 세타 표기법 : 상한과 하한이 같은 정확한 차수를 표현하기 위한 표기법 (~시간)

보통 빅 O 표기법을 씀

알고리즘이 최악일 때 어떤 성능을 지녔는지 판단해야 사용유무를 판단할 수 있기 때문

 

빅 - 오 표기법

• O(f(n))과 같이 표기, "Big oh of f(n)"으로 읽음
• 함수의 상한을 나타내기 위한 표기법 (최악의 경우, 계산 결과 수행 시간 안에는 알고리즘 수행 완료 보장)
• 먼저 실행 빈도수를 구하여 실행 시간 함수를 찾고, 이 함숫값에 가장 큰 영향을 주는 n에 대한 항을 한 개 선택하여 계수는 생략하고 O의 오른쪽 괄호 안에 표시
• 대표적인 시간 복잡도
  • O(1)
  • O(log n)
  • O(n)
  • O(n²)
  • O(2ⁿ)

실행 시간 함수에서 n값의 변화에 따른 실행 빈도수 비교

시간 복잡도에 따른 알고리즘 수행 시간 비교 예