[자료구조]0X03배열

배열

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

1. 성질

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

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

임의의 위치에 원소를 추가/제거 구현

#include <iostream>
using namespace std;

void insert(int idx, int num, int arr[], int& len){
    for(int i=len-1; i>=idx; i--) {
        arr[i+1] = arr[i]; // 삽입 하려는 위치의 원소부터 끝까지 하나씩 뒤로 이동시킴
    }
     arr[idx] = num; // 해당 위치에 원소를 삽입 
    len++;
}

void erase(int idx, int arr[], int& len){
    for(int i=idx; i<len; i++) {
        arr[i] = arr[i+1]; // 삭제하려는 위치까지 뒤의 원소를 한 칸씩 앞으로 이동시킴
    }
    len--;
}

배열 tip 특정 원소로 채우기 (주로 0으로 초기화할때 사용)
1. 전역으로 선언하면 0으로 초기화
2. 1차원 배열
   int a[20];
   fill(a, a+20, 0)
3. 2차원 배열
   int b[20][20]
   for(int i=0; i<20; i++)
       fill(b[i], b[i]+20, 0);

2. STL vector

1. 배열과 달리 크기를 자유자재로 늘리거나 줄일 수 있음
2. vec2 = vec 연산은 deep copy로 vec2을 바꿔도 원본인 vec에 영향을 주지 않음

   주의
   for(int i=0; i<=v.size()-1; i++)와 같이 쓰지 않는다.
   v.size()는 unsigned int/unsigned long long을 반환하므로 v.size()가 0인 경우 overflow가 발생하여 무한루프에 빠짐

3. 연습문제

처음한 풀이

int freq[100]
int func2(int arr[], int N) {
	for(int i=0; i<N; i++) {
    	freq[arr[i]] = 1;
    }
    for(int i=0; i<101; i++) {
    	if(freq[i] == 1 & freq[100-i] == 1)
        	return 1;
     	return 0;
    }

시간 복잡도 N+101; O(N)

배운 풀이

int occur[101]
int func2(int arr[], int N) {
	for(int i=0; i<N; i++) {
    	if(occur[100-arr[i]]) 100-arr[i]가 이미 확인
        	return 1;
        occur[arr[i]]=1;
     }
    return 0;

시간 복잡도 N; O(N)
출처: https://blog.encrypted.gg/927