코딩 테스트를 위한 자료 구조와 알고리즘 with C++ C-style 배열의 문제점 메모리 할당, 해제를 수동으로 처리해야 한다. 배열 범위 밖의 원소를 참조하는 것을 검사하지 못한다. 깊은 복사를 제공하지 않는다. std::array 메모리를 자동으로 할당하고 해제한다. array.at(int index) 함수를 이용해 범위 밖 원소 참조에 대한 예외 처리가 가능하다. 배열의 크기가 같은 경우 깊은 복사, 깊은 비교를 지원한다. #include #include using namespace std; template void print(const array& arr) { for (T e : arr) cout

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 노드란? typedef struct { // 데이터 int data; // 다음 노드의 포인터 Node *next; } Node; 연결 리스트의 구조 노드의 링크로 구성된다. 각 노드는 다른 메모리 Chunk에 저장된다. 시작 노드를 Head, 마지막 노드를 Tail이라고 한다. Tail의 next 포인터는 NULL을 가리켜 끝임을 표시한다. 연결 리스트의 성능 원소 접근은 Head에서 시작하여 링크를 따라가야 하므로 O(n) 시간에 수행된다. 특정 원소를 알고 있을 때, 삭제 혹은 뒤에 원소를 추가하는 것은 O(1) 시간에 수행된다. 모든 노드가 다른 메모리 위치에 존재하므로 Cache locality (캐시 지역성)을 기대할 수 없다. 배열과 ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 배열의 메모리 구조 단일 메모리 Chunk에 저장된다. 각 원소는 Base Address로부터의 오프셋을 통해 접근한다. 배열의 성능 원소 접근은 상수 시간 O(1)에 수행된다. 정적, 동적 배열은 성능 면에서 동일하다. Cache locality (캐시 지역성)으로 인해 순차 접근에서 좋은 성능을 낸다. Cache locality란? 특정 원소에 접근할 때 주변 원소들을 함께 가져와 접근 속도가 빨라지는 속성 배열을 사용해야 할 때 원소의 개수가 변하지 않는 경우(혹은 최대 개수가 정해진 경우) 순차 접근이 많은 경우 원소의 삽입 삭제가 적은 경우 주간 청소 당번 목록 최대 100명의 회원 목록 정적 배열 int arr[10]; Stack에 할당..