Back to Blog
알고리즘배열자료구조STL vector

0x03. 배열 - 순차 자료구조의 기본

배열의 정의와 성질, Insert/Erase 구현, STL vector 사용법을 정리한다.

0x03 배열

0x00 정의와 성질

지금까지 프로그래밍 언어의 관점에서 배열을 다뤘기 때문에 자료구조로써의 배열에 대해 익히는 필요가 있다.

정의

배열 : 메모리 상에 원소를 연속하게 배치한 자료구조

성질

  1. **O(1)**에 k번째 원소를 확인 / 변경 가능
  2. 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음
  3. Cache hit rate가 높음
  4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림

0x01 기능과 구현

배열 삽입

추가한 5번 뒤의 원소들을 전부 한 칸씩 밀어야해서 O(N)

마치 책상에 책이 연속해서 꽂혀있을 때 중간에 책을 넣기 위해서는 나머지 책들을 밀어야하는 것과 같다.

배열 삭제

마찬가지로 그 이후에 있는 모든 원소들을 한 칸씩 당겨와야해서 O(N)

임의의 위치에 있는 원소를 확인 / 변경 = O(1) 원소를 끝에 추가 = O(1) 마지막 원소 제거 = O(1) 임의의 위치에 원소를 추가 / 제거 = O(N)

구현

Insert 함수 : 한칸씩 미는 것을 앞부터가 아닌 뒤부터 사용하면 추가적인 메모리 사용

void insert(int idx, int num, int arr[], int& len){
    for(int i=len; i>idx; i--) {
        arr[i] = arr[i-1];
    }
    arr[idx] = num;
    len++;
}

Erase 함수 : 마찬가지로 왼쪽부터 밀기

void erase(int idx, int arr[], int& len){
    for(int i=idx; i<len-1; i++) {
        arr[i]= arr[i+1];
    }
    arr[len-1]= '\0';
    len--;
}

사용 팁 : 전체를 특정값으로 초기화

  1. memset - 실수 여지가 있어 비추천
  2. for
  3. fill 함수 < 가장 추천!!

0x02 STL vector

'=' operator 사용시 deep copy

push_front, pop_front 함수는 O(N)

vector 예시

1 - range-based for loop : 복사된 값이기 때문에 원본에는 영향 X, 다만 int& e : v1으로 하면 원본이 e에 들어감

3 - size() 함수는 unsigned int값, 즉 크기가 0이면 -1이 아닌 4294967295가 되어버린다 ( Overflow )

0x03 연습문제

BOJ 10808 알파벳 개수 ( 문자열을 입력받고 해당 문자열의 모든 알파벳의 개수를 출력 )

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int arr[26] = {0,};
    string s;

    cin >> s;
    for(int i=0; i<s.size(); i++) {
        int index= s[i] - 'a';
        arr[index]++;
    }

    for(int i : arr) cout << i << " ";
}

0x01강의 연습문제 ( 배열에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1, 없으면 0을 반환 )

O(N²)가 아닌 O(N)의 방법을 찾기

연습문제 설명

→ 등장여부를 체크하는 배열, 100-n의 여부확인 후 있으면 1을 반환, 없으면 n을 1로 변경하고 다음으로

연습문제 코드

→ 나는 생각해보았을 때 100-n의 값을 다른 배열에 저장하려고 하였으나 완전한 해답이 보이지 않았다 ,,

문제 풀이

이번에는 강의를 듣고난 후 총 6문제가 있었다. 문제 중에 풀었던 문제도 있었고 난이도도 어렵지 않게 해결하였다.

Note_ 3273번 : 두 수의 합, 이 문제는 연습문제와 동일한 유형의 문제였다. O(N²)으로 문제를 풀려고하니 시간초과가 뜨는 것을 확인 할 수 있었다. 다시 O(N)으로 해결하였다.

11328번 : Strfry, 이 문제는 정답 코드를 기억해두는 것이 좋을 것 같다. 두 개의 배열을 만들어 카운트하고 비교하는 것이 아니라 하나의 배열로 첫번째 문자열에는 ++, 두번째에는 --하여 마지막에 각 인덱스가 0인지만 확인하는 방법이다.

1919번 : 애너그램 만들기, 이 문제는 두 개의 배열을 만들어 알파벳을 카운트하고 마지막에 두 배열의 인덱스 값을 비교하여 다를 경우 차이값을 더하여 출력해주었다.

리뷰

이제 시작하는 과정이지만 강의를 듣고 구현하고 문제를 푸는 과정이 신기하고 재밌다.

배열에 대해서는 그냥 데이터들이 있는 막대기를 떠올렸었고 크게 어려움이 없었으니 가볍게 넘어가기 바빴다.

하지만 이렇게 다시 배우니 새롭고 몰랐던 것이 많았다는 생각이 많이 들었다.

특히 vector에 대해서는 단순히 문제를 풀기 시작해서 vector에 있는 많은 함수가 쉽고 편해서 구체적으로 공부도 하지 않은 상태에서 사용하기 바빴다.

이제 함수들의 구현과 시간복잡도 등을 생각하며 푸는 연습을 할 것이고 벌써 다음에 배울 내용이 기대된다.

다음은 0x04 연결 리스트로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편