Programming Principles [3]: 데이터 추상화와 리스트 (Data Structures & List)

추상화는 복잡한 시스템에서 핵심적인 부분만을 남기고 불필요한 세부 사항을 제거하는 개념이다. 너무 추상적인 설명은 실질적인 정보가 부족하고, 너무 구체적인 설명은 불필요한 정보를 포함하여 비효율적일 수 있다. 따라서 적절한 수준에서 핵심 정보만을 남기는 것이 중요하다. 프로그램 역시 추상화의 한 형태로, 프로그램이 무엇을 해야 하는지는 설명하지만, 내부적으로 어떻게 동작하는지는 숨긴다.

자동차를 운전할 때, 운전자는 액셀러레이터(가속 페달)와 브레이크를 조작하며 속도를 조절한다. 하지만 자동차 내부에서는 엔진이 연료를 연소하고, 변속기가 동력을 조절하며, 브레이크 시스템이 작동하는 등 복잡한 과정이 일어난다. 프로그래밍에서도 이와 같은 개념이 적용된다. 예를 들어, car.accelerate()라는 함수를 호출하면 차가 가속되지만, 내부적으로 엔진과 변속기가 어떻게 작동하는지는 몰라도 된다. 즉, 사용자는 "어떻게?"(how)가 아닌 "무엇을?"(what)에 집중할 수 있다.

1.2 추상 데이터 타입 (ADT, Abstract Data Type)

추상 데이터 타입(ADT, Abstract Data Type)은 데이터와 데이터를 조작하는 연산을 정의하는 데이터 타입으로, 내부 구현 방식과는 독립적으로 동작한다. 즉, ADT는 "무엇을 할 수 있는지"를 정의하지만, "어떻게 구현되는지"는 숨긴다. 예를 들어, 리스트(List) ADT는 데이터를 저장하고 추가, 삭제할 수 있는 기능을 제공한다. 하지만 리스트가 배열로 구현되었는지, 연결 리스트로 구현되었는지는 ADT의 정의에서 중요하지 않다. ADT는 크게 데이터(Data)와 연산(Operations)으로 나뉜다.

데이터(Data): ADT가 다루는 정보의 종류. (예: 정수 리스트, 문자열 집합 등)
연산(Operations): ADT가 제공하는 기능. (예: 데이터 추가, 삭제, 탐색 등)

이러한 연산은 ADT를 사용하는 사람이 알고 있어야 하지만, 구현 방식은 몰라도 된다. 추상 데이터 타입(ADT)은 동일한 개념을 가지더라도 구현 방식이 다를 수 있으며, 제공하는 연산의 수도 차이가 있을 수 있다. 하지만 ADT가 정의하는 핵심 연산은 동일하게 유지된다. 즉, 같은 ADT라도 언어나 라이브러리에 따라 내부 구현이 다를 수 있고, 추가적인 기능이 포함될 수도 있지만, 기본적인 연산은 일관되게 제공된다.

정보 은닉 (Information Hiding)란?

정보 은닉(Information Hiding)은 모듈의 내부 세부 사항을 숨기고, 외부에서는 특정한 인터페이스를 통해서만 접근할 수 있도록 하는 개념이다. 이는 시스템의 복잡성을 줄이고, 데이터의 무결성을 보호하며, 유지보수를 쉽게 하기 위한 중요한 소프트웨어 설계 원칙이다. 정보를 직접 접근할 수 없도록 제한하고, 필요한 기능만 공개하는 방식은 캡슐화(Encapsulation)와 유사하다.

소프트웨어 시스템에서 각 모듈(예: 클래스, 함수 등)은 특정 기능을 수행하는 독립적인 블록으로 구성된다. 하지만 모듈의 내부 동작을 외부에서 직접 조작할 수 있다면, 예상치 못한 오류나 보안 문제가 발생할 수 있다. 이를 방지하기 위해 정보 은닉을 적용하여, 내부 세부 사항을 숨기고 필요한 기능만 외부에서 사용할 수 있도록 설계한다. 예를 들어, 은행 시스템에서 사용자의 계좌 정보는 매우 민감한 데이터다. 계좌 잔액을 마음대로 변경할 수 있도록 허용한다면 보안 문제가 발생할 수 있다. 따라서, balance(잔액) 변수는 private으로 설정하고, deposit(amount) 및 withdraw(amount) 같은 메서드를 통해서만 값을 변경하도록 한다. 정보 은닉은 다음과 같은 장점이 있다.

보안(Security): 중요한 데이터가 외부에서 직접 변경되지 않도록 보호할 수 있다.
무결성(Integrity) 보장: 데이터를 조작할 때 특정 규칙(예: 음수 금액 출금 금지)을 적용하여 예상치 못한 오류를 방지할 수 있다.
유지보수성(Maintainability) 증가: 내부 구현이 변경되더라도, 인터페이스(메서드)는 그대로 유지되므로 코드 변경이 쉽다.
모듈화(Modularity) 향상: 각 모듈이 독립적으로 동작하며, 다른 모듈과 불필요하게 결합되지 않는다

정보 은닉과 캡슐화는 서로 관련이 깊은 개념이다. 캡슐화(Encapsulation)는 데이터와 연산을 하나의 단위로 묶는 개념이며, 정보 은닉(Information Hiding)은 캡슐화된 데이터 중 특정 정보에 대한 접근을 제한하는 개념이다. 즉, 캡슐화는 정보 은닉을 포함하는 더 넓은 개념이며, 정보 은닉을 통해 데이터를 보호하고, 시스템을 보다 안전하게 만들 수 있다. 더 자세한 설명은 이전 페이지의 객체지향 프로그래밍 참고.

1.3 데이터 추상화 (Data Abstraction)

데이터(Data)란 사람이든 컴퓨터든 이해하고 사용할 수 있도록 표현된 정보다. 쉽게 말해, 우리가 일상에서 접하는 모든 숫자, 문자, 이미지, 소리 등은 데이터가 될 수 있다. 예를 들어, 스마트폰으로 찍은 사진도 데이터이고, 친구에게 보낸 문자 메시지도 데이터다. 프로그래밍에서는 데이터가 중요한 두 가지 역할을 한다.

첫째, 프로그램이 처리하는 핵심 요소로서 존재한다. 예를 들어, 유튜브에서 동영상을 검색할 때 입력하는 검색어, 온라인 쇼핑몰에서 판매되는 상품 목록, 스마트워치가 측정하는 심박수 같은 것들이 모두 데이터다. 프로그램은 이러한 데이터를 받아들여 처리하고, 사용자에게 원하는 결과를 보여준다. 둘째, 객체 지향 프로그래밍(OOP)에서는 데이터가 객체(Object)라는 개념으로 사용된다. 객체는 데이터를 포함할 뿐만 아니라, 그 데이터를 다룰 수 있는 기능(메서드)도 함께 가진다. 예를 들어, 자동차(Car)라는 개념을 코드로 만든다고 생각해보자. 이때 Car 객체는 색깔(color), 속도(speed), 브랜드(brand) 같은 데이터를 가지고 있을 수 있다. 하지만 자동차는 단순한 정보 덩어리가 아니라 움직일 수도 있어야 한다. 따라서 accelerate(가속), brake(멈춤) 같은 기능(메서드)도 함께 포함된다. 이렇게 하면 Car 객체를 사용해 다양한 자동차를 만들고, 동일한 기능을 공유하면서도 각기 다른 속성을 가질 수 있다.

즉, 데이터는 단순한 정보가 아니라 프로그램이 동작하는 데 필수적인 요소이며, 객체 지향 프로그래밍에서는 데이터와 행동이 하나의 객체로 결합되어 코드의 재사용성과 유지보수성을 높이는 데 도움을 준다.

데이터 추상화(Data Abstraction)는 데이터 타입의 논리적 특성(추상적인 측면)과 이를 구현하는 방식(구체적 구현)을 분리하는 개념이다. 논리적 특성은 데이터를 다룰 때 고려해야 할 요소들을 정의하는 것으로, 데이터가 가질 수 있는 값, 수행할 수 있는 연산, 그리고 사용할 수 있는 데이터 타입 등을 포함한다. 예를 들어, 학생(Student) 객체를 설계한다고 가정해보자. 이때 학생의 ID, 이름, 생년월일 같은 속성을 정의하고, 학생 정보를 추가(add), 삭제(delete), 수정(update)하는 연산이 필요함을 결정하는 과정이 바로 논리적 특성이다. 반면, 구체적 구현은 이러한 기능을 실제로 어떻게 구현할지를 결정하는 부분이다. 예를 들어, void add(Student s) { /* 데이터베이스에 저장하는 코드 */ }처럼 내부적으로 데이터가 어떻게 저장되며, 연산이 어떤 방식으로 수행되는지를 코드로 정의하는 것이 구체적 구현에 해당한다.

자료 구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하는 방법을 의미한다. 이를 이해하기 위해 도서관을 예로 들어보자. 도서관에는 수많은 책이 있지만, 책이 무작위로 쌓여 있다면 원하는 책을 찾기가 매우 어려울 것이다. 따라서 도서관에서는 책을 특정한 방식으로 정리하여 배치하는데, 예를 들어 주제별, 작가별, 혹은 고유 번호별로 정렬할 수 있다. 이러한 정리 방식이 바로 자료 구조에 해당한다.

예를 들어, 가장 단순한 자료 구조인 배열(Array)은 책이 일렬로 정리된 책장과 같다. 책장에는 여러 권의 책이 순서대로 놓여 있으며, 각 책은 고유한 위치(인덱스)를 가지고 있어 특정 책을 찾을 때 빠르게 접근할 수 있다. 반면에 연결 리스트(Linked List)는 책을 일렬로 정렬하는 대신, 각 책이 다음 책을 가리키는 방식으로 연결된 형태라고 볼 수 있다. 이러한 구조는 새로운 책을 추가하거나 삭제할 때 더 유연하게 동작할 수 있다.

복합 데이터 타입(Composite Data Type)은 여러 개의 개별 데이터를 하나의 단위로 묶어서 다룰 수 있는 데이터 타입이다. 예를 들어, 학생(Student)의 정보를 관리한다고 가정해 보자. 학생의 이름, 학점(GPA), 나이 등의 데이터는 각각 문자형(char), 실수형(float), 정수형(int)과 같은 기본 데이터 타입으로 저장할 수 있다. 하지만 학생 한 명의 정보를 하나의 변수로 관리하기 위해서는 개별 데이터 요소를 하나의 구조로 묶을 필요가 있다. 이를 가능하게 해주는 것이 바로 복합 데이터 타입이다. 복합 데이터 타입에는 대표적으로 구조체(Struct)와 클래스(Class)가 있다. 구조체는 여러 개의 서로 다른 데이터 타입을 하나로 묶는 방법이며, 클래스는 구조체와 비슷하지만 객체 지향적인 특징을 가지고 있어 데이터와 함수를 함께 포함할 수 있다. 예를 들어, StudentRecord라는 구조체를 정의하여 학생 정보를 저장하는 방법을 살펴보자.

struct StudentRecord {
    char name[10]; // 학생 이름
    float GPA;     // 학점
    int age;       // 나이
};

int main() {
    StudentRecord student1 = {"Alice", 3.8, 21}; // 구조체 변수 선언 및 초기화

    cout << "이름: " << student1.name << endl;
    cout << "학점: " << student1.GPA << endl;
    cout << "나이: " << student1.age << endl;

    return 0;
}

위 코드에서 StudentRecord 구조체는 name, GPA, age라는 세 가지 데이터를 하나의 단위로 묶어서 저장한다. 그리고 student1이라는 변수를 생성하여 특정 학생의 정보를 저장하고 출력할 수 있다. 구조체와 비슷하지만 더 강력한 기능을 제공하는 것이 클래스(Class)이다. 클래스는 멤버 변수뿐만 아니라 멤버 함수도 포함할 수 있어 데이터 보호 및 조작이 용이하다. 다음은 같은 StudentRecord를 클래스 형태로 정의한 예제이다.

#include <iostream>
#include <cstring> // strcpy 함수 사용을 위해 필요
using namespace std;

class StudentRecord {
private:
    char name[10]; 
    float GPA;
    int age;

public:
    // 생성자(Constructor)
    StudentRecord(const char* student_name, float student_GPA, int student_age) {
        strcpy(name, student_name);
        GPA = student_GPA;
        age = student_age;
    }

    // 학생 정보 출력 함수
    void displayInfo() {
        cout << "이름: " << name << endl;
        cout << "학점: " << GPA << endl;
        cout << "나이: " << age << endl;
    }
};

int main() {
    StudentRecord student1("Bob", 3.9, 22); // 객체 생성 및 초기화
    student1.displayInfo(); // 학생 정보 출력

    return 0;
}

이 코드에서 StudentRecord 클래스는 생성자를 통해 데이터를 초기화하고, displayInfo() 함수를 이용하여 학생 정보를 출력할 수 있다. 클래스는 구조체와 달리 멤버 변수를 private으로 설정하여 외부에서 직접 접근하지 못하도록 보호할 수도 있다. 복합 데이터 타입을 사용하면 데이터를 구조화하여 효율적으로 관리할 수 있으며, 여러 개의 관련 정보를 하나의 단위로 다룰 수 있어 프로그램의 가독성과 유지보수성이 향상된다. 특히, 클래스는 객체 지향 프로그래밍의 기본 개념인 캡슐화(Encapsulation), 상속(Inheritance), 다형성(Polymorphism)과 결합하여 더욱 강력한 기능을 제공한다.

클래스(Class)와 구조체(Struct)는 다음과 같은 방식으로 활용할 수 있다.

같은 타입의 다른 변수에 할당 – 동일한 클래스 또는 구조체 타입의 변수를 다른 변수에 복사할 수 있다.
함수의 매개변수로 전달 – 값으로 전달(Call by Value)하면 복사본이 생성되며, 참조로 전달(Call by Reference)하면 원본 데이터를 직접 수정할 수 있다.
함수의 반환값으로 사용 – 함수에서 클래스 또는 구조체 객체를 반환할 수 있으며, 호출한 곳에서 해당 객체를 활용할 수 있다.

1.4 Memory Application

컴퓨터 아키텍처를 이해하려면 CPU, 메모리, 저장 장치의 관계를 먼저 알아야 한다. CPU는 컴퓨터의 핵심 연산 장치로, 프로그램의 명령을 해석하고 실행하는 역할을 한다. 메모리는 CPU가 빠르게 데이터를 처리할 수 있도록 임시 저장 공간을 제공하지만, 용량이 한정적이고 가격이 비싸다. 반면, 저장 장치는 속도는 느리지만 대용량 데이터를 보관할 수 있으며, HDD와 SSD가 이에 해당한다.

이 과정을 쉽게 이해하기 위해 책을 읽는 과정과 비교할 수 있다. 저장 장치는 책장과 같고, 메모리는 책상과 같다. 책장에는 많은 책이 있지만, 한꺼번에 책상에 모두 펼쳐둘 수 없기 때문에 필요한 책만 꺼내서 책상에 놓고 읽는다. 마찬가지로, 프로그램과 데이터는 평소에는 저장 장치에 보관되다가 실행될 때 메모리로 불러와진다. CPU는 사람의 두뇌와 같은 역할을 한다. 책상 위에 펼쳐진 책을 독자가 읽듯이, CPU는 메모리에서 프로그램의 데이터를 가져와 처리한다. 예를 들어, 사용자가 "리그 오브 레전드(LoL)"를 실행하면, 컴퓨터는 LoL의 데이터를 저장 장치에서 찾아 메모리로 불러온다. 그 후 CPU는 메모리에 적재된 데이터를 읽고 실행하면서 게임이 원활하게 동작하도록 한다.

하지만 메모리의 공간은 한정적이기 때문에, 여러 개의 프로그램을 동시에 실행하면 공간이 부족해질 수 있다. 책상 위에 너무 많은 책을 올려놓으면 정리가 어려운 것처럼, 메모리에 너무 많은 데이터가 올라가면 속도가 느려진다. 이를 해결하기 위해 운영체제는 가장 덜 사용되는 데이터를 다시 저장 장치로 보내고, 필요한 데이터를 불러오는 작업을 반복한다. 예를 들어, 사용자가 LoL을 실행하는 동안 오래 사용하지 않은 MS Word의 일부 데이터를 저장 장치로 이동시키는 방식이다. 컴퓨터가 프로그램을 실행하는 과정을 정리하면 다음과 같다. 먼저 사용자가 LoL 실행 버튼을 누르면, 운영체제가 HDD나 SSD에서 LoL을 찾아 메모리로 불러온다. CPU는 메모리 속 데이터를 읽고 처리하여 게임을 실행한다. 만약 메모리가 부족하면, 운영체제는 사용하지 않는 프로그램의 데이터를 저장 장치로 이동시키고 필요한 데이터를 불러오는 작업을 수행한다.

메모리 할당(Memory Allocation)은 프로그램이 실행될 때 운영체제가 필요한 메모리를 자동으로 할당하는 과정이다. 프로그램이 실행되면, 변수와 객체를 저장할 수 있도록 메모리 공간이 할당되며, 이는 코드 실행에 필요한 명령어와 데이터를 저장하는 데 사용된다. 변수를 선언하면, 운영체제는 해당 변수의 데이터 타입에 따라 적절한 크기의 메모리 공간을 할당한다. 예를 들어, int int_val;와 같이 정수를 선언하면 sizeof(int) 값에 따라 4바이트의 메모리가 할당된다. 마찬가지로, float float_val;은 sizeof(float) 값인 4바이트를 차지하며, short short_val;은 2바이트, char char_val;은 1바이트를 차지한다. 각각의 변수는 메모리 내 특정 주소에 저장되며, 프로그램이 실행되는 동안 이 공간을 사용하게 된다. 객체(Object)의 경우, 객체가 생성될 때 내부 멤버 변수들을 저장할 수 있도록 필요한 메모리 공간이 할당된다. 예를 들어, StudentRecord라는 클래스를 선언하고, 그 안에 char name[10];, float GPA;, int age; 멤버 변수가 있다면, 이 클래스의 객체가 생성될 때 10바이트의 문자 배열, 4바이트의 실수형 변수, 4바이트의 정수형 변수가 메모리에 배치된다.

객체를 생성하고 데이터를 저장하는 과정에서도 메모리 할당이 이루어진다. 예를 들어, StudentRecord temp_student;를 선언하면, temp_student라는 객체가 생성되면서 name, GPA, age를 저장할 메모리 공간이 할당된다. 이후 temp_student.name = "Alice";라고 하면, "Alice"라는 문자열이 name 배열에 저장되며, 각 문자는 1바이트씩 차지하고 마지막에는 문자열 종료를 나타내는 '\0'이 추가된다. temp_student.GPA = 3.65;가 실행되면, GPA 변수에 4바이트 크기의 float 값이 저장되고, temp_student.age = 22;가 실행되면 age 변수에 4바이트 크기의 정수 값이 저장된다.

이러한 메모리 할당 과정에서 중요한 개념 중 하나는 데이터 정렬(data alignment)이다. 특정 아키텍처에서는 성능 최적화를 위해 변수가 특정 주소에서 정렬되어야 하며, 이에 따라 구조체의 실제 메모리 크기는 개별 변수 크기의 합보다 클 수 있다. 예를 들어, 위 구조체에서 name이 10바이트를 차지하고, 이후 GPA(4바이트)와 age(4바이트)가 배치되는데, 데이터 정렬로 인해 name 뒤에 2바이트의 패딩(padding)이 추가될 수도 있다. 결과적으로, 메모리 할당은 변수와 객체의 크기뿐만 아니라 데이터 정렬 방식에 따라 결정되며, 이를 효율적으로 관리하는 것이 프로그램 성능과 안정성에 영향을 미친다.

2차원 배열 intArray[5][12]에서 각 요소는 메모리에 행(row) 순서대로 일렬로 저장된다. intArray[3][7]의 주소를 계산할 때는 아래 공식을 사용한다. 주소 = BaseAddress + (행 × 열의 개수 × 요소 크기) + (열 × 요소 크기) 여기서 BaseAddress가 2000이고, 요소의 크기(sizeof(int))가 4바이트, 총 열 개수는 12이므로, intArray[3][7]의 주소는 2000 + (3 × 12 × 4) + (7 × 4) = 2000 + 144 + 28 = 2172가 된다. 즉, 메모리 상에서 intArray[3][7]은 주소 2172번지에 저장된다.

2. 리스트 (List)

리스트는 요소들이 순서대로 배열된 데이터 구조로, 각 요소는 특정한 위치를 가지며 선형적인 관계를 형성한다. 리스트에서 선형 관계(Linear relationship)란 각 요소가 특정한 순서로 정렬되어 있으며, 첫 번째 요소를 제외한 모든 요소는 하나의 이전 요소(Predecessor)를 가지고 있고, 마지막 요소를 제외한 모든 요소는 하나의 다음 요소(Successor)를 가지는 것을 의미한다.

예를 들어, 리스트 [A, B, C, D]에서 B는 A의 후속 요소이며, C의 선행 요소가 된다. 리스트의 길이(Length)는 포함된 요소의 개수를 나타내며, 리스트의 상태에 따라 변할 수 있다. 예를 들어, 리스트 [10, 20, 30]의 길이는 3이지만, 새로운 요소 40을 추가하면 길이가 4로 증가한다. 반대로 요소를 제거하면 길이가 줄어든다.

리스트는 요소의 정렬 여부에 따라 정렬되지 않은 리스트(Unsorted list)와 정렬된 리스트(Sorted list)로 구분된다. 정렬되지 않은 리스트는 요소들이 특정한 순서 없이 저장되며, 삽입과 삭제가 자유롭게 이루어진다. 예를 들어, 리스트 [5, 1, 8, 3, 2]는 정렬되지 않은 상태로, 요소들이 임의의 순서로 배치되어 있다. 반면, 정렬된 리스트는 요소들이 특정한 기준(예: 오름차순 또는 내림차순)에 따라 정렬되어 있으며, 새로운 요소를 추가할 때도 정렬을 유지해야 한다. 예를 들어, 리스트 [1, 2, 3, 5, 8]은 오름차순으로 정렬된 상태이다. 정렬된 리스트는 검색이 효율적일 수 있지만, 삽입과 삭제 시 정렬을 유지하기 위해 추가적인 연산이 필요하다는 특징이 있다.

1.1 Unsorted List

Concepts

정렬되지 않은 리스트(Unsorted list)는 데이터 항목이 특정한 순서 없이 저장되는 리스트를 의미한다. 요소들이 임의의 위치에 추가되며, 삽입과 삭제가 자유롭게 이루어진다. 예를 들어, [7, 3, 9, 1, 5]와 같은 리스트는 특정한 정렬 기준 없이 요소들이 배치된 상태이다. 새로운 요소를 추가할 때도 정렬을 신경 쓰지 않고 마지막이나 특정 위치에 삽입할 수 있다. 이러한 리스트는 데이터를 빠르게 추가하거나 삭제하는 데 유리하지만, 특정 요소를 찾기 위해 리스트를 처음부터 끝까지 탐색해야 하므로 검색 효율이 떨어질 수 있다.

ADT(Abstract Data Type) 연산

생성자(Constructor): ADT의 인스턴스를 생성한다.
변환자(Transformer): 데이터 값을 변경한다.
관찰자(Observer): 데이터 값을 변경하지 않고 상태를 확인한다.

Implementation

UnsortedType::UnsortedType() {
    length = 0;
}

리스트가 생성될 때 length를 0으로 초기화하여 빈 리스트를 구성한다. 반환형이 없으며 객체 생성 시 자동 호출된다.

void UnsortedType::appendItem(ItemType value) {
    if (isFull()) return;
    data[length] = value;
    length++;
}

새로운 값을 리스트의 끝에 추가한다. 배열의 다음 위치에 값을 넣고 length를 증가시킨다. O(1)의 시간 복잡도를 가진다.

void UnsortedType::insertItem(int pos, ItemType value) {
    if (isFull()) return;
    for (int i = length; i > pos; i--) {
        data[i] = data[i - 1];
    }
    data[pos] = value;
    length++;
}

리스트의 특정 위치에 값을 삽입하며, 이후의 모든 데이터를 한 칸씩 뒤로 이동시킨다. pos가 작을수록 많은 이동 연산이 발생하여 O(N)의 시간 복잡도를 가진다.

void UnsortedType::removeItem(ItemType value) {
    if (isEmpty()) return;
    for (int i = 0; i < length; i++) {
        if (data[i] == value) {
            for (int j = i + 1; j < length; j++) {
                data[j - 1] = data[j];
            }
            length--;
            break;
        }
    }
}

특정 값을 찾아 제거하며, 제거된 위치 뒤의 데이터를 앞으로 이동시킨다. 최악의 경우 O(N)의 시간 복잡도를 가진다.

void UnsortedType::improved_removeItem(ItemType value) {
    if (isEmpty()) return;
    for (int i = 0; i < length; i++) {
        if (data[i] == value) {
            data[i] = data[length - 1];
            length--;
            break;
        }
    }
}

제거할 값을 찾은 후, 마지막 원소를 해당 위치로 복사하여 이동 연산을 최소화한다. 데이터 순서를 유지할 필요가 없을 때 O(1)에 가까운 연산이 가능하다.

void UnsortedType::updateItem(int pos, ItemType new_value) {
    if (pos >= length) return;
    data[pos] = new_value;
}

리스트의 특정 위치 값을 새 값으로 대체한다. 인덱스 범위 확인 후 단순 대입이므로 O(1) 연산이다.

void UnsortedType::clear() {
    length = 0;
}

length만 0으로 만들어 리스트를 초기화한다. 배열 자체는 그대로 남지만 이후 삽입 시 덮어씌워진다. 매우 효율적인 O(1) 연산이다

int UnsortedType::size() {
    return length;
}

현재 리스트의 길이를 반환한다. 연산량이 적어 O(1)이다.

bool UnsortedType::isFull() {
    return (length == MAX_SIZE);
}

리스트가 꽉 찼는지 확인하는 함수로, 배열의 최대 크기와 현재 길이를 비교한다.

bool UnsortedType::isEmpty() {
    return (length == 0);
}

리스트가 비어있는지를 확인한다. 조건문 하나로 O(1) 시간에 수행된다.

ItemType UnsortedType::getItem(int pos) {
    if (pos >= length) throw std::out_of_range("Error");
    return data[pos];
}

특정 위치의 값을 반환한다. 인덱스를 검사하고 해당 값을 반환하는 단순한 연산이다.

bool UnsortedType::findItem(ItemType item) {
    int location = 0;
    while (location < length) {
        if (data[location] == item) return true;
        location++;
    }
    return false;
}

리스트 내에서 특정 값을 선형 탐색하며, 발견 시 true, 끝까지 못 찾으면 false를 반환한다. 평균 O(N/2), 최악 O(N)의 성능을 가진다.

appendItem( ) vs insertItem( )

appendItem(value)는 리스트의 끝에 새로운 값을 추가하는 함수이며, insertItem(pos, value)는 리스트의 특정 위치에 값을 삽입하는 함수이다. 이 두 연산의 속도를 비교하기 위해 시간 복잡도를 분석해보자.

appendItem(value)는 리스트의 끝에 값을 추가하는 연산으로, 두 가지 연산이 필요하다.

리스트의 마지막 위치에 value 추가 → 1 연산
리스트의 길이 length 증가 (length++) → 1 연산

즉, 총 2번의 연산이 필요하며, 리스트의 크기에 관계없이 항상 일정한 연산량이 요구된다. 따라서 시간 복잡도는 O(1) 이다. 예를 들어, 리스트의 길이가 length = 1000이라 하더라도 appendItem(value)의 연산 횟수는 여전히 2번으로 변함이 없다. 즉, 리스트 크기와 무관하게 일정한 시간이 소요되는 연산이다.

insertItem(pos, value)는 리스트의 특정 위치에 값을 삽입하는 연산으로, 여러 개의 연산이 필요하다.

pos 이후의 모든 데이터를 한 칸씩 뒤로 이동 → length - pos 개의 연산
pos 위치에 value 삽입 → 1 연산
리스트의 길이 length 증가 (length++) → 1 연산

즉, insertItem(pos, value)의 총 연산 횟수는 리스트 길이에 따라 달라지며, O(n)의 시간 복잡도를 가진다.
만약 리스트의 길이가 1000이고 pos = 1이라면,

999번의 데이터 이동 연산
1번의 값 삽입 연산
1번의 길이 증가 연산

총 1001번의 연산이 필요하다. 리스트 크기가 커질수록 삽입 연산의 비용이 커진다.

appendItem(value)는 항상 O(1)의 시간 복잡도를 가지므로, 리스트의 크기에 관계없이 일정한 속도로 실행된다. 반면, insertItem(pos, value)는 O(n)의 시간 복잡도를 가지므로 리스트가 클수록 삽입 위치에 따라 실행 시간이 길어질 수 있다. 즉, 리스트의 끝에 요소를 추가할 경우에는 appendItem(value)가 훨씬 빠르며, 특정 위치에 값을 삽입해야 하는 경우에는 insertItem(pos, value)의 비용이 높아질 수 있다. 리스트의 크기가 커질수록 insertItem()의 성능 차이가 더욱 두드러지므로, 효율적인 알고리즘을 설계할 때 이러한 연산 비용을 고려해야 한다.

* Big-O 표기법에서 시간 복잡도를 단순화할 때는 두 가지 주요 정리가 있다. 정리 1은 계수(coefficient)는 무시한다는 것으로, 예를 들어 O(2N)이나 O(3N²)처럼 앞에 붙은 숫자는 알고리즘의 성장률에 큰 영향을 주지 않으므로 각각 O(N), O(N²)로 표현된다. 정리 2는 현저히 작은 항은 무시한다는 것으로, 예를 들어 O(N² + 3N + 5)는 N²이 가장 빠르게 증가하므로 O(N²)로 단순화되며, O(2ⁿ + 4N³ + 5N² + 7N + 6)의 경우에도 2ⁿ이 지수적으로 가장 크게 성장하기 때문에 O(2ⁿ)으로 표현된다. 요약하면, Big-O에서는 가장 영향력 있는 항만 남기고 나머지는 모두 생략합니다.

void UnsortedType::improved_insertItem(int pos, ItemType value) {
    if (isFull()) return;

    data[length] = data[pos];  // ① pos 위치의 원소를 마지막 위치로 복사
    data[pos] = value;         // ② 새 값을 pos 위치에 삽입
    length++;                  // ③ 리스트 길이 증가
}

improved_insertItem은 일반적인 insertItem보다 효율적인 방식으로 삽입을 수행하는 함수이다. 기존 방식은 삽입 위치 이후의 모든 데이터를 한 칸씩 뒤로 이동시켜야 했지만, 이 방식은 간단히 pos 위치의 데이터를 마지막 빈 칸으로 복사하고, 새 값을 pos 위치에 바로 삽입함으로써 이동 연산을 한 번만 사용한다.. 리스트의 순서가 중요하지 않은 Unsorted List의 특성을 활용한 최적화이며, 항상 O(1)의 시간복잡도를 가진다.

1.2 Sorted List

Concepts

정렬된 리스트는 키(key) 값에 따라 정렬된 상태로 유지되며, 리스트 내부 요소들 간에는 특정한 의미론적 순서 관계가 존재한다. 예를 들어, sorted_list = [2, 3, 6, 7, 9, 12]와 같이 정렬될 수 있으며, 데이터의 특정 속성을 기준으로 정렬될 수도 있다. 학생 정보를 예로 들면, ID, GPA, 생년월일 등의 기준에 따라 정렬하여 관리할 수 있다.

// SortedType.h
typedef int ItemType;
class SortedType {
private:
    ItemType data[MAX_SIZE];
    int length;
public:
    SortedType();
    void insertItem(ItemType value);
    void removeItem(ItemType value);
    void updateItem(ItemType old_value, ItemType new_value);
    void clear();

    int size();
    bool isFull();
    bool isEmpty();
    bool findItem(ItemType item);
    ItemType getItem(int pos);
};

implementation

SortedType::SortedType() {
    length = 0;
}

리스트 생성 시 length를 0으로 초기화하여 비어 있는 정렬 리스트를 구성한다. 반환형이 없으며 객체 생성 시 자동 호출된다.

void SortedType::insertItem(ItemType value) {
    if (isFull()) return;

    int location = 0;
    while (location < length) {
        if (value > data[location]) {
            location++;
        } else {
            break;
        }
    }

    for (int i = length; i > location; i--) {
        data[i] = data[i - 1];
    }

    data[location] = value;
    length++;
}

정렬을 유지하기 위해 삽입 위치를 선형 탐색으로 찾고, 이후 데이터들을 한 칸씩 뒤로 이동시켜 새 값을 삽입한다. 시간복잡도는 O(N)이며, 삽입은 항상 정렬 상태를 보존한다.

void SortedType::removeItem(ItemType value) {
    if (isEmpty()) return;

    int location = 0;
    while (location < length) {
        if (value > data[location]) {
            location++;
        } else if (value == data[location]) {
            break;
        } else {
            return;
        }
    }

    for (int i = location + 1; i < length; i++) {
        data[i - 1] = data[i];
    }

    length--;
}

삭제할 값을 탐색하고 찾은 위치 이후의 모든 항목을 앞으로 한 칸씩 이동시킨다. 최악의 경우 O(N)의 시간복잡도를 가지며, 정렬 상태를 유지한다.

void SortedType::updateItem(ItemType old_value, ItemType new_value) {
    removeItem(old_value);
    insertItem(new_value);
}

특정 값을 새로운 값으로 갱신하려면 먼저 해당 항목을 제거한 후, 새로운 값을 정렬된 위치에 다시 삽입한다. 두 연산이 O(N)이므로 전체 시간복잡도는 O(N)이다.

void SortedType::clear() {
    length = 0;
}

리스트를 초기화하는 함수로, 내부 데이터는 그대로 존재하되 length만 0으로 만든다. 이후 삽입 시 데이터를 덮어쓰므로, 매우 빠른 O(1)의 연산이다.

ItemType SortedType::getItem(int pos) {
    if (pos >= length) throw std::out_of_range("Error");
    return data[pos];
}

특정 인덱스에 있는 항목을 반환한다. 정렬된 리스트에서도 인덱스를 통해 직접 접근 가능하므로 O(1)의 성능을 가진다.

이진 탐색을 통한 검색 최적화

정렬된 리스트에서 findItem() 연산을 효율적으로 수행하기 위해 이진 탐색(Binary Search) 을 적용할 수 있다.

bool SortedType::findItem(ItemType item) {
    int mid;
    int first = 0;
    int last = length - 1;
    while (first <= last) {
        mid = (first + last) / 2;
        if (item < data[mid]) {
            last = mid - 1;
        } else if (item > data[mid]) {
            first = mid + 1;
        } else {
            return true;
        }
    }
    return false;
}

이진 탐색의 시간 복잡도는 O(logN) 이므로 선형 탐색보다 훨씬 효율적이다.

Time Complexity

'Computer Scinece > Programming Principles' 카테고리의 다른 글

Programming Principles [6] : 최적화 알고리즘 (Optimization Algorithms) (1)	2024.09.18
Programming Principles [5] : 재귀 알고리즘 (Recursive Algorithm) (0)	2024.09.18
Programming Principles [4]: 자료 구조 (Data Structures) (0)	2024.09.18
Programming Principles [2] : 객체지향 프로그래밍 (Object-Oriented Programming) (1)	2024.09.18
Programming Principles[1]: 프로그래밍 기본 (Basic Algorithms) (1)	2024.09.18

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Programming Principles [3]: 데이터 추상화와 리스트 (Data Structures & List)

1. 데이터 추상화 (Data Abstraction)

1.1 추상화 (Abstraction)

1.2 추상 데이터 타입 (ADT, Abstract Data Type)

1.3 데이터 추상화 (Data Abstraction)

1.4 Memory Application

2. 리스트 (List)

1.1 Unsorted List

Concepts

Implementation

1.2 Sorted List

Concepts

implementation

'Computer Scinece > Programming Principles' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역