6/24 배열, 리스트

알고리즘 : 문제를 해결하기 위해 정해진 진행절차나 방법, 컴퓨터에서 알고리즘은 어떠한 행동을 하기 위해서 만들어진 프로그램 명령어의 집합

<알고리즘 조건>

1. 입력 : 알고리즘은 0개 이상의 입력을 가져야함
2. 출력 : 알고리즘은 최소 1개 이사의 결과를 가져야함
3. 명확성 : 수행 과정은 모호하지 않고 정확한 수단을 제공해야 함
4. 유한성 : 수행 과정은 무한하지 않고 유한한 작업 이후에 정지해야 함
5. 효과성 : 모든 과정은 명백하게 실행 가능해야 함

자료구조 : 프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미. 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미

<자료구조 형태>

선형 구조 : 자료 간 관계각 1대1인 구조 - 배열, 연결리스트, 스택, 큐 ,덱

비선형 구조 : 자료 간 관계가 1대 다 혹은 다 대 다인 구조 - 트리, 그래프

알고리즘 성능 : 상황에 따라 적합한 알고리즘을 선택할 수 있도록 하는 기준

<알고리즘 평가 기준>

컴퓨터에서 알고리즘과 자료구조의 평가는 시간과 공간 두 자원을 얼마나 소모하는지가 효율성의 중점. 일반적으로 시간을 위해 공간이 희생되는 경우가 많음

시간복잡도 : 알고리즘의 시간적 자원 소모량

공간복잡도 : 알고리즘의 공간적 자원 소모량

Big-O : 입력 크기 n이 증가할 때, 알고리즘의 실행 시간 또는 메모리 사용량이 얼마나 빠르게 증가하는지를 표현하는 표기법이다.

O(1) 1번 O(log N) 약 10번 O(N) 1,000번 O(N log N) 약 10,000번 O(N²) 1,000,000번

효율성 : O(1) < O(log N) < O(N) < O(N log N) < O(N²)

logN / NlogN : 데이터가 늘어날수록 문제 해결에 걸리는 시간/횟수의 상승폭이 줄어듦, 반 분할 씩이 가능해질 때 사용(ex 숫자 업다운 게임)

※ 단, 이진 탐색 / logN 탐색의 경우 정렬된 데이터에만 적용 가능

인덱스 : 배열은 요소들을 메모리에 연속적으로 배치하는 원리로 구현, 이를 이용해서 배열의 특정요소의 메모리 주소를 계산할 수 있음. i 번째 배열 요소 메모리주소 == 배열 시작 메모리 주소 + (i * 자료형의 크기)

배열의 효율

접근 : 원하는 데이터를 가져오는데 기능, datas[0] → O(1)

탐색 : 원하는 데이터가 자료구조에 있는지 확인하는 기능, datas.IndexOf(10) → O(n)

추가/삭제 : C#에서는 배열의 크기가 정해진 후, 원칙적으로 배열의 크기를 변하지 못하게 하도록 함.

추가/삭제가 가능한 리스트

List는 내부적으로 배열을 사용하지만, 요소가 추가되어 공간이 부족해지면 더 큰 배열을 새로 생성하고 기존 요소를 복사하여 크기를 동적으로 관리하는 자료구조이다.

현재 리스트의 Capacity 이상으로 Add가 되면 Capacity를 두 배로 늘린 배열을 새로 참조를 한다. 만일 사용해야할 리스트의 초기 크기가 큰 경우, List.Capacity의 크기를 미리 정의해줄 수 있음. 예시 - list.Capacity = 1000

// List<T>에서 Add 한 번은 평균적으로 O(1), 최악의 경우 O(N)이다.
// 이유: Capacity가 부족한 상태에서 Add를 하면 더 큰 내부 배열을 새로 만들고,
// 기존 요소들을 새 배열로 복사해야 하기 때문이다.

List<int> list = new List<int>();

for (int i = 0; i < 1000; i++)
    list.Add(i);

// 위 반복문 전체의 시간복잡도는 O(N)이다.
// Add가 대부분 O(1)이고, 확장 시 복사 비용이 발생하더라도
// 전체 누적 비용은 O(N)으로 볼 수 있다.

현재 저장된 요소 개수는 Count로 확인하고, 내부 배열의 확보된 공간은 Capacity로 확인한다.

List는 요소를 제거해 Count가 줄어들어도 내부 배열의 Capacity는 자동으로 줄어들지 않으며, 확보된 메모리를 줄이려면 TrimExcess()를 사용해야 한다.

추가, 삽입 : List.Add(값), List.Insert(인덱스, 값) -

삭제 : List.Remove(값) - 삭제, 반환형이 bool이므로 Remove에 성공하면 true, 실패하면 false

List.RemoveAt(인덱스) - RemoveAt은 반환형이 void

탐색 : List.IndexOf(값) - 반환형 int

크기 : List.Count

배열은 Length, 리스트는 Count인 이유

Array.Length → 배열이 생성될 때 정해진 전체 길이입니다. 한 번 생성하면 길이가 고정됩니다.

List.Count → 현재 List 안에 실제로 들어 있는 요소의 개수입니다.