Programming Principles [3]: 자료 구조 (Data Structures)

1. 자동 할당 (Automatic Allocation)

• 저장 위치: STACK
• 할당 시점: 함수 호출 시
• 해제 시점: 함수 종료 시
• 크기 변경: 불가 (고정)
• 장점: 간편, 자동 해제
• 단점: 메모리 크기 제한 있음

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

1.1 추상화 (Abstraction)

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

 

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

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

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

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

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

정보 은닉 (Information Hiding)란?

 

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

 

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

 

1. 보안(Security): 중요한 데이터가 외부에서 직접 변경되지 않도록 보호할 수 있다.
2. 무결성(Integrity) 보장: 데이터를 조작할 때 특정 규칙(예: 음수 금액 출금 금지)을 적용하여 예상치 못한 오류를 방지할 수 있다.
3. 유지보수성(Maintainability) 증가: 내부 구현이 변경되더라도, 인터페이스(메서드)는 그대로 유지되므로 코드 변경이 쉽다.
4. 모듈화(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)는 다음과 같은 방식으로 활용할 수 있다.

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

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. 리스트 (List)

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

ADT(Abstract Data Type) 연산

 

리스트는 ADT로 정의되며, ADT의 기본 연산은 다음과 같다.

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

Unsorted List - Logical Level

1. 생성자 (Constructor)
   • [ClassName]()
2. 변환자 (Transformer)
   • appendItem(value): 리스트 끝에 요소를 추가
   • insertItem(pos, value): 특정 위치에 요소를 삽입
   • removeItem(value): 특정 요소를 삭제
   • updateItem(pos, new_value): 특정 위치의 값을 갱신
   • clear(): 리스트를 비운다
3. 관찰자 (Observer)
   • size(): 리스트 크기 반환
   • isFull(): 리스트가 꽉 찼는지 확인
   • isEmpty(): 리스트가 비었는지 확인
   • findItem(item): 특정 아이템을 찾는다
   • getItem(pos): 특정 위치의 아이템을 가져온다

Unsorted List - Implement Level

// UnsortedType.h
typedef int ItemType;
class UnsortedType {
private:
    ItemType data[MAX_SIZE]; // 배열 기반 리스트
    int length;
public:
    UnsortedType();
    void appendItem(ItemType value);
    void insertItem(int pos, ItemType value);
    void removeItem(ItemType value);
    void updateItem(int pos, ItemType new_value);
    void clear();

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

Time Complexivity 

appendItem( ) vs insertItem( )

 

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

 

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

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

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

 

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

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

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

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

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

 

Which One is Faster?

 

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

 

정렬된 리스트에서의 탐색 연산을 살펴보면, 선형 탐색(Linear Search)은 O(N)의 시간 복잡도를 가지지만, 이진 탐색(Binary Search)은 O(log N)의 복잡도를 갖는다. 이진 탐색은 리스트가 정렬되어 있어야만 사용할 수 있으며, 탐색 범위를 절반씩 줄여 나가기 때문에 훨씬 효율적이다. 마지막으로, 리스트의 크기가 클수록 효율적인 알고리즘을 선택하는 것이 중요하다. 정렬이 필요한 경우 O(N log N)의 성능을 가지는 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)을 사용하고, 탐색이 빈번한 경우 정렬된 리스트를 활용하여 O(log N)의 탐색 성능을 갖는 이진 탐색을 적용하면 보다 효율적인 프로그램을 만들 수 있다.

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);
};

 

정렬된 리스트의 주요 연산

1. 삽입 (insertItem)
   • 적절한 위치를 찾은 후, 이후 요소를 한 칸씩 이동하여 공간을 만들고 삽입한다.
   • 시간 복잡도: O(N) (최악의 경우 모든 요소를 이동해야 함)
2. 삭제 (removeItem)
   • 요소를 찾은 후, 이후 요소를 한 칸씩 이동하여 공간을 메운다.
   • 시간 복잡도: O(N)
3. 탐색 (findItem)
   • 선형 탐색 (O(N))을 사용할 수도 있지만, 이진 탐색을 적용하면 O(logN)으로 효율을 높일 수 있다.

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

정렬된 리스트에서 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 

Time Com

 

3. Stack

스택(Stack)은 데이터를 저장하고 꺼내는 방식이 후입선출(Last In, First Out, LIFO) 구조인 선형 자료구조로, 삽입(push)과 삭제(pop) 연산이 오직 스택의 최상단(top)에서만 이루어진다. 이러한 특성 덕분에 되돌리기(Undo), 웹 브라우저의 뒤로 가기, 함수 호출 시의 호출 스택 등 다양한 분야에서 활용된다. 배열을 이용한 스택 구현에서는 top 변수로 스택의 상태를 관리하며, push, pop, isFull, isEmpty, size 등의 연산을 통해 데이터를 다룬다. 또한 C++의 클래스 템플릿을 사용하면 int, char, float, 사용자 정의 타입 등 다양한 자료형에 대해 코드 재사용이 가능하며, 스택은 함수 호출 시 자동 메모리 할당이 이루어지는 Stack 영역과도 밀접하게 연관되어 프로그램의 메모리 구조 이해에 중요한 역할을 한다.

 

분류	함수 이름	설명
생성자	StackType()	스택 객체를 초기화 (top 값을 -1로 설정)
변형자	push(value)	스택의 top에 값을 추가 (스택이 가득 차면 오류)
변형자	pop()	스택의 top 값을 제거하고 반환 (비어있으면 오류)
관찰자	size()	스택에 현재 저장된 요소의 개수를 반환
관찰자	isFull()	스택이 가득 찼는지 여부를 확인
관찰자	isEmpty()	스택이 비어 있는지 여부를 확인

 

✅ 1. Stack의 기본 구현 (배열 기반)

스택은 보통 배열(Array) 또는 **연결 리스트(Linked List)**를 통해 구현되며, 강의에서는 배열 기반 스택 구현을 다룹니다.

📄 클래스 정의 (Header File – StackType.h)

const int MAX_SIZE = 100;  // 최대 크기 지정

typedef int ItemType;      // 데이터 형식 (초기엔 int로 고정)

class StackType {
private:
    ItemType data[MAX_SIZE];  // 배열로 데이터 저장
    int top;                  // 스택의 꼭대기를 가리키는 인덱스

public:
    StackType();              // 생성자
    void push(ItemType value); 
    ItemType pop();           
    int size() const;
    bool isFull() const;
    bool isEmpty() const;
};

 

🧠 핵심 원리

• top == -1 → 스택이 비어 있는 상태
• push() → top++ 후 data[top]에 값 저장
• pop() → data[top]을 반환 후 top--

---

✅ 2. Stack 주요 함수 구현 예시 (.cpp 파일 기준)

✔ 생성자 (초기화)

 

StackType::StackType() {
    top = -1;
}

✔ push()

void StackType::push(ItemType value) {
    if (isFull()) {
        cout << "[Error] Stack is Full" << endl;
        return;
    }
    top++;
    data[top] = value;
}

✔ pop()

ItemType StackType::pop() {
    if (isEmpty()) {
        cout << "[Error] Stack is Empty" << endl;
        return -1;  // 오류 시 기본값 반환
    }
    return data[top--];
}

✔ size(), isFull(), isEmpty()

int StackType::size() const {
    return top + 1;
}

bool StackType::isFull() const {
    return top == MAX_SIZE - 1;
}

bool StackType::isEmpty() const {
    return top == -1;
}

 

✅ 3. Class Template의 활용

❓ 왜 필요할까?

기존의 typedef int ItemType 방식은 **하나의 자료형(int)**만 다룰 수 있어 유연성이 부족합니다.
→ 이를 해결하기 위해 C++의 Class Template 사용!

---

🔧 Stack Template 정의

template <class ItemType>
class StackType {
private:
    ItemType data[MAX_SIZE];
    int top;

public:
    StackType();
    void push(ItemType value);
    ItemType pop();
    int size() const;
    bool isFull() const;
    bool isEmpty() const;
};

 

구현 예 (push, pop)

template <class ItemType>
void StackType<ItemType>::push(ItemType value) {
    if (isFull()) {
        cout << "[Error] Stack is Full" << endl;
        return;
    }
    top++;
    data[top] = value;
}

template <class ItemType>
ItemType StackType<ItemType>::pop() {
    if (isEmpty()) {
        cout << "[Error] Stack is Empty" << endl;
        return ItemType();  // 기본값 반환
    }
    return data[top--];
}

 

✅ 4. Template 사용 예시

📦 정수형 스택

StackType<int> intStack;
intStack.push(10);

🔠 문자형 스택

StackType<char> charStack;
charStack.push('A');

🎯 사용자 정의 타입 (예: 학생 정보)

struct StudentRecord {
    string name;
    string id;
    string dob;
};

StackType<StudentRecord> studentStack;

✅ 5. 템플릿 사용 시 주의사항

• 템플릿은 선언(.h)과 구현을 하나의 파일에 포함시키는 것이 일반적
  → 분리 시 컴파일 에러 발생 가능
• 다양한 자료형에 대해 동일한 코드 재사용 가능하여 유지 보수와 확장성이 높아짐

메모리 할당

 

✅ 개요

프로그램이 실행될 때 사용하는 메모리는 STACK, HEAP, DATA, BSS, CODE로 나뉘며, 변수의 선언 방식에 따라 어디에, 언제, 어떻게 메모리가 할당되고 해제되는지가 달라집니다. 이 개념은 C/C++ 같은 시스템 프로그래밍 언어에서 특히 중요합니다.

---

🧠 메모리 구조 요약

영역	설명	예시 대상
Stack	함수 호출 시 지역 변수 저정	지역 변수, 함수 파라미
Heap	동적 메모리 할당 공간	new, malloc으로 할당한 변수
Data	초기값 있는 전역/정적 변수 저장	int x = S; 전역 변수
Bss	초기값 없는 전역/정적 변수	static int count;
Code(text)	프로그램의 실행 코드 영역	함수, 로직 등

 

1. 자동 할당 (Automatic Allocation)

• 저장 위치: STACK
• 할당 시점: 함수 호출 시
• 해제 시점: 함수 종료 시
• 크기 변경: 불가 (고정)
• 장점: 간편, 자동 해제
• 단점: 메모리 크기 제한 있음

📌 코드 예시

void sum() {
    int a = 3;
    int b = 5;
    int result = a + b;
    cout << result << endl;  // 8 출력
}  // 함수 종료 시 a, b, result는 사라짐

🧠 Stack 구조 (함수 호출 순서)

main()
  -> sum() 호출 → 지역 변수 a, b, result 생성
  <- sum() 종료 → 지역 변수 메모리 해제

 

2. 동적 할당 (Dynamic Allocation)

• 저장 위치: HEAP
• 할당 시점: 실행 중(new/malloc 호출 시)
• 해제 시점: 개발자가 명시적으로 delete/free 호출 시
• 크기 변경: 가능
• 장점: 유연한 크기 조절 가능
• 단점: 메모리 누수 위험, 해제를 직접 해야 함

📌 코드 예시

int* makeArray(int size) {
    int* arr = new int[size];  // HEAP에 메모리 할당
    return arr;
}

int main() {
    int* myArr = makeArray(5);
    // ... 사용 중 ...
    delete[] myArr;  // 꼭 해제해야 함
    return 0;
}

⚠ 누수 위험 예시 (메모리 해제 안 한 경우)

void leak() {
    int* data = new int[100];
    // delete[] data;  // 생략되면 누수 발생
}

3. 정적 할당 (Static Allocation)

• 저장 위치: DATA or BSS
• 할당 시점: 프로그램 시작 시
• 해제 시점: 프로그램 종료 시
• 크기 변경: 불가
• 장점: 상태 유지 가능
• 단점: 메모리 항상 차지함

📌 코드 예시

void counter() {
    static int count = 0;
    count++;
    cout << "호출 횟수: " << count << endl;
}

int main() {
    counter();  // 호출 횟수: 1
    counter();  // 호출 횟수: 2
}

static 변수는 함수 내에 있어도 함수 종료 후 값이 유지됨