스탠다드 특강 4 - 자료구조

김정환·2024년 10월 23일

개발공부 특강

자료구조

데이터를 어떻게 접근하고 저장하느냐에 따라 효율성이 달라짐
같은 데이터라도 어떻게 접근할지에 대한 것 = 자료구조
CS (Computer Science) 지식에서 제일 핵심
이번 특강에서는 많이 쓰는 것에 집중한다

무조건 List만 쓰는지?

왜? 동적으로 편하게 쓰는 것이 마음이 편하다고 생각하는 경우가 많음
얼마나 느리겠느냐는 안일한 마음

단점

데이터가 많아질수록 느려짐.
참조가 많아질수록 심해진다. (이유는 아래에서)

시간 복잡도

알고리즘에 필요한 연산의 수가 데이터의 개수에 대해 대략 어느정도인지
예) 버블 정렬 -> O(n^2)
기술면접에서는 로직의 시간복잡도를 설명해야한다.

배열

왜 쓸까

같은 자료형의 데이터를 쭉 이어서 저장하고 싶어서
인덱스 기반으로 데이터를 저장하고 싶어서
=> 즉, 인덱스 기반 데이터 접근을 O(1) 시간하고 싶어서

문법

int[] arr = new int[10];// 사이즈를 정해놓는다.
int[] arr = {1,2,3,4};	// 값을 넣어 정해놓는다. 이때 사이즈는 4
int[] arr; 				// 첫 사용 때까지 사이즈를 보류

주요 메서드 / 프로퍼티

arr[index] : arr의 index번째 원소에 접근
arr.Length : arr의 크기 반환

데이터의 지역성

배열 계열을 쓰는 이유

메모리에서 데이터를 가져올 때 주변에 있는 데이터를 같이 가져오게 됨 (주변 데이터도 캐싱하는 것)
배열 계열(리스트 등)의 성능이 딕셔너리 계열보다 훨씬 좋은 이유 중 하나

2차원 배열

여러 차원으로 구성하여 복잡한 구조를 표현할 수 있다.
맵, 판, 인벤토리 등을 n차원 배열로 구현

문법

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

리스트

왜 쓸까

배열에서 편의기능이 많이 추가되었기 때문 (즉, 신경쓰기 싫어서)
-> 즉, 인덱스 기반 데이터 접근을 O(1) 시간에 편하게 하고 싶어서
쓰기 편하다 == 원래 내가 해야할 일을 다른 곳에서 해주고 있다는 것.
- 사용에 유의할 필요가 있음.

특징

배열은 고정 크기, 리스트는 동적으로 크기가 재할당됨.
- 0 > 4 > 8 > 16 ... 순으로 늘어남
- 이 부분에서 성능을 많이 사용.
내부적으로는 배열로 구현되어 있음.

주요 메서드

각 연산별 시간 복잡도를 잘 알아둬야 함.

Add(T)
- 공간이 넉넉하다면 O(1)
- 새로 할당한다면 O(n) : 크기를 늘리고 재할당하므로
Insert(T)
- 중간에 추가 O(n) : 삽입된 이후의 요소들은 한 칸씩 밀어냄
Remove(T), RemoveAt(index)
- 마지막 자리 제거 O(1) : 요소를 제거하고 다른 요소를 이동시킬 필요가 없어서
- 중간 자리를 제거 O(n) : 요소를 지우고 뒷 부분의 요소들을 한 칸씩 끌어당김
Contains(T), IndexOf(T)
- 리스트에서 검색은 요소를 순차적으로 찾음 O(n)
Count
- 내부의 size 값을 가져옴 O(1)
인덱스를 통한 접근 : O(1)

연결 리스트 Linked List

데이터 뒤에 다음 데이터의 주소값으로 넣어 연결된 리스트.

왜 쓸까

데이터의 길이가 매우 유동적이거나 중간에서 삭제가 많이 일어날 때
직접 사용할 일 많이 없음 <- 결국 데이터를 계속 찾아야 함, 캐시히트가 너무 낮음

딕셔너리 구현에 사용되어 언급

Single Linked

일방향으로 구현

Double Linked

헤드에 이전 값을 갖고 있어 양방향 구현이 가능

딕셔너리 Dictionary

왜 쓸까

검색 속도가 빠르다 :
데이터 값을 통해서 접근하고자 할 때 O(1) 시간에 하고 싶어서 (CS적 관점)
데이터 값이 다양한 타입일 때 활용하고 싶어서 (실용적 관점)
대응관계가 있는 데이터에서 사용

면접에서 자주 물어봄

쉬운 문제

사용해봤다면 주요 메서드에 대해 설명? Add, ContainsKey

어려운 문제

데이터를 찾는 연산의 시간복잡도? O(1)
딕셔너리에서 해싱을 통해 데이터를 찾는 과정을 설명해보시오
(드물지만) foreach가 되는 이유?
- 엔트리들의 경우 배열로 이루어져 있음 = 이를 통해서 순회할 수 있는 것.

주요 메서드

Count : O(1)
Add(TKey, TValue) :
- 입력받은 key와 value를 딕셔너리에 쌍을 지어 저장한다.
- 해시 함수를 사용하고 인덱스를 찾으므로 상수의 시간복잡도를 갖는다. O(1)
TryGetValue(TKey, out Tvalue) :
- 키가 딕셔너리에 존재하는지 확인하고, 키가 있으면 키에 대한 값을 반환
- 반환타입 : bool
- out 매개변수 : Tvalue
ContainsKey(TKey) :
- 단순하게 키가 딕셔너리에 존재하는지 반환
- 반환타입 : bool
Remove(TKey) :
- 매개변수로 받은 key와 연결된 value를 제거한다.
- 마찬가지로 해시 함수를 사용하고 인덱스를 찾으므로 시간복잡도는 O(1)이다.

TryGetValue vs ContainsKey

둘 다 딕셔너리에 키가 있는지 확인하는 용도로 쓸 수 있음.
둘의 차이점 - 탐색 속도 차이
- TryGetValue 속도 :
  딕셔너리 내부 해시 테이블에서 키를 찾고, 값을 검색하는 작업이 동시에 이루어짐.
  한 번의 연산으로 키의 존재 유무를 확인하고 값을 얻을 수 있는 것.
- ContainsKey 속도 :
  딕셔너리 내부 해시 테이블에서 키를 찾는 것에만 초점이 맞춰져있음.
  값이 필요한 경우 추가적 연산이 필요함.

내부 작동 구조

모든 자료형을 처리하는 방법 GetHashCode() 해시 함수 사용.

GetHashCode()

모든 종류의 데이터들을 고정된 길이(4바이트)의 고유한 숫자 (Hash)로 표현하는 메서드.
이렇게 만들어진 해시 코드를 해시 테이블의 인덱스로 사용해서 해당 위치에 값을 저장하거나 검색함.

주소

숫자로 만들어야 메모리에 넣을 수 있어서 사용. => 주소로 만들어 주기 위함

예) 문자열을 숫자로 표현. 해시를 이용하므로 일방향 복호화 (비밀번호와 같이)
특정한 주소에 데이터를 넣을 때는 정수의 숫자를 사용해야하므로

해시 테이블

이렇게 해시로 변한 키값은 해시 테이블이라는 배열 구조에 저장됨.

각 배열 요소는 버킷(Bucket)이라 부름.
각 버킷은 키-값 쌍을 저장한다.
해시 함수는 키의 해시 코드를 해시 테이블의 크기로 나눈 나머지 값을 인덱스로 사용하여 버킷을 결정한다.
- 인덱스 = 키의 해시 코드 % 해시 테이블의 크기

충돌 Collision

해시 충돌 Hash Collision
서로 다른 두 개 이상의 키가 동일한 해시 값을 가지는 상황.

해시 함수는 임의의 크기의 입력을 고정된 크기의 해시 값으로 변환함.
입력 가능한 키의 수는 무한한데 해시 값의 범위는 제한되어 있기에 값이 중복되는 경우가 나올 수 밖에 없는 것.

딕셔너리도 사용함에 따라 인덱스 값이 겹치는 경우가 발생할 것임.

위 이유와 함께 해시 테이블의 크기가 정해져있는 값이라 발생.
- 예) 초기 해시 테이블의 크기는 3.
  이때 해시 테이블이 가질 수 있는 인덱스 : 0,1,2
  사용함에 따라서 해시 코드 % 3의 결과가 중복되는 경우는 당연히 발생함.
딕셔너리가 이 문제를 처리하는 방법 : Resize
테이블의 크기 * 2 보다 큰 가장 작은 소수로 크기 변경
- 예) 위의 예시에서 충돌 발생.
  1. 3 * 2 보다 큰 수들 중에서 가장 작은 소수를 다음 크기로 지정.
    즉, 7을 선택해서 다음 크기로 지정.
  2. 7의 크기를 가지는 배열을 만들고 기존 값들을 재할당한다.
  3. 추가하고자 했던 값을 새로 생긴 공간에 넣는다.

시간복잡도

평균 O(1) : 충돌이 발생하지 않으면 해시 함수로 해시 코드를 검색하는데서 상수 시간을 소모
최악 O(n) : 충돌이 발생했다면 해시 테이블의 크기를 늘리고 재할당하는데서 O(n) 만큼의 시간을 소모

특징

편리하다. 평균 O(1)
단, 해싱을 하는 과정에서 시간복잡도가 발생하므로 일반적인 O(1)보다는 느리고 O(n)보단 빠름.
메모리를 희생하여 속도를 얻은 느낌

스택 Stack

후입선출 구조. LIFO (Last In First Out)
마지막에 들어온 것이 먼저 나감.

왜 쓸까

가장 마지막으로 들어온 데이터에 대한 접근을 O(1) 시간하고 싶어서

특징

배열을 이용
리스트와 같은 재할당 로직이 사용

주요 메서드

Push : 요소를 스택의 top에 삽입 O(1)
Pop : 스택의 top에 있는 요소를 출력 O(1)
Peek : 스택의 top에 있는 요소에 접근 O(1)
Count : O(1)
검색 : 특정 값을 찾으려면 찾을 때까지 모두 확인 O(n)

활용 (UI 등)

구글 피처드 기능 가이드 대응 (Back Key): 모바일에서 뒤로가기 기능에 대한 대응
- 백키로 열린 UI들을 닫는 기능 구현에 사용
Undo 기능 구현에도 활용 가능 => 메멘토 패턴

큐 Queue

선입선출 구조. FIFO (First In First Out)
먼저 들어온 값이 먼저 나감.

왜 쓸까

가장 오래된 데이터에 접근을 O(1) 시간 하고 싶어서

그런 식으로 관리할 때, 데이터를 넣고 빼는 과정을 O(1)로 하고 싶을 때
대기열 구현 등

주요 메서드

Enqueue : 큐의 Back에 값을 삽입 O(1)
Dequeue : 큐의 Front값을 출력 O(1)
peek : 큐의 Front값에 접근 O(1)
검색 : 특정 값을 찾으려면 찾을 때까지 모두 확인 O(n)

활용

오브젝트 풀 구현
대기열 구현 등

Linq

Language Integrated Query
~~대략 직역하면 언어와 통합한 질의 방법 정도~~

왜 쓰지?

코드의 가독성을 높여줌.
단, 성능이 좋아지는 건 아님

OrderBy :

요소를 연산을 적용하여 정렬시킴 (오름차순)

var orderBy = num.OrderBy(x => x); // 기본 오름차순 
Console.WriteLine(string.Join(", ", orderBy)); // 1, 3, 5, 7, 9

var orderByReverse = num.OrderBy(x => -x); // 연산을 적용하여 정렬. 내림차순이 되도록 함
Console.WriteLine(string.Join(", ", orderByReverse)); // 9, 7, 5, 3, 1

FirstOrDefault :

조건에 맞는 요소 중 첫번째를 찾되 없으면 기본값을 반환

List<int> num = new List<int>() { 5, 3, 9, 1, 7 };

int firstNum = num.FirstOrDefault(n => n >= 9); // 9보다 큰 첫 번째 요소 찾기
Console.WriteLine(firstNum); // 9

firstNum = num.FirstOrDefault(n => n >= 1); // 1보다 큰 첫 번째 요소 찾기
Console.WriteLine(firstNum); // 5. 현재 순서상 1보다 가장 큰 요소인 5를 반환

firstNum = num.FirstOrDefault(n => n >= 10); // 10보다 큰 첫 번째 요소 찾기
Console.WriteLine(firstNum); // 0. 찾을 수 없으므로 0(기본값)을 반환한 것

Select :

맵핑, 요소에 원하는 연산을 수행하여 결과값을 반환

List<int> num = new List<int>() { 5, 3, 9, 1, 7 };

var select = num.Select(n => n * n);
Console.WriteLine(string.Join(", ", select)); // 25, 9, 81, 1, 49

select = num.Select(n => n % 3);
Console.WriteLine(string.Join(", ", select)); // 2, 0, 0, 1, 1

ForEach :

각 요소를 순회

List<int> num = new List<int>() { 5, 3, 9, 1, 7 };

num.ForEach(n => Console.WriteLine(n));
// 5
// 3
// 9
// 1
// 7

TrueForAll :

모든 요소에 대해 조건식이 일치하면 True 아니면 False

List<int> num = new List<int>() { 5, 3, 9, 1, 7 };

bool isOdd = num.TrueForAll(n => n % 2 == 1);
Console.WriteLine(isOdd); // True

bool isGreaterThen = num.TrueForAll(n => n >= 2);
Console.WriteLine(isGreaterThen); // False

Take

첫번째 요소부터 입력한 매개변수만큼 추출

List<int> num = new List<int>() { 5, 3, 9, 1, 7 };

var take = num.Take(2);
Console.WriteLine(string.Join(", ", take)); // 5, 3

take = num.Take(5);
Console.WriteLine(string.Join(", ", take)); // 5, 3, 9, 1, 7

take = num.Take(7); // 길이를 벗어나도 더 이상 추출하지 않음
Console.WriteLine(string.Join(", ", take)); // 5, 3, 9, 1, 7

사용 대상

List를 상속받은 IEnumable을 가진 구조여야함.
Collections들은 대체로 상속받고 있으므로 쓸 수 있음.

김정환

사파 개발자

이전 포스트

내일배움캠프 27일차 TIL : 팀프로젝트 제출, 제네릭 싱글턴

다음 포스트

스탠다드 특강 4 - 자료구조

자료구조

무조건 List만 쓰는지?

단점

시간 복잡도

배열

왜 쓸까

문법

주요 메서드 / 프로퍼티

데이터의 지역성

2차원 배열

문법

리스트

왜 쓸까

특징

주요 메서드

연결 리스트 Linked List

왜 쓸까

Single Linked

Double Linked

딕셔너리 Dictionary

왜 쓸까

면접에서 자주 물어봄

쉬운 문제

어려운 문제

주요 메서드

TryGetValue vs ContainsKey

내부 작동 구조

GetHashCode()

주소

해시 테이블

충돌 Collision

시간복잡도

특징

스택 Stack

왜 쓸까

특징

주요 메서드

활용 (UI 등)

큐 Queue

왜 쓸까

주요 메서드

활용

Linq

왜 쓰지?

OrderBy :

FirstOrDefault :

Select :

ForEach :

TrueForAll :

Take

사용 대상

내일배움캠프 27일차 TIL : 팀프로젝트 제출, 제네릭 싱글턴

내일배움캠프 29일차 TIL : 인터페이스

0개의 댓글