자료구조의 이해

1. 자료구조란 무엇인가?

자료구조는 컴퓨터 프로그램을 통해 문제를 해결하는 과정에서 정보를 효율적으로 표현하고 구성 및 활용하는 기법을 학습하는 교과목입니다. 이는 자료를 효율적으로 표현하고 저장하며 처리할 수 있도록 정리하는 것을 의미합니다.

• 핵심 목적: 컴퓨터 프로그램의 성능은 효율적인 자료구조와 이에 따른 알고리즘으로 구성되므로, 컴퓨터 프로그래머 및 개발자로 성장하기 위한 중요한 교과목입니다
• 학습 내용: 리스트, 스택, 큐, 트리, 그래프 등 다양한 자료구조를 이해하고, 이와 관련된 선택, 탐색 및 정렬 문제와 그 효율성 및 해석 기법을 공부합니다

2. 과목의 주요 특징 및 수업 내용

자료구조와 알고리즘을 함께 학습하며, 이론과 실습을 병행하여 문제 해결 능력을 향상시키는 데 중점을 둡니다.

• 이론 및 실습 병행: 자주 사용하는 자료구조의 핵심 알고리즘으로 설계한 후 이를 C 프로그램으로 구현하면서 이론과 실습을 병행함
• 문제 해결 능력 향상: 자료구조를 활용한 문제 해결 능력 향상을 위한 수업 방식을 채택합니다
• 실습 환경: Visual Studio 2019 Community 버전을 사용합니다

주요 학습 주제

• 자료구조와 알고리즘 이해를 위한 기본 지식 및 C 프로그래밍 기법

• 순차 자료구조: 자료의 논리적 순서와 물리적 저장 순서가 일치하는 표현 방법을 학습합니다

  • 예: 배열을 이용한 리스트, 스택, 큐, 데크, 트리, 그래프 구현

• 연결 자료구조: 물리적 순서를 고려하지 않고 논리적 순서대로 연결하여 자료를 구성하는 표현 방법을 알아봅니다

  • 예: 포인터를 이용한 리스트, 스택, 큐, 데크, 트리, 그래프 구현

• 다양한 자료구조: 스택, 큐 (선형), 트리 (1:n 계층형), 그래프 (m:n 관계)의 특징과 연산 방법을 학습합니다

• 자료 응용: 정렬 및 검색 알고리즘을 살펴보고 구현합니다

  • 정렬: 선택, 버블, 퀵, 삽입, 셸, 병합, 기수, 힙, 트리 정렬
  • 검색: 순차, 이진, 이진 트리 검색, 해싱

3. 자료의 표현 방식

컴퓨터 내부에서 자료를 표현하는 다양한 방법을 학습합니다. 모든 형식의 자료는 2진수 코드로 표현되어 저장 및 처리됩니다.

• 2진수 코드의 단위: 1비트, 1니블 (4비트), 1바이트 (8비트)
• n비트 표현: n개의 비트로 $2^n$개의 상태를 표현할 수 있습니다

3.1. 수치 자료의 표현

10진수 표현

• 존(zone) 형식: 10진수 한 자리를 1바이트(8비트)로 표현하며, 상위 4비트는 존 영역(1111)으로, 하위 4비트는 수치 영역으로 사용합니다. 마지막 자리의 존 영역에 부호(양수: 1100, 음수: 1101)를 표시합니다
• 팩(pack) 형식: 10진수 한 자리를 4비트로 표현하며, 최하위 4비트에 부호(양수: 1100, 음수: 1101)를 표시합니다

2진수 정수 표현

• 부호 절댓값 형식: 최상위 1비트는 부호(0: 양수, 1: 음수)를, 나머지 n-1비트는 절댓값을 표시합니다
• 1의 보수(1' complement) 형식: 음수를 표현할 때 부호 비트 대신 1의 보수를 사용합니다. 양수 표현은 부호 절댓값과 같으며, 음수의 첫 비트는 1이 됩니다. (A-B) 뺄셈을 (A+(B의 1의 보수))로 변환하여 계산할 수 있습니다
• 2의 보수(2' complement) 형식: 음수를 표현할 때 2의 보수를 사용합니다. 컴퓨터 시스템에서 실제로 사용하는 형식입니다. (A-B) 뺄셈을 (A+(B의 2의 보수))로 변환하여 계산할 수 있으며, 덧셈 연산에서 오버플로 처리가 1의 보수 형식보다 간단합니다

2진수 실수 표현

• 고정 소수점 표현: 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어 있는 것으로 취급합니다
• 부동 소수점 표현: 고정 소수점 형식에 비해 표현 가능한 값의 범위가 넓으며, 실수를 소수부, 지수, 밑수로 구분하여 표현합니다

3.2. 문자 자료의 표현

문자에 대한 이진수 코드를 정의하여 사용합니다.

• BCD 코드: 6비트를 사용하여 문자를 표현합니다. 상위 2비트는 존 비트, 하위 4비트는 2진수 비트로 구성됩니다
• EBCDIC 코드: 8비트를 사용하여 문자를 표현합니다. 상위 4비트는 존 비트, 하위 4비트는 2진수 비트로 구성됩니다
• ASCII 코드: 7비트를 사용하여 문자를 표현합니다. 상위 3비트는 존 비트, 하위 4비트는 2진수 비트로 구성됩니다
• 유니코드: 세계 여러 나라의 언어를 통일된 방법으로 표현할 수 있도록 정의한 국제 표준 코드(ISO/IEC 10646)입니다. 2바이트를 조합하여 하나의 글자를 표현함으로써 다양한 언어를 지원하며, 현재 인터넷 기반 프로그램과 제품에 일반화되어 사용됩니다

3.3. 논리 자료의 표현

논리값(참/거짓, 1/0)을 표현하기 위한 자료 형식입니다. 1바이트를 사용하여 표현하며, 참은 최하위 비트 1 또는 전체 비트 1, 거짓은 전체 비트 0 등으로 정의할 수 있습니다.

3.4. 포인터 자료의 표현

메모리의 주소를 표현하기 위한 자료 형식입니다. 변수의 주소나 메모리의 특정 위치에 대한 주소를 저장하고 주소 연산에 사용됩니다.

3.5. 문자열 자료의 표현

여러 문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식입니다. 부분 문자열을 표현하는 방법에는 세 가지가 있습니다.

1. 구분자를 사용하는 방법: 부분 문자열 사이에 구분자를 사용하며, 메모리 이용률은 효율적이나 탐색 시간은 비효율적입니다
2. 고정 길이를 사용하는 방법: 가장 긴 문자열 길이에 맞춰 고정 길이로 저장하며, 메모리 이용률은 비효율적이나 탐색 시간은 효율적입니다
3. 포인터를 사용하는 방법: 부분 문자열을 연속 저장하고 각 부분 문자열에 대한 포인터를 사용하며, 메모리 이용률과 탐색 시간 모두 효율적입니다

4. 자료의 추상화

추상화는 크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법입니다.

자료 추상화 (data abstraction)

처리할 자료, 연산, 자료형에 대한 추상화 표현을 의미합니다.

• 자료: 프로그램의 처리 대상이 되는 모든 것
• 연산: 어떤 일을 처리하는 과정으로, 연산자에 의해 수행됩니다
• 자료형: 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합입니다
  • 예: 정수 자료형 - 정수의 집합과 +, -, x, ÷, mod 연산자 집합

추상 자료형 (ADT, Abstract Data Type)

자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형입니다.

• 추상화: "무엇(what)인가?"를 논리적으로 정의하는 단계입니다
• 구체화: "어떻게(how) 할 것인가?"를 실제적으로 표현하는 단계입니다

참고: 자료와 연산에 있어서 추상화는 '추상 자료형'과 '알고리즘 정의'에 해당하며, 구체화는 '자료형'과 '프로그램 구현'에 해당합니다

실습 툴 설치 및 활용

Visual Studio 2019 Community를 활용하여 실습 환경을 구축하고 C 언어로 자료구조 및 알고리즘을 구현합니다.