배열 - C++ ( 문제 포함 )

[1] 배열 개념

배열

배열은 순서대로 원소들이 연속적인 형태로 구성되어 있는 구조이며, 여러 타입으로 지정되어 효율적으로 관리를 할 수 있습니다.

[1-1] 배열 선언

배열의 경우, 정수형 변수를 여러 개 선언해서 관리하기보다는 정수형 배열을 선언해서 관리하는 게 더욱 효율적입니다. 비교하는 예시를 아래와 같은 예시로 보도록 하겠습니다.

// ...
int main() {

    // 인트형 변수 5개 선언
    int a1 = 1;
    int a2 = 2;
    int a3 = 3;
    int a4 = 4;
    int a5 = 5;
    cout << a1 << endl;
    cout << a2 << endl;
    cout << a3 << endl;
    cout << a4 << endl;
    cout << a5 << endl;

    // 1차원 배열 선언, for 문을 이용해 간편하게 출력
    int arr[5] = {1, 2, 3, 4, 5};
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << endl;
    }

    // 2차원 배열 선언
    int arr2[3][3] = {{1,2,3},{1,2,3},{1,2,3}}
    for (int i = 0; i < 3; i++) {
        for (int j = 0; i < 3; j++) {
            cout << arr2[i][j];
        }
    }
}

[1-2] 배열과 차원

배열은 2차원 배열과 그 이상의 다차원 배열을 이용하기도 하지만 컴퓨터 메모리 구조는 1차원으로 이루어져 있기에 다차원 배열은 컴퓨터 메모리의 1차원 공간에 연속 할당되어 나타나게 됩니다. 아래의 코드 예시를 보도록 하겠습니다.

(1) 배열의 접근 및 제어

변수명 앞에 &를 붙이면 변수와 배열의 주소값을 하도록 하겠습니다. 아래의 예시의 출력 결과에 따라서, 배열을 저장하는 메모리 구조가 연속적이라고 확인할 수 있습니다.

// ...
int main() {
    // 배열 선언
    int arr[3] = {100, 200, 300};
    for (int i = 0; i < 3; i++) {
        cout << &arr[i] << endl;
    }
}

/*
    출력결과
    C++ test.cpp && ./a.out
    0x7ffcbd97515c
    0x7ffcbd975160
    0x7ffcbd975164
*/

📒 NOTE

- int의 크기는 4바이트 이므로 주소가 4 증가
- double은 8 바이트라서 주소가 8 증가
- char 는 1 바이트이므로 1 증가

[2] 배열의 효율성

[2-1] 배열 연산의 시간 복잡도

배열은 모든 위치에 있는 데이터에 한번에 접근이 가능합니다. 따라서 배열에 있는 데이터에 접근하는 시간복잡도는 O(1)입니다.

📒 NOTE
배열 안에 있는 원하는 데이터를 찾아서 접근하는 것은 다른 의미입니다. 원하는 위치를 짚어서 접근한다는 게 O(1)이라는 의미입니다. 선형탐색은 O(n)입니다.

배열을 사용하게 있어서 여러 경우가 존재합니다. 배열 안에 데이터를 삽입(맨 뒤에 삽입하는 경우, 맨 앞에 삽입하는 경우, 중간에 데이터를 삽입하는 경우)할 때, 시간 복잡도를 확인하도록 하겠습니다.

(1) 맨 뒤에 삽입할 경우

배열이 arr[5] 일 때, arr[0] ~ arr[2] 까지만 데이터가 있는 경우에는 배열 arr[0] ~ arr[2]에 있는 데이터를 고려할 필요 없이 arr [3]에만 데이터를 삽입하면 되기에 시간 복잡도는 O(1)라고 할 수 있습니다.

(2) 맨 앞에 삽입할 경우

배열이 arr [5] 일 때, 마찬가지로 arr[0] ~ arr[2] 까지만 데이터가 있는 경우, 맨 앞에 데이터를 넣을 때는 기존에 있던 arr[0] ~ arr[2]에 있던 데이터를 고려해야 합니다. 왜냐하면 배열의 주소 시작값이 정해져 있기에 기존에 있던 데이터를 뒤로 한 칸씩 미뤄야 하기 때문입니다. 따라서 점근표기법에 의해서 시간복잡도는 O(N)이 됩니다.

(3) 중간에 삽입할 경우

중간에 데이터를 삽입할 경우, 중간 이후에 있는 데이터도 뒤로 미뤄야 하기에 시간 복잡도는 O(N)입니다.

📒 IMPORTANT
배열을 선택할 때 고려할 점

• 할당할 수 있는 메모리 크기를 고려해야 합니다. 대부분 문제에서 메모리가 정해져 있습니다. int 형은 4바이트이고 1kb는 1024바이트이고, 1MB는 1024KB입니다. 따라서 문제에서 메모리 제한이 128MB라고 주어졌을 때, 128MB = 128 * 1024 * 1024 / 4 면 약 3300만 개의 int 형 배열을 선언할 수 있습니다.
• 맨 앞, 중간에 데이터를 삽입할 때 시간 복잡도가 O(N)입니다. 문제에서 여러 번의 삽입이 요구될 때는 많은 데이터 삽입으로 시간초과가 될 수 있으니 다른 방법이나 시간 초과를 고려해야 합니다.

[3] 배열 문제

프로그래머스의 배열 문제를 풀어보도록 하겠습니다.

게임 캐리터를 4가지 명령어로 움직이려고 하고, 명령어는 위, 아래, 오른쪽, 왼쪽으로 이동하고 처음 가본 길을 카운트하는게 목적입니다.

총 명령어의 dirs 길이가 500개 정도 된다고 합니다. dirs 길이만큼 좌표를 바꿔서 visited 배열을 이용해서 처음 간 곳인지 아니면 방문했던 곳인지 확인하도록 합니다. 핵심은 가고자 하는 길이 처음 갔던 길이면 도착지에서 출발지로 다시 향하면 갔던 길로 확인하는 것이 핵심이라고 할 수 있습니다.

문제 링크

• https://school.programmers.co.kr/learn/courses/30/lessons/49994?language=cpp

프로그래머스

 

#include <iostream>

using namespace std;

bool visited[11][11][4] = {};

int dy[] = {1, 0, -1, 0};
int dx[] = {0, -1, 0, 1};

int intDir(char c) {
  // u d l r
  if (c == 'U') {
    return 0;
  } else if (c == 'D') {
    return 2;
  }
  else if (c == 'L') {
    return 1;
  }
  else if (c == 'R') {
    return 3;
  }
}


int solution(string dirs) {   
// input value;

  int startPoint[2] = {5, 5};
  int cnt = 0;

  for (char c : dirs) {
    int dir = intDir(c);
    int nx = startPoint[0] + dx[dir];
    int ny = startPoint[1] + dy[dir];

    if (nx < 0 || ny < 0 || nx > 10 || ny > 10) continue;

    if (!visited[startPoint[0]][startPoint[1]][dir]) { 
      visited[startPoint[0]][startPoint[1]][dir] = true;
      visited[nx][ny][(dir + 2) % 4] = true;
      cnt++;
    }
    startPoint[0] = nx;
    startPoint[1] = ny;
  }

  return cnt;
}

📒 NOTE
시간 복잡도는 dirs 길이만큼 움직이므로 O(N)이라고 할 수 있겠습니다.

[4] 참고문헌

• 박경록, 코딩 테스트 합격자 되기 C++편
• 박경록 저자님의 스터디에 참가하여 정리하며 작성한 글입니다.