[C++ 코딩테스트 자료구조 알고리즘] 01-1 배열, 연결리스트(linked list), std::array

배열

• 정적 배열은 int arr[size]; 형태로 선언합니다.
• C에서 동적배열은 int* arr = (int*)malloc(size * sizeof(int)); 형태로 선언합니다.
• C++에서 동적 배열은 int* arr = new int[size]; 형태로 선언합니다.

정적 배열은 stack 메모리 영역에 할당된다. 그래서 함수를 벗어날 때 자동으로 해제 된다. 반면에 동적 배열은 힙heap 영역에 할당되며 사용자가 직접 해제하기 전까지 유지

배열은 캐시 지역성이 좋다. 옆에 있는 원소의 캐시도 함께 데려오기 때문에 나중에 연속된 원소에 매우 빠르게 접근할 수 있다.

연결리스트 (linked list)

연결된 자료구조는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장

이 경우 서로 다른 메모리 위치에 데이터가 저장된다.

ㅁㅁ→ㅁㅁ→ㅁㅁ→ㅁㅁ(data next)

이러한 형태로 구성된 자료 구조 → 연결 리스트 (linked list)

ㅁ안에 data 저장한 데이터가 들어가며 그 다음 ㅁ에는 다음 노드를 가리키는 포인터 next를 갖고 있다. 맨 마지막 노드에는 next가 아닌, null을 갖는다.

연결리스트에서 특정 원소에 접근하려면 리스트의 시작 부분인 헤드부분부터 시작하여 원하는 원소에 도착할 때까지 next 포인터를 따라 이동해야한다. i번째 원소면i번 이동해야함.

원소 접근 시간은노드 개수에 비례 → 시간 복잡도 O(n)

• 연결리스트는 포인터를 이용하여 원소의 삽입 또는 삭제를 매우 빠르게 할 수 있음
• 연결리스트에서 삽입, 삭제 할 때 새로운 것을 만들어서 next 포인터가 새로운 것을 가리키게 하거나 삭제에서는 연결되어 있지 않도록 수정하면 된다.
• 메모리에 연속적으로 원소가 저장되지 않기 때문에 캐시 지역성 X
• 배열과 연결리스트에서 모든 원소를 차례대로 방문 → 같은 시간 복잡도 하지만 연결리스트의 성능이 조금 더 떨어진다.

연속된 자료 구조 연결된 자료 구조

모든 데이터가 메모리에 연속적으로 저장	데이터는 노드에 저장, 노드는 메모리 곳곳에 흩어져 있다
임의 원소에 즉각적으로 접근	임의 원소에 접근하는 것은 선형 시간 복잡도, 느리다
데이터가 연속적으로 저장되어 있고 , 캐시 지역성 효과로 인해 모든 데이터를 순화하는 것이 매우 빠르다	캐시 지역성 효과가 없으므로 모든 데이터를 순화회하는 것이 느리다
데이터 저장을 위해 정화하게 데이터 크기 만큼의 메모리 사용	각 노드에서 포인터 저장을 위해 여분의 메모리 사용

파라미터 배열 연결리스트

임의 접근	O(1)	O(n)
맨 뒤에 원소 삽입	O(1)	O(1)
중간에 원소 삽입	O(n)	O(1)
캐시 지역성	있음	없음

배열과 연결리스트는 매우 범용적이며 많은 응용 프로그램에서 데이터를 저장하는 용도로 사용 중

→ 자료 구조의 구현은 버그가 없어야 하며, 최대한 효율적으로 동작해야한다.

C++에서는 std::array, std::vector, std::list 같은 다양한 자료 구조 클래스 제공

<C스타일 배열의 단점>

• 메모리 할당과 해제 수동으로 해제하지 못하면 메모리 릭이 발생할 수 있고 이 경우 해당 메모리 영역을 사용할 수 없다.
• [ ] 연산자에서 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못한다. 잘못 사용하면 세그멘테이션 결함 또는 메모리 손상으로 이어짐
• 배열을 중첩해서 사용할 경우, 문법이 너무 복잡해서 코드를 이해하기 어렵다.
• 깊은 복사가 기본으로 동작하지 않는다. 이러한 동작은 수동으로 구현해야한다.

→ C++에서는 std::array 제공

std::array

메모리를 자동으로 할당하고 해제한다. 원소의 타입과 배열 크기를 매개변수로 사용하는 클래스 템플릿이다.

예제 코드

std::array<int, 10> arr1; //크기가 10인 int 타입 배열 선언

arr1[0]=1; //첫 번째 원소를 1로 설정
std::cout<< "arr1 배열의 첫 번째 원소 : " << arr1[0] << std::endl;

std::array<int,4> arr2 = {1,2,3,4};
std::cout <<"arr2"의 모든 원소 :";

for (int i =0;i <arr.2.size() ; i++)
std::cout <<arr2[i] << "  ";
std::cout << std::endl;

//출력결과 arr1배열의 첫 번째 원소 : 1
// arr2의 모든 원소 : 1 2 3 4 

std::array는 C스타일 배열과 똑같은 방식으로 배열 원소에 접근할 수 있는 [] 연산자를 제공

배열 원소 인덱스를 지정할 경우 , 빠른 동작을 위해 전달된 인덱스 값이 배열의 크기보다 작은지 검사하지 않는다. 대신 at(index) 형식의 함수도 함께 제공 → 이 함수는 인자로 전달된 index의 값이 유효하지 않으면 std::out_of_range 예외를 발생시킨다.

또는 다른 이유로 인해 유효하지 않은 인덱스에 접근할 수 있는 상황이라면 예외처리 코드 생성가능

std::array 객체를 다른 함수에 전달하는 방식은 기본 데이터 타입을 전달하는 것과 유사

값 또는 참조로 전달 가능, const를 사용할 수도 있다. 참조, 역참조, 포인터 연산 ㅌ

다차원 배열을 전달하는 경우에도 가독성이 훨씬 좋다.

예제코드 (print()에 std::array 배열을 값으로 전달하는 예제 코드

void print(std::array<int,5> arr)
{
for(auto ele :arr)
std::cout<<ele<<",";
}

std::array<int, 5> arr = {1,2,3,4,5};
print(arr);

//출력결과 : 1,2,3,4,5,

→ 전달받을 배열 크기가 고정되어 있기 때문에 다른 크기의 배열 전달 X

다양한 크기의 객체에 대해 동작하는 범용적인 배열 출력 함수를 만들고 싶다면 print()를 함수 템플릿으로 선언하고, 배열 크기를 매개변수로 전달

tmeplate <size_t N>
void print(const std::array<int, N>&arr);

객체를 전달 시 자동으로 깊은 복사가 동작 이러한 동작을 피하고 싶을 시 const참조 또는 참조

반복자와 범위기반 for 문법을 이용하여 우너소에 차례대로 접근 가능하다.

예제코드

std::array<int, 5> arr = {1,2,3,4,5};
for (auto element :arr)
{
std:cout<<element<<" " ;
}

//출력결과 1 2 3 4 5

begin() → 가장 첫 번째 원소 위치 반환

end() → 가장 마지막 위치 반환

산술 연산을 통해 원소의 위치를 옮길 수 있다.

컨테이너 내부의 위치를 나타내는 데 필요한 모든 기능에 대해서도 반복자가 사용된다.

• 특정 위치에 원소 삽입, 원소 삭제 등

→ 소스 코드의 재사용성, 유지 보수, 가독성 측면에서 이점을 얻을 수 있다.

//범위 기반 반복문

for(auto it = arr.begin(); it != arr.end(); it++){
auto element = (*it);
std::cout<<element << ' ';
}

front () : 배열의 첫 번째 원소에 대한 참조를 반환

back () : 마지막 원소

data() : 배열 객체 내부에서 실제 데이터 메모리 버퍼를 가리키는 포인터를 반환

arr.front() //형식으로 사용

std::array는 깊은 비교를 위한 관계 연산자와 깊은 복사를 위한 복사 할당 연산자도 지원한다.

C스타일 배열에 대해서 관계 연산자 사용 시 포인터 주소 값 비교 → 얕은 비교 실용적 X