자료구조-배열

zzangbae·2023년 4월 15일
0

자료구조

목록 보기
1/1

이 글은 공부하면서 정리한 '학생'의 글입니다. 따라서, 틀린 부분이 있을 수 있음을 명시합니다.
혹시 틀린 부분이 보이시거나, 추가로 알려주실 수 있으신 분이 계시다면 언제든 환영이니 댓글 달아주세요:)

참고 : 바킹독블로그(https://blog.encrypted.gg/927)

이번 시간에는 자료구조 첫 번째, 배열에 대해서 알아보겠습니다.

배열이란?

: 연속된 메모리 주소에 데이터를 저장한 자료구조

배열의 종류

  • 정적 배열 : 크기가 정해져 있는 배열
  • 동적 배열(vector) : 크기가 정해져 있지 않은 배열

배열의 특징

  1. 데이터를 연속된 메모리 주소에 저장
  2. Cache hit rate가 높음 (따로 정리 예정)
  3. overhead가 거의 없음 - 추가적인 데이터 저장 필요X
  4. 특정 위치에 접근이 빠름 -> O(1)

배열 관련 시간 복잡도

  • 배열 마지막에 원소 추가 : O(1)
  • 배열 마지막의 원소 삭제 : O(1)
  • 배열 중간에 원소 추가 : O(N)
  • 배열 중간에 원소 삭제 : O(N)
    why?
    => 중간에 추가(insert)하면 뒤로 나머지 원소들을 밀어야함(for 랜덤 엑세스)
    => 중간에 삭제(erase)하면 뒤의 나머지 원소들을 당겨야함(for 랜덤 엑세스)

정적배열의 선언

int a[4];
int a[] = {1, 2, 3, 4};

정적 배열 함수 구현(중간에 원소삽입, 중간의 원소삭제)

// idx: 삽입할 공간, num: 넣을 원소, arr: 해당 배열, len: 배열의 길이
void insert(int idx, int num, int arr[], int len) {
	for(int i = len; i < idx; i--) {
    	arr[i] = arr[i - 1];
    }
    arr[idx] = arr[num];
    len--;
}

// idx: 원소를 지울 공간
void erase(int idx, int arr[]), int len) {
	len--;
    for(int i = idx; i < len; i++) {
    	arr[i] = arr[i + 1];
    }
}

배열 초기화 -> 3가지 방법

int a[30];
int b[30][30];

// 1. memset을 이용(#include<cstring>) -> 비추천
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);

// 2. for문을 이용
for(int i = 0; i < 30; i++) 
	a[i] = 0;
for(int i = 0; i < 30; i++) 
	for(int j = 0; j < 30; j++) 
    	b[i][j] = 0;

// 3. fill함수 이용(#include<algorithm>) -> 추천
fill(a, a+30, 0);
for(int i = 0; i < 30; i++) 
	fill(b[i], b[i]+30, 0);

동적배열의 선언

#include<iostream>
#include<vector>
vector<int> v1(3, 4);	// {4, 4, 4}
vector<int> v2(3);		// {0, 0, 0}
vector<int> v3 = {1, 2, 3, 4}	// {1, 2, 3, 4}
vector<int> v4;			// {}

동적배열 관련 메서드

v1.push_back(5);	// {4, 4, 4, 5}	시간복잡도: O(N)
v3.pop_back();		// {1, 2, 3}	시간복잡도: O(N)

cf) 전역에서 선언한 배열과 지역에서 선언한 배열은 다르다?

  • 지역에서 선언한 배열의 주소는 따로 정해져서 특이한(알고리즘 풀땐 쓰레기..)값이 나옴
#include<iostream>
using namespace std;

int a[4];

int main(){
	int b[4];
    for(int i = 0; i < 4; i++)
    	cout << a[i] << " ";	// 0 0 0 0 
    cout << "\n";
    for(int i = 0; i < 4; i++)
    	cout << b[i] << " ";	// -858993460 -858993460 -858993460 -858993460
    return 0;
}
profile
배우는 게 너무 즐거운 개발자

0개의 댓글