[알고리즘/개념/C++] 배열과 Vector

SHark·2023년 3월 2일

알고리즘

목록 보기

9/20

다양한 자료구조에 대한 지식은 알고리즘에 대한 지식만큼이나 중요하다. 자료구조는 컴퓨터에 데이터를 효율적으로 저장하고, 조회하고, 수정하는 등에 밀접한 연관이 있기 때문이다.
즉, 효율적인 로직은 "적절한 자료구조와 적절한 알고리즘을 사용하는 것"이므로, 두 가지 모두 알고있어야한다.

배열

배열은 아주 간단하고, 직관적인 자료구조형이다. 자료형을 일렬로 쭉 늘어뜨리는 자료구조형이다.
마치 사람들이, 한 줄로 쭉 서있는것처럼 말이다. 메모리 공간에도 연속적으로 할당이되기 때문에, 배열을 인덱스로 접근하면 , O(1)의 시간복잡도를 갖게된다.

왜 인덱스로 접근하면 O(1)의 시간복잡도를 갖게될까?
이유는 생각보다 간단한데, Array를 변수에 할당하면, array의 시작 메모리주소를 갖게된다. 배열은 시작주소부터 연속적으로 할당이 되어있기 때문에, 시작메모리 주소를 이용해서 배열로 접근하게된다. 예를들어, Arr[1]이라고하면, Arr[1]의 메모리주소에 직접적으로 접근하는게 아니라, Arr의 시작주소 +1로 접근한다.

연속적으로 메모리 공간에 존재하기 때문에, "수정"에 약간 불리한 구조를 갖고있다. N번째에 내가 원소를 넣고싶다면, 나머지 원소들을 수정해야한다. 그 과정이 평균적으로 N/2 걸리므로, 중간에 원소를 삽입,삭제하는 과정은 O(N)이 걸린다.

원소에 접근 : O(1)
맨 끝에 원소 추가 : O(1)
맨 끝 원소 삭제 : O(1)
중간에 원소를 삽입 , 삭제 : O(N)

Insert 연산 직접구현

배열에 중간에 원소를 직접 삽입하는 코드를 짜보자. 중간에 원소를 삽입하고, 나머지 원소들은 뒤로가는 과정을 구현하면 된다.

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

void Insert(int index,int num,int arr[],int &len){
	for(int i=len;i>index;i--){
    	arr[i] = arr[i-1];
    }
    arr[index] = num;
    len++;
	
}
void printArr(int arr[],int &len){
	for(int i=0;i<len;i++}{
		cout<<"arr[i]:"<<arr[i]<<'\n';
    }
}

void insert_test(){
	int arr[10] = {10,20,30};
    int len =3;
    insert(3,40,arr,len);
    printArr(arr,len)
    insert(1,50,arr,len);
}
int main(){
	insert_test();
    return 0;
}

물론, 임시변수를 둬서 저장하는 방식을 이용해도 되지만, 끝에서 당겨주고, 내가 원하는 자리에 원소를 넣는 코드가 훨씬 직관적으로 다가와서, 이렇게 짜보았다.

Delete 연산 직접구현

중간원소를 삭제하는 연산은 어떻게 구현할 수 있을까? 아래 그림을 코드로 나타내보자.

#include<bits/stdc++.h>
using namespace std;
void erase(int index,int arr[],int &len){
	len--;
	for(int i=index;i<len;i++){
    	arr[i] = arr[i+1]
    }
}
int main(){
	int arr[10] = {10,20,30}
    int len =3;
	erase(1,arr,3)
	return 0;
}

배열 사용시 주의점

배열은 Index Ouf of Range라는 에러가 흔히 발생한다. 즉, 양끝의 영역을 다룰 때는 항상 주의를 해주어야한다. 위의 배열을 삭제해주는 연산도, len--를 먼저해주지 않으면,index가 out of range가 될 수 있다. 예를들어 i =2 일때, arr[3]은 존재하지 않으므로, out of range가 발생할 수 있다.

배열 밀어버리기

그럼, 뭔가 이런 생각을 해볼 수 있지 않을까? 원소들을 오른쪽으로 한칸 씩이동하는 방법은 알겠는데, 맨 끝 친구가 맨 앞으로 다시 가는 배열을 만들어볼 수 있지 않을까?

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

void Shift_right(int arr[], int &len)
{
  int tmp = arr[len - 1];
  for (int i = len; i > 0; i--)
  {
    arr[i] = arr[i - 1];
  }
  arr[0] = tmp;
}

int main()
{
  int arr[] = {10,
               20,
               30};
  cout << arr[0] << arr[1] << arr[2] << '\n';
  int len = 3;
  Shift_right(arr, len);

  cout << arr[0] << arr[1] << arr[2] << '\n';
  return 0;
}