[코딩테스트] 배열 / 연결리스트

배열

- 배열: 같은 타입의 원소들을 효율적으로 관리하기 위한 기본 자료형

- 연속된 메모리를 이용한 자료구조

- 탐색: O(1), 맨 뒤 삽입: O(1), 맨 앞/중간 삽입: O(N)

- 배열 선택시 고려할점: 할당 가능한 메모리 크기 확인/중간 데이터 삽입 횟수 확인

 

배열 다루기

#include <iostream>

int main(int argc, char** argv) {
    /** 배열 선언 및 초기화 
    * 배열 선언: type arr_name[size]; 
    * 배열 초기화(기본값은 0): type arr_name[size] = {val1, ...};
    */
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[5] = {1, 3, 4};         // 나머지는 0
    int arr3[] = {};                 // 모든 요소를 0으로 초기화
    int arr[4];                      // 배열내 원소는 쓰레기값
    
    /* 배열 접근 및 제어 */
    int int_arr[3] = {4, 6, 9};
    double double_arr[4] = {1.1, 5.2, 4.3, 9.5};
    char char_arr[3] = {'x', 'y', 'z'};
    std::cout << "---< int 배열 주소값 증가 확인 >---" << std:endl;    
    std::cout << &int_arr1[0] << std::endl;
    std::cout << &int_arr1[1] << std::endl;
    std::cout << "---< double 배열 주소값 증가 확인 >---" << std:endl;
    std::cout << &double_arr1[0] << std::endl;
    std::cout << &double_arr1[1] << std::endl;
    
    /* 배열 값 수정 */
    int int_arr[3] = {4, 6, 9};
    int_arr[0] = 10;
    std::cout << int_arr[0] << std::endl;
    
    /* 2차원 배열 */
    int arr[2][3] = {{1,2, 3}, {4, 5, 6}};
    std::cout << arr[2][3] << std::endl;
    
    
    return 0;
}

연결리스트

- 파편화된 메모리 사용(연속되지 않음)

- Node간의 연결에서 포인터 필요

 

연결리스트 다루기

#include <list>

int main(int argc, char** argv){
    /* 리스트 생성 및 초기화 */
    std::list<int> lst = {7, 5, 16, 8};
 
    /* 삽입 */
    lst.push_front(25);
    lst.push_back(13);
    lst.insert(lst.begin(), 42);

	/* 삭제 */
    lst.pop_front();
    lst.pop_back();
    
    /* 탐색 */
    auto it = std::find(l.begin(), l.end(), 16);
    if (it != l.end())
	    std::cout << *it << std::endl;
}

#include <forward_list>

문제 추천

- 두 개 뽑아서 더하기(Lv1)

- 모의고사(Lv1)

- 행렬의 곱셈(Lv2)

- 실패율(Lv1)

- 방문 길이(Lv2)

+)

- 배열의 평균값(Lv0)

- 배열 뒤집기(Lv0)

- n^2 배열 자르기(Lv2)

- 나누어 떨어지는 숫자 배열(Lv1)

---

문제 풀이