혼잣말처럼 넘기는 자료구조 (파트1)

[출처: Data Structures Explained]
목차
파트 1	기본 용어 및 개념 > 추상화, 성능 등등.  배열  스택  큐
파트 2	연결 리스트 > 기본 개념 > 단순 연결 리스트 > 단순 원형 연결 리스트 > 이중 연결 리스트  이진 트리 > 기본 개념 > 형태 > 연산
파트 3	그래프 > 기본 개념 > 기술하기 > 탐색 > 최소 신장 트리: 프림, 크루스컬, 솔린  힙 > 기본 개념 > 형태 > 연산
파트 4	선택 트리 > 승자 트리, 패자 트리  숲  BS 트리 > 탐색, 삽입, 삭제  BS변형 > Splay, AVL, BB  멀티웨이 탐색 트리 ① > m원, B, B*, B+  멀티웨이 탐색 트리 ② > 2-3 트리, 2-3-4 트리, 레드 블랙 트리  마치며.

* 참조 서적에 초판이 1994년 이고 2020년 이후에도 개정판이 나온거 같은데 그걸로 봐도 되지 않을까 싶지만 제가 가지고 있던건 구판이다보니 이걸 기준으로
* 자체적으로 만들어둔 예제 코드는 가급적 JAVA(포인터 부재), C++(포인터 존재)별로 담는것이 목표이나 일부 생략하고 넘어 갈 수도 있습니다.
* C++은 C++11을 기준으로 잡고 있습니다.

 

1. 기본 용어 및 개념

1) 자료? 정보?

-> "행위의 객체 '무엇을'이라는것을 바로 '자료(data)라고 한다. 자료는 스스로를 조직(organization)'하는 경우가 많다. 개별 자료가 아닌 여러 개의 자료의 집합은 자기만의 독특한 구조를 자기고 있다." (p.28, C로 배우는 알고리즘, 1994)

-> "'자료'는 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)입니다. 일반적으로 자료는 기기를 통해 측정되거나 특정 행동을 통해 수집되죠. ...(중략)... '정보'는 어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호간의 관계(relationship)를 표현하는 내용이라고 할 수 있습니다." (p.3, 자료구조, 2023)

DIKW 피라미드(DIKW pyramid) [#출처]

-> "데이터는 숫자 또는 문자 등으로 측정되거나 표현된다. ...(중략)... 데이터에 의미를 부여하거나 데이터를 모아서 가공·정리하면 정보가 된다." (p.4, 빅데이터의이해와활용, 2022)

-> /* (토막글)datum이 모인것이 data이라는것이 원칙?원론?이라도 관용적으로는 단수처럼 쓰인다나 뭐라? [#참조] */

2) 추상화?

-> "추상화를 통해 말하는 사람의 의사를 간결하게 전달할 수 있게 되는것입니다. 자료의 추상화는 다양한 대상을 컴퓨터에서 저장하고 처리하기 위해 그 대상들의 의미와 구조에 대해서 공통의 특징만을 뽑아 정의한 것이라고 할 수 있습니다." (p.6, 자료구조, 2023)
-> "컴퓨터 과학에서 추상화(abstraction)는 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다." (위키백과 한국어판, 2023)

-> /* 사람으로 치면, 저 그룹은 (대체로) 무슨 이슈에 대해 처리가 느린편이다/최소 신장이 어떻다/무슨 자격증을 가지고 있다 등등. */


3) 자료구조? 알고리즘?

-> "알고리즘을 방법이라고 생각할 때 알고리즘은 행위적 측면을 부여받는다. 위의 예에서 보듯이 '무엇을 어떻게 하라'는 것이 문제 해결의 방법이라고 할 때 '어떻게 하라'는 행위적 측면이 바로 알고리즘이 된다.

...(중략)... 조직된 자료를 자료 구조(data structure)라고 하며 이 또한 컴퓨터 공학에서 매우 중요한 부분을 차지한다.

...(중략)... 노른자가 커진다면 흰자는 줄어야 하고, 노른자가 작아진다면 흰자가 커져야 하는것이다. 마찬가지로 자료 구조가 잘 조직화되어 복잡한 구조라면 알고리즘은 간단하게 할 수 있고, 자료구조가 단순한 구조이면 알고리즘은 복잡해지는 것이다." (p.28, C로 배우는 알고리즘, 1994)

-> "추상화를 통해 자료의 논리적 관계를 구조화한 것을 자료구조(data structure)라고 합니다. 자료의 추상화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있습니다.

...(중략)... 어떤 일을 컴퓨터에 시키기 위해 필요한 명령문을 알고리즘이라고 한다면, 알고리즘이 효율적으로 작동하기 위해서 필요한 다양한 자료의 논리적 구조나 관계를 '자료구조'라고 하는것입니다. 그리고 자료구조가 효율적으로 정의되지 못하면 알고리즘이 느리게 수행되거나 결과가 다르게 나올 수도 있습니다." (pp.6-7, 자료구조, 2023)


4) 추상 자료형(abstract data type, ADT)?

-> "추상 자료형은 자료의 복잡한 논리적 성격을 정의하는 형식으로 자료값의 집합과 연산 집합에 대한 정의로 이루어집니다. 또한 알고리즘의 기본 개념을 반용하여 정의됩니다. 정리하자면, 추상 자료형은 자료구조를 표현하는 가장 대표적인 방법입니다." (p.9, 자료구조, 2023)

-> "추상 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다. 예를 들어 전기 밥솥을 추상 자료형에 비유한다면 그 속에 들어가는 밥은 자료가 되고, 밥솥에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다. 추상 자료형에서는 이것들이 어떻게 구성되는지 관심이 없고, 몇 와트의 전기를 소모하는지에 대해서도 관심이 없다." (위키백과 한국어판, 2023)

-> /* 처리할 자료(들)에 대해서 수학적인 수도 코드같은게 포함되었다 쯤? */

 

5) 알고리즘의 조건과 성능 측정(performance measurement)

출력	알고리즘 수행 한 후에 최소 하나 이상의 결과를 생성.
유효성	명령어를 누가 실행하건 똑같은 결과.
입력	명제가 될 수 있는 문장을 입력하는것처럼 추상적이지 않은 입력값.
명확성	누가 읽어도 같은 의미로 이해/해석해서 동일한 동작을 수행 가능.
유한성	종료 조건이 있어야 한다. /* 특수한 경우나 목적이 아니면 이상한 루프문 돌려서 CPU 점유 100%찍어 버리지 말고...*/

-> 성능측정: 실행하고 처리되는데 걸리는 최저/평균/최악의 실행시간을 말한다.

-> /* 수박을 통채로 자르는데 짧은 과도를 쓰면 불편하거나 도무지 처리가 안 되고 계란후라이 1인분을 하는데 명절에 전부칠때나 쓰는 전기 후라이팬을 쓰면, 그거 누가 다 뒷처리 하라고? 범용성이 좋아서 만능에 가까운(!) 알고리즘은 있을지언정, 어디에나 만능인 알고리즘이 있다고 주장하는 사람이 있다면 그 사람은... 약을 파는것이 아닐지로 의혹. */

2. 배열

 

1) 개념 및 정의

-> "인덱스와 원소값(<index, value>)의 쌍으로 구성된 집합 ...(중략)... 배열의 각 원소의 물리적 위치(메모리 주소)의 순서가 배열의 논리적인 순서(추상회된 인덱스의 순서)와 일치합니다. 따라서 배열의 첫 번째 원소가 위치하는 메모리 주소를 알면 인덱스를 이용하여 임의의 배열 원소의 주소값을 계산할 수 있습니다. 배열의 인덱스 값을 이용해서 배열의 원소값에 직접 접근 할 수 있습니다." (p.21, 자료구조, 2023)

-> "C에서는 배열을 아주 단순한 구조로 정의하였다. '연속된 메모리 공간을 치자하는 같은 데이터형들의 집합'이 그 정의이다. 이 이상도 이하도 아니다." (p.96, C로 배우는 알고리즘, 1994)

-> /* C/C++에서도 배열의 index는 0-base이고, 주소값은 당연히 16진수. 배열에 할당된 주소 시작값+자료형*k이면 index=k의 주소값이 된다. */

 

 

2) 1차원 배열

[#출처, javatpoint]

-> /* 한줄 서기로 정렬된 데이터들 대기열. 번호표는 0번부터입니다. */

 

 

3) 2차원 배열

-> /* 액셀 혹은 층별로 호수가 하나 이상인 아파트 구조처럼 정렬. 1층의 3호실이면 1003호, 5층의 3호실이면 5003호처럼. 하지만 여기서도 숫자는 0부터 카운트 한다 */

-> "2차원 배열은 원소를 컴퓨터 메모리에 저장하는 순서에 따라 '열우선 순서 행렬'과 '행우선 순서 행렬'로 구분됩니다. 동일한 열에 있는 원소를 먼저 차례대로 컴퓨터 메모리에 저장하는 방법을 열우선 순서 저장 방식이라고 하고, 동일한 행에 있는 원소를 먼저 차례대로 컴퓨터 메모리에 저장하고 다음 행으로 이동하여 첫 번째 원소부터 차례대로 컴퓨터 메모리에 저장하는 방법을 행우선 순서 저장 방식이라고 합니다. 행우선 수선 다차원 배열이나 열우선 순서 다차원 배열은 프로그래밍 언어에 따라 결정됩니다. 코볼(COBOL), 파스칼(Pascal), C와 같은 프로그래밍 언어는 행우선 순서에 따라 저장되고, 포트란(FORTRAN)의 경우에는 열우선 순서를 이용합니다." (pp.34-35, 자료구조, 2023)

 

 

4) 희소 행렬(sparse matrix)

-> int[][]일 경우 배열 원소가 0인 경우가 대다수인 행렬을 일컫는다.(초기값이 0이라는 전제하에)

-> /* 화면을 꽉 채운 액셀 테이블이 있지만, 경우에 따라서는 입력되지 않거나 0처럼 아직 기본값인 많으면 압축처럼 메모리를 절약할 방법이 없을까 싶을때 관련된 방법이 이거다. 메모리 절약을 위한 압축같은 변환이다보니 연산시 과부하가 발생할 수 있는 단점 존재. */

5) 연산 예시코드

> [#웹컴파일러, C++]

#include <iostream>
#include <string>

using namespace std;

int main()
{
    const int SIZE_ARR = 5;


    cout << "연산1. 배열 생성 및 초기화"<< endl;
    int myArr1[SIZE_ARR] {2023, 9, 17, 11, 0};
    int myArr2[SIZE_ARR];
    for(int loopIdx=0; loopIdx<SIZE_ARR; loopIdx++)
    {//크기만 선언된 배열에 초기값 입력.
        myArr2[loopIdx] = 0;
    }

    cout << "==============================="<< endl;
    cout << "연산2. 배열값 검색 및 접근"<< endl;
    for(int loopIdx=0; loopIdx<SIZE_ARR; loopIdx++)
    {
        if(myArr1[loopIdx]==11){    cout << "11 위치는 index = " << to_string(loopIdx) << endl; }
    }
    cout << "myArr2[3] = " << to_string(myArr2[3]) << endl;


    cout << "==============================="<< endl;
    cout << "연산3. 배열값 변경"<< endl;
    for(int loopIdx=0; loopIdx<SIZE_ARR; loopIdx++)
    {
        myArr2[loopIdx] = myArr1[loopIdx] - 10;
        cout << "(myArr2)index="<< to_string(loopIdx) <<" --> " << to_string(myArr2[loopIdx]) << endl;
    }
    

    return 0;
}

> [#웹컴파일러, JAVA]

public class Main
{
   public static void main(String[] args)
   {
        final int SIZE_ARR = 5;
	    
	    
        System.out.println("연산1. 배열 생성 및 초기화");
        int[] myArr1={2023, 9, 17, 11, 0};
        int[] myArr2 = new int[SIZE_ARR];
        for(int loopIdx=0; loopIdx<SIZE_ARR; loopIdx++)
        {//크기만 선언된 배열에 초기값 입력.
            myArr2[loopIdx] = 0;
        }
    
        System.out.println("===============================");
        System.out.println("연산2. 배열값 검색 및 접근");
        for(int loopIdx=0; loopIdx<SIZE_ARR; loopIdx++)
        {
            if(myArr1[loopIdx]==11){    System.out.println("11 위치는 index = " + loopIdx); }
        }
        System.out.println("myArr2[3] = " + myArr2[3]);
    
    
        System.out.println("===============================");
        System.out.println("연산3. 배열값 변경");
        for(int loopIdx=0; loopIdx<SIZE_ARR; loopIdx++)
        {
            myArr2[loopIdx] = myArr1[loopIdx] - 10;
            System.out.println("(myArr2)index="+ loopIdx +" --> "+ myArr2[loopIdx]);
        }
   }
}

3. 스택

 

1) 개념 및 정의

[#출처, 지층과 층서]

-> 오래전에 퇴적된 지층일수록 맨 밑에 있고 지표면은 비교적 최근에 쌓인 흙이 있다. 스택에서도 먼저 입력된 값이 맨밑에 있고, 최근에 입력된 값일수록 꼭대기.

-> 깊은 땅속에 묻힌 화석을 발굴하려면 사람들이 딛고 서 있는 맨 위에 있는 지표면의 흙부터 퍼내야 합니다. 스택에서는 Top부분을 pop 연산 처리 한것에 해당

-> 땅을 파내며 발굴중 중간에 폭우와 태풍으로 대량의 흙탕물이 발굴하던 구덩이에 새로 고이네요? 스택에서는 push 연산 처리로 Top이 변경된것에 해당

-> 구덩이에 쌓이던 흙탕물이 아무리 새로 고여도 하늘에 닿을것처럼 쌓이진 않죠? 스택에도 메모리 자원은 한정된터라 스택 크기에도 한계.

 

 

2) 연산 예시코드

-> 배열 기반

-> /* 기왕하는거 call by ref방식을 우선으로. 최대한 눈이 헷갈리지 않게. 주석 적정선을 했지만 코드가 길어져서 그냥 외부링크. 코드가 유실되면... 그건 그때 가서 생각하는걸로 */

-> 입력 연산시 0이 아닌 양의 수만 입력하는걸로 가정.

*.cpp	*.java
> [#웹컴파일러, C++]	> [#웹컴파일러, JAVA]

 

3) 전위/후위 표기법

-> /* A+B를 처리시 (+ AB)로 읽으면 전위 표기법. (AB +)로 읽으면 후위 표기법. 초등학교 산수책에서부터 보는건 중위 표기법 */

-> "우리가 일반적으로 사용하는 수식 표현 방법인 중위 표기법과 달리 후위 표기법이 컴퓨터가 해석하기에는 훨씬 빠르고 간결한 표현법입니다. 그래서 후위 표기법이 컴퓨터에서는 훨씬 많이 사용됩니다." (p.53, 자료구조, 2023)

-> /* (후위 표기법)사칙연산 제대로 들어가게 되면 기존에 읽던것처럼 우선순위가 높은 사칙연산부터 묶어서 분리수거(?). */

 

(예시)	A + B * C - D / E          1 + 3 * 2 - 8 / 4
1단계	연산자 우선순위에 맞춰 괄호로 정리 ==>   A + (B * C) - (D / E)          1 + (3 * 2) - (8 / 4)
2단계	괄호내에서 분리수거(?) ==>   A + (BC *) - (DE /)          1 + (3 2 *) - (8 4 /) 연산자를 완전히 분리수거(?)될때까지 1단계와 2단계 방법을 반복.   +나 -는 비슷한 우선순위이므로 ==>   (A(BC *) +) - (DE /)          (1 (3 2 *) +) - (8 4 /) ==>   ((A(BC *) +)(DE /) -)         ((1 (3 2 *) +) (8 4 /) -)
3단계	더는 할 게 없다? 괄호를 전부 제거 ==>   ABC * +DE / -         1 3 2 *+ 8 4 /-
(계산하기)	이제 왼쪽 구간부터 처리를 해야 하는데 피연산자&연산자 경계면 찾아서 피연산자 2개에 연산자 하나에 대한 연산결과를 그 자리에 다시 놓으면 ==>   ABC * +DE / -        1 3 2 *+ 8 4 /- ==>   A⒜ +DE / -            1 6+ 8 4 /- ==>   ⒝DE / -                 7 8 4 /- ==>   ⒝⒞ -                     7 2 - ==>   최종결과!!              5

 

4. 큐

1) 개념 및 정의

[#출처, dineshonjava.com]

-> /* 스택이 쌓여있는 윗부분부터 걷어내는것과 달리 큐는 입력한 순서대로 출력이 되는 질서정연한 자료구조. 이를 놓고 업계에서는 선입 선출(First In First Out 혹은 Last In Last Out)이라 */

-> 큐내에서 먼저 출력이 될 입력값의 인덱스는 머리/front등으로 불리고, 마지막으로 출력이 될 인덱스를 꼬리/reat등으로 불린다.

 

 

2) 연산 예시코드

-> 배열 기반

-> 입력 연산시 0이 아닌 양의 수만 입력하는걸로 가정.

*.cpp	*.java
> [#웹컴파일러, C++]	> [#웹컴파일러, JAVA]

-> 삭제 연산을 하다보면 머리와 꼬리의 인덱스값이 일치하는 시점이 온다. 이리되면 큐는 더 이상 사용 불가다.

 

 

3) 응용 및 원형큐
-> 라운드 로빈 스케줄링(RR 스케줄링): "작업 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받습니다. 즉, 일정한 크기의 시간 할당량을 모든 작업에 주고, 그 시간 동안 작업이 완료되지 못하면 준비 큐의 맨 뒤에 다시 배치됩니다. 그리고 준비 큐에 있는 다음 작업에 CPU를 할당합니다." (pp.74-75, 자료구조, 2023)
-> 원형큐(Circular Queue): 배열 기반인 큐의 문제는 정해진 배열에서 순서대로 값을 다 빼다보면 순서 인덱스상 비어버린 앞 공간은 버려지는터라 이를 효율적으로 재활용키 위한 방법이 원형큐.

 머리와 꼬리의 index값을 별도로 관리하여

(headIndex+1)%(배열의 크기)

(tailIndex+1)%(배열의 크기) 로 계산하면 배열은 그대로 놓고 인덱스값을 통해 논리적으로 원형같은 순환구조가 됨.

기타. 참조자료

1) 서적

강태원, 정광식 저. 자료구조, 한국방송통신대학교출판문화원, 2023년.

이긍희, 함유근, 김용대, 이준환, 원중호 저. 빅데이터의이해와활용, 한국방송통신대학교출판문화원, 2022년.

이재규 저. C로 배우는 알고리즘, 세화, 1994년.

2) 웹페이지

한국어

DIKW pyramid, wikipedia.org (접속: 2023-09-02)

추상 자료형, 위키백과 한국어판 (접속: 2023-09-03)

추상화 (컴퓨터 과학), 위키백과 한국어판 (접속: 2023-09-02)


영어

C++ Arrays - javatpoint (접속: 2023-09-16)

기타. 변경이력

일자	변경이력
2023-08-20	초안 작업 시작.
2023-12-28	일반 공개. [#blogger] [#티스토리]