배열

• 메모리 상에 원소를 연속하게 배치한 자료구조. 시간복잡도 O(1)으로 k번째 원소의 위치를 바로 계산 (확인 및 변경 등) 할 수 있다.
• 타 자료구조와는 다르게 추가적으로 소모되는 메모리의 양이 거의 없다.
• 메모리 상에 데이터들이 붙어있으므로 Cache hit rate가 높다.
  • Cache hit rate란 캐시 적중률을 의미하며 명령이나 자료를 찾기 위해 캐시 메모리에 접근했을 때 자료가 존재하면 적중 Hit 되었다 하고 없다면 실패했다고 한다. 적중률은 적중횟수/총 접근횟수 이며 컴퓨터의 성능을 나타내는 척도로 사용된다.
• 메모리 상 연속한 구간을 잡아야 하므로 할당에 다소 제약이 존재한다.

 

기능

1. 원소를 확인/변경 : O(1)
2. 배열 끝에 원소를 추가 : O(1)
3. 배열 끝 원소를 제거 : O(1)
4. 임의의 위치에 원소를 추가 : O(N)
   1. 추가한 뒷자리의 원소들을 전부 한 칸씩 밀어야 하므로 O(N)이 필요하게 된다.
5. 임의의 위치의 원소를 제거 : O(N)

구현

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++;
}

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

 

 

연습문제

1. 백준 10808 : https://www.acmicpc.net/problem/10808

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.

var input = Console.ReadLine();
int[] arr = new int[26];
if (input != null)
    foreach (char c in input)
        arr[c - 'a']++;

Console.WriteLine(String.Join(' ', arr));

 

2. 주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 프로그램을 작성하라. arr의 각 수는 0 이상 100 이하이고 N은 1000 이하이다.

int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int[] arr = new int[101];
int answer = 0;
for (int i = 0; i < input.Length; i++)
{
    if (arr[100 - input[i]]) answer = 1;
    arr[input[i]] = 1;
}

Console.WriteLine(answer);