자료구조의 기초2

int 100개의 배열이 있다고 했을때 우리가 원하는 값을 찾기 위해서는 최악의 경우 100개를 모두 확인해야만한다.

이를 빅오표기법으로 O(N)으로 표시한다.

 

쉽게 생각하면 최악의 경우를 () 괄호안에 넣어서 표시해주는 표기법이다.

트리 구조의 경우는 한 번의 탐색마다 탐색할 데이터의 수가 절반으로 감소하기 때문에 다음과 같이 표기한다.

 

다만 배열에서 내가 원하는 데이터가 몇번째 인덱스에 있는지 안다면 바로 찾아낼 수 있는데 이와 같은 경우 O(1)로 표기되며, 이를 활용한 것이 Hash Table이라는 자료구조다.

 

* Hash Table과 Direct Addressing Table

둘 다 비슷하지만 Hash Table은 Hash 함수를 사용하여 데이터를 찾아낸다.

예를 들어 "Apple"을 Key 값으로 넘기면 이 Apple을 숫자로 변환하고, 곱하고, 나누어 0~256 사이의 숫자가 나오게 하고 그 값을 인덱스로 하여 해당 인덱스의 데이터를 반환하는 것이다.

 

Direct Addressing Table은 따로 함수를 사용하지 않고 넘기는 Key 값이 인덱스 그 자체로 사용된다. 즉 Key 값이 정수형이여만 하는 것이다. 문자열을 넣고 싶다면 이 문자열을 정수형으로 변환하는 함수가 필요한데 이를 해시 함수라고 하며, 결국 해시 테이블로 바뀌게 되는 것이다.

 

int Bucket[256] = {};

char str[7] = "ABCDEF";

for(size_t i = 0; i < 6; i++)
{
  Bucket[str[i]]++;
}

// 1. 사용된 알파벳의 종류 확인.
for(size_t i = 0; i < 256; i++)
{
  if(Bucket[i] != 0)
  {
    std::cout << (char)i << std::endl;
  }
}

// 2. 사용된 알파벳의 종류와 사용 횟수 확인
for(size_t i = 0; i < 256; i++)
{
  if(Bucket[i] != 0)
  {
    std::cout << (char)i << " : " << Bucket[i] <<std::endl;
  }
}

 

단점 : 내가 저장할 데이터가 몇개인지 모르니 최대 크기로 메모리를 잡아야 한다.

즉 메모리를 더 쓰고 성능을 올리는 방식이다. 메모리를 덜 쓰려고 배열의 크기를 줄이면 줄일수록 전달받은 Key 값을 해당 범위 이내의 정수 값으로 변환해야하므로 코드가 길어지고, 성능이 저하된다.

 

위의 경우는 DAT 방식이고 hash 함수를 사용한 해시 테이블의 경우는 Key 값을 별도의 함수(해시 함수)를 통해 정수형 데이터로 변경하는 방법이 포함되어 있다.

 

이때 만약 중복된 인덱스 값이 나온다면 어떻게 할까?

 

1. Separate Chaining : 분리 연결법

리스트 배열로 만들어서 동일한 값이 나온 경우 해당 인덱스에 있는 리스트 자료구조에 추가하는 식으로 구현한다.

 

for(size_t i = 0; i < 256; ++i)
{
    if(Bucket[i] != 0)
    {
      for(size_t i = 0; i < Bucket[i]; ++i)
      {
        std::cout << (char)i;
      }
    }
}

 

또는 위와 같이 아스키 코드라는 전제하여 정렬되어 출력되도록 구현할 수도 있다.

 

패턴 찾기

char Array[10] = "BTABCQABC";
char Pattern[4] = "ABC";

bool IsPattern(int Index)
{
  for(size_t i = 0; i < 3; i++)
  {
    if(Pattern[i] != Array[Index + i])
       return false;
  }
  
  return true;
}


int main()
{
    int count = 0;
    
    for(size_t i = 0; i < 7; ++i)
    {
      if(IsPattern(i))
      count++;
    }
    
    std::cout << count << std::endl;
}

 

 

재귀함수

동일한 함수를 계속 재사용하는 함수

void function(int Value)
{
	if(Value >= 5)
    {
      return;
    }
    
	function(Value + 1);
}

 

위와 같이 함수내에서 자기 자신(함수)를 호출하는 형태를 말한다.

중요한것은 매번 호출되는 함수는 사실상 스택 메모리에 새롭게 생성되는 함수이므로, 앞전에 호출된 함수와 동일한 함수가 아니다. 함수는 같을지 모르나 실행 정보가 다르기 때문이다.

 

그렇기 때문에 매 함수가 실행될때 마다 새롭게 스택 메모리 영역에 함수의 실행 정보가 올라가며 설정해둔 스택 메모리 영역을 초과하는 순간 Stack Overflow가 발생한다.

 

재귀함수를 사용하려면 반드시 빠져나가는 구문을 작성해야 하며, Stack Overflow가 나지않도록 주의해야한다.

 

기타 기초 코테

 

1. 방향을 표현하기 위한 코딩

int Arr[3][3] = 
{
    1, 2, 3,
    4, 5, 6,
    7, 8, 9
};

int Direct[4][2] = 
{
  -1, 0,
  1, 0,
  0, -1,
  0, 1
  
};

int x = 1;
int y = 1;

for(size_t i = 0; i < 4; i++)
{
    int NewX = x + Direct[i][1];
    int NewY = y + Direct[1][0];
}

 

2. 2중 포인터

 

이중 포인터 변수 : 포인터의 주소를 저장하는 포인터 변수.

위와 같은 구조로 만들어지며, *PtrPtrA = A의 주소값이 나오며 **PtrPtrA = A의 값인 80이 나온다.

 

int A = 10;

int* PtrA = &A;

int** PtrPtrA = &PtrA;

 

3. 2중 for문에서 패턴 찾기

 

int map[5][5] = 
{
    1, 3, 4, 5, 1,
    2, 6, 8, 3, 1,
    4, 6, 8, 9, 0,
    3, 9, 8, 8, 5,
    1, 2, 3, 4, 5
}

int Pattern[2][2] = 
{
    1, 3,
    2, 6
}

bool IsPattern(int IndexY, int IndexX)
{
    for(size_t i = 0; i < 2; ++i)
    {
        for(size_t j = 0; j < 2; ++j)
        {
           if(map[IndexY + i][IndexX + j] != Pattern[IndexY][IndexX])
           return false;
        }
    }
    
    return true;
}

int main()
{
    for(size_t i = 0; i < 4; ++i)
    {
        for(size_t j = 0; j < 4; ++j)
        {
          if(IsPattern(i, j))
          {
            std::cout << "패턴 있음" << std::endl;
            break;
          }
        }
    }

    std::cout << "패턴 없음" << std::endl;
}