[Array] 배열기초

Array란? 데이터들이 연속적으로 이어져서 인덱스를 이용한 랜덤엑세스를 지원하는 자료구조입니다.

랜덤 엑세스는 인덱스를 통해 바로 데이터에 접근하게 해주기 때문에 O(1)의 시간 복잡도를 가집니다.
알고리즘 문제에서 Array는 이 자체만으로 문제로 만들어지기 보다는 백트래킹이나 다이나믹 프로그래밍과 조합되는 경우가 많습니다.
Array로만 만들어지는 문제들은 대부분 Sorting과 관련되어있다. 여기서 sorting은 O(nlogn)을 가져간다고 암기 해두기로 합시다.
Sorting은 Stable(스테이블) Sorting과 Unstable(언스테이블) Sorting이 있는데, 차이는 age와 name을 담은 자료구조를 정렬한다고 했을때 age가 정렬되고, name을 담은 데이터도 순서를 유지한다면 스테이블(merge), 그렇지 않다면 언스테이블한 정렬(heap,quick)이 됩니다. 나이(age) 데이터 정렬을 위해서 이름(name) 데이터에 대한 순서를 깨뜨리기 때문인데 이때 순서란, 배열을 삽입할때 인덱스로 정렬된 순서를 의미합니다.
ex) 나이가 50으로 같은, A,B,C,D,E가 0,1,2,3,4의 순서대로 배열에 삽입되었을때 Sorting 후에 이것이 유지되지 않는다면 언스테이블입니다.

배열에서 정렬이 중요한 이유는 정렬된 배열은 이진 탐색을 이용하면 시간탐색도가 O(logN)으로 탐색을 진행할 수 있기 때문입니다.

다차원 배열의 경우는 이후 다른 챕터에서 배울, 그래프를 통해 탐색 하기 때문에 그떄 설명합니다.

C#으로 스테이블 정렬을 구현해보겠습니다.

using System;

struct Employee
{
    public int age;
    public string name;

    public Employee(int age, string name)
    {
        this.age = age; this.name = name;
    }
}

class MainApp
{
    static void Main(string[] args)
    {
        List<Employee> employees = new List<Employee>();
        employees.Add(new Employee(200,"A"));
        employees.Add(new Employee(200,"B"));
        employees.Add(new Employee(200,"C"));
        employees.Add(new Employee(200,"D"));
        employees.Add(new Employee(200,"E"));

        for (int i = 1; i < 100; i++)
        {
            employees.Add(new Employee(i, "Z"));
        }

        //정렬 기준은 나이
        List<Employee> temp = employees.OrderBy(p => p.age).ToList();

        foreach (var item in employees)
        {
            Console.WriteLine($"{item.age}, {item.name}");
        }
    }
}

출력

1, Z
2, Z
3, Z
4, Z
5, Z
6, Z
7, Z
8, Z
9, Z
200, A
200, B
200, C
200, D
200, E