내일배움캠프 26일차 TIL - 자료구조 특강 정리

자료구조를 배우는 이유 - 같은 구조라도 성능차이가 발생하기 때문

컴퓨터 공학의 핵심

 

---

시간 복잡도

• 알고리즘의 동작에 필요한 연산이 데이터의 갯수에 따라 대략 어느정도인가?
• 주로 빅오 (big O) 표기법으로 나타냄
• $n^{2} +  2n + 1 $ 와 같은 경우, 최대차항만 남겨 O( $n^{2}$ ) 으로 표기한다, 최고차항의 상수도 무시할 수 있다.

시간 복잡도에 따라 걸리는 시간은 대략 이러한 그래프를 보입니다.

지수함수, 팩토리얼 함수 형태의 시간복잡도가 나타나는 연산은 되도록 피해야하며, 로그 - 선형 함수 이하의 연산이 가장 이상적입니다.

 

---

배열 Array

• 모든 자료구조의 기본과 같은 형태
• 크기를 정한만큼, 저장공간을 부여
• Length() 메서드의 경우, 배열의 크기를 반환하는 메서드
• 데이터 지역성
  • 배열 데이터 참조시, 주변의 데이터를 같이 가져옴 → 주변 배열 정보가 캐시에 같이 올라오기 때문에, 성능에 이점이 있음
• 2차원 배열등을 사용 가능

주요 메서드

int[] arr = { 1, 2, 3, 4, 5 };

//배열의 크기
int length = arr.Length;

정확히는 Length 프로퍼티를 통해 배열의 크기를 반환받을 수 있습니다.

이때, 배열에 얼마나 저장되었는가가 아닌, 배열의 크기를 반환한다는점을 유의해야 합니다.

※ C#에서는 배열 생성시 초기화를 하지 않을경우 Null 이 가능할경우 Null 값, 이외에는 기본값을 배열에 채움니다.

 

그 외

int[] arr = new int[5];

//배열을 전부 입력한 내용으로 채움
Array.Fill(arr, 1);

//배열에서 지정한 값을 찾아서 반환, 없으면 해당 타입의 기본값 반환
Array.Find(arr, 2);

//배열을 정렬
Array.Sort(arr);

//배열의 내용 뒤집기
Array.Reverse(arr);

int[] arr2 = new int[10];
//배열 내용 복사 (왼쪽 내용에서 3개를, 오른쪽에 복사) 
Array.Copy(arr, arr2, 3);

 

 

Array클래스를 통해 접근하는 메서드에 이러한 내용이 존재합니다.

 

---

리스트 List

• 1차원 배열에서 편의성을 추가 (인덱스 기반 접근을 O(1) 시간에 편하게 하기 위해사용)
• 동적으로 크기 재할당
• 내부적으로 배열으로 구현

 

주요 메서드

//정수형을 저장하는 리스트 선언
List<int> list = new List<int>();

//리스트의 마지막 인덱스에 추가
list.Add(0);
list.Add(1);
list.Add(2);
list.Add(1);
list.Add(2);
//현재 리스트 배열 [0, 1, 2, 1, 2]
//리스트 배열에 여유가 있을경우 시간복잡도 O(1)
//리스트 확장시, 새 배열을 만들고 옮기는 작업 필요, 시간복잡도 O(n)

//리스트에서 지정한 내용을 찾아 삭제, 인덱스 0부터 찾으며, 하나를 삭제시 종료
list.Remove(2);
//현재 리스트 배열 [0, 1, 1, 2]

//리스트에서 지정한 인덱스를 삭제
list.RemoveAt(3);
//현재 리스트 배열 [0, 1, 2]
//삭제메서드는 인덱스를 당기는 작업 실행, 시간복잡도 O(n)

//리스트에서 해당 내용이 있는지 확인
if(list.Contains(1))
{
    //모든 리스트를 검색, 시간복잡도 O(n)
}

//리스트에 저장된 내용의 갯수
int length = list.Count();

 

리스트의 .Count() 메서드는 리스트의 크기가 아닌, 리스트에 저장된 내용의 수를 반환합니다.

리스트에 저장 용량을 수동으로 제어하거나, 현재 리스트의 용량을 알고 싶을 경우 .Capacity 프로퍼티를 통해 가능합니다.

 

---

딕셔너리 Dictionary

• 대응관계에 있는 데이터를 관리하기 위해 사용
• 값을 통해 데이터 접근을 O(1) 시간에 하기 위해 사용

주요 메서드

Dictionary<int, string> member = new Dictionary<int, string>();

//딕셔너리에 데이터 추가, 매개변수는 (키 값, 저장할 값)
member.Add(0, "1번");
member.Add(1, "2번");

string name;
//딕셔너리에 저장된 키값을 통해 저장값 반환
member.TryGetValue(1, out name);

//딕셔너리에 해당 키 값의 존재 여부
if(member.ContainsKey(0))
{
    //입력한 키 삭제 (저장값도 같이 삭제)
    member.Remove(0);
}

 

그 외

• 키 값이 int 형이 아닐경우 해시코드로 만들어 int 값으로 변환한 뒤 주소로 사용
• 주소를 bucket 으로 나누어 저장
• bucket 에 담겨진 주소(엔트리) 가 많아지면, 버킷의 크기를 늘림(이때, 버킷의 내용을 모두 꺼낸뒤 다시 넣는 작업이 필요하기 때문에, 시간복잡도 O(n) 이 발생)
• 연결 리스트를 통해 구현됨
• 키값이 저장된 버킷을 바로 찾아가 엔트리를 꺼내기 때문에, 입력, 데이터 찾기 작업의 시간복잡도가 O(1)
• foreach 가 가능
  • 모든 엔트리를 호출하는 방식으로 동작

---

스택 Stack

• 가장 마지막에 들어온 데이터에 빠르게 접근하기 위해 사용 (선입 후출)
• 데이터를 넣고, 빼는 과정의 시간복잡도가 O(1) → 배열의 가장 마지막에만 접근하기 때문

주요 메서드

//스택 생성
Stack<int> stack = new Stack<int>();

//스택에 값 입력
stack.Push(1);
stack.Push(2);
stack.Push(3);
//현재 스택 값 [1, 2, 3]

//스택에서 값 호출(빼기)
int a = stack.Pop();
//현재 스택 값 [1, 2]

//스택의 마지막 값 확인
int b = stack.Peek();
//현재 스택 값 [1, 2]

//스택에 저장된 값 갯수
int length = stack.Count();

//스택이 하나라도 남아있으면 반복
while(stack.Any())
{

}

 

그 외

• 스택에 용량이 부족할경우, 리스트와 마찬가지로 스택의 크기를 늘림 (시간복잡도 발생 O(n))
• 구글 피처드 기능 가이드 중, Back 키 입력 대응을 위해 사용
  • 새로운 UI를 켤 때, UI정보를 스택에 저장, 뒤로가기를 누를경우 스택에 저장된 내용을 Pop 하여 비활성화
• 메멘토 패턴에 사용 (Undo 시스템)

---

큐 Queue

• queue 에서 ueue 는 묵음이라는 놀라운 사실
• 가장 오래된 데이터에 빠르게 접근하기 위해 사용 (선입선출)
• 데이터를 넣고, 빼는 과정의 시간복잡도가 O(1) → 배열의 가장 처음에만 접근하기 때문

메서드

//큐 생성
Queue<int> q = new Queue<int>();

//큐에 데이터 삽입
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
//현재 큐 값 [1, 2, 3]

//큐에서 데이터 사용
int a = q.Dequeue();
//현재 큐 값 [2, 3]

//큐에 현재 데이터 갯수 확인
int length = q.Count();

 

 

그외

• 대기열, 오브젝트 풀 등에 활용

 

---

Linq 

• 데이터를 쉽게 관리하기 위해 사용
• 시간복잡도 성능이 좋은것은 아님

//리스트 생성
list<int> list = new List<int>();
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);

//정렬
//오름차순
list.OrderBy(x => x);
//내림차순
list.OrderByDescending(x => x);

//만족하는 값 반환( 리스트 값 => 조건식)
//만족하는값이 없을경우, 기본값 반환
int a =list.FirstOrDefault(x => x > 2);
//같은 조건찾기지만, First는 조건에 만족하는값이 없을경우 에러 발생
int b = list.First(x => x > 5);

//리스트의 내용을 변환 (Where 과 조합하여, 특정값을 뽑아내는데도 사용됨)
List<int> list2 = list.Select(x => x * 2).ToList();
//list2 내용 [2, 4, 6, 8]

//리스트의 내용을 매개변수로, 모든 리스트내용에 대하여 메서드 호출
list.ForEach(x => Console.WriteLine(x));

//모든 리스트값 각각이 조건을 만족하는지 여부
if(list.TrueForAll(x => x > 0))
{
    //만족하지 않는 값이 들어올경우 즉시 종료(false 반환)
}

//조건이 하나라도 만족하는지 여부
if(list.Any(x => x < 3))
{
    //하나라도 발견되면 즉시 종료(true 반환)
}

//리스트에서 지정한 갯수만큼 앞에서 가져오기
int[] arr = list.Take(3).ToArray();

 

그 외

• IEnumerable 인터페이스를 상속받고 있어야 Linq 사용 가능
  • 배열, 리스트, 딕셔너리, 큐, 스택 모두 IEnumerable 을 상속받고 있기때문에, 크게 신경쓸 필요는 없음