저급 언어와 고급 언어란?

• 프로그래밍 언어는 저급 언어와 고급 언어로 나뉘어져 있습니다.

저급 언어( Low-level programming language )

• 0과 1 또는 어셈블리어를 저급 언어( Low-level programming language )라고 합니다.

고급 언어( High-level programming language )

• C/C++, C#, Java, Python, JavaScript, Ruby 등과 같이 사람의 언어와 가까운 언어를 고급 언어( High-level programming language )라고 합니다.

저급 언어와 고급 언어와의 관계

• 컴퓨터는 0과 1만 이해할 수 있습니다. 하지만, 대부분의 개발자들은 0과1이 아닌 C/C++, C#, Java, Python, JavaScript, Ruby 등의 고급 언어로 개발을 합니다.
  
  그렇기 때문에 고급 언어들은 컴파일 또는 인터프리트를 통해서 저급 언어로 변환하여 컴퓨터에게 작성한 로직을 수행하도록 명령합니다.

컴파일 언어( Compiled language )란?

• 컴파일 언어는 컴파일러에 의해 소스 코드 전체가 저급 언어로 변환되어 실행되는 고급 언어이며 대표적으로 C/C++ 이 있습니다.
  
  컴파일 언어로 작성된 소스 코드를 저급 언어로 변환하는 과정을 컴파일( Compile )이라고 합니다.
  
  컴파일 언어는 컴파일 과정에서 개발자가 작성한 소스 코드 전체를 훑어보며 소스 코드에 문법적인 오류는 없는지 확인하며 문법적으로 하나라도 오류가 발견되면은 컴파일에 실패하게 됩니다.

컴파일 방식

전처리

• 전처리 단계는 매크로 언어들을 치환하는 단계입니다.

컴파일러

• 고급 언어를 저급 언어인 어셈블리어로 번역됩니다.

어셈블러

• 어셈블리어를 컴퓨터가 이해할 수 있는 0과 1로 구성된 바이너리 코드로 번역됩니다.

링커

• 바이너리 코드로 번역된 각각의 목적 파일들을 링킹 과정으로 거쳐서 하나의 실행 파일로 만듭니다.

인터프리터 언어

• 인터프리터 언어는 인터프리터에 의해 소스 코드가 한 줄씩 저급 언어로 번역되어 실행되는 언어를 말합니다.
  
  소스 코드를 한 줄씩 번역하여 실행하기 때문에 컴파일 언어처럼 소스 코드 전체를 저급 언어로 변환하는 시간을 기다릴 필요가 없습니다.
  
  한 줄씩 인터프리터에 의해서 저급 언어로 번역되어 실행되기 때문에 소스 코드에 문제가 있더라도 문제가 있는 소스 코드 라인을 만나기 전까지는 정상적으로 실행됩니다.

컴파일 언어 vs 인터프리터 언어

• 컴파일 언어는 컴파일 과정을 거쳐서 소스 코드 전체를 저급 언어로 번역한 후 실행되기 때문에 인터프리터 언어보다 실행 속도는 빠릅니다. 하지만, 인터프리터 언어는 컴파일 과정을 기다릴 필요 없이 즉시 한 줄씩 번역하면서 실행할 수 있다는 장점이 있기 때문에 어떤 언어가 좋고 나쁘다고는 할 수 없습니다.
  
  C/C++ 처럼 확실한 컴파일 언어도 있지만 Python, JavaScript 등과 같은 언어들은 인터프리터 언어이면서 컴파일 언어의 속성을 보이기 때문에 명확하게 구분되지 않는 경우도 있습니다.

컴퓨터에서 문자열을 표현하는 방법

• 컴퓨터는 문자와 코드 포인트( code point )가 맵핑되어 있는 문자 집합을 통해서 0과 1을 문자로 변환하여 표현합니다.

문자열 인코딩, 디코딩이란?

문자 인코딩( character encoding )이란?

• 문자 집합을 참조하여 문자를 0과 1로 변환하는 것을 문자 인코딩이라고 합니다.

문자 디코딩( character decoding )이란?

• 문자 집합을 참조하여 0과 1로 이루어진 값을 문자로 변환하는 것을 문자 디코딩이라고 합니다.

문자열 인코딩 종류

• ASCII, ANSI, EUC-KR, UTF, SBCS, MBCS, WBCS 등이 있습니다.

Call by value와 Call by Reference의 차이

• 함수를 정의할 때 매개변수를 어떤 식으로 받고 사용하느냐의 따라서 Call by value와 Call by reference로 나뉩니다.

Call by value란?

• Call by value는 함수 매개변수의 형식을 값을 복사하는 형태로 정의한 것을 말합니다.

Call by value 예시

int Add(int num1, int num2)
{
    return num1 + num2;
}


int main()
{
    int num1 = 10;
    int num2 = 20;

    std::cout << Add(num1, num2);

    return 1;
}

• 위 코드는 Add() 함수를 호출할 때 int 데이터 타입의 num1, num2의 값 자체를 복사하여 함수를 호출하고 있습니다.

Call by reference란?

• Call by reference는 함수 매개변수의 형식을 주소 값을 복사하는 형태로 정의한 것을 말합니다.

• Call by reference는 매개변수의 주소 값을 받기 때문에 함수 내부에서 값을 수정하였을 때 해당 함수를 호출 했을 때 전달한 인자의 값 또한 수정됩니다.

Call by reference 예시

int IncrementNumber(int *pNum)
{
    return (*pNum)++;
}

int IncrementNumber(int &num)
{
    return num++;
}

int main()
{
    int num = 0;

    IncrementNumber(&num);

    IncrementNumber(num);

    std::cout << num;

    return 1;
}

• 위 코드는 IncrementNumber() 매개변수로 포인터 타입과 래퍼런스 타입을 받을 수 있는 형태로 오버로딩 되어있으며, 함수를 호출할 때 int 데이터 타입의 num의 주소값을 전달할하여 호출하고 있습니다.

Call by value vs Call by reference

• Call by value는 값을 복사하는 형태이기 때문에 데이터 타입의 따라서 복사하는 크기가 달라집니다. 하지만, Call by reference는 컴파일 환경이 32bit 또는 64bit냐의 따라서 4byte 혹은 8byte를 복사하기 때문에 매개변수 데이터 타입의 크기와 상관없이 복사 오버헤드가 고정적입니다.

Call by value를 사용해야 할 때

• 매개변수의 데이터 크기가 포인터 크기와 작거나 같고 함수 내부에서 값의 수정이 필요하지 않다면은 Call by value를 사용하는 것이 좋습니다.
  그 이유는 해당 함수를 호출한 사용자가 해당 함수가 인자 값을 수정하지 않는 다는 것을 확실히 알 수 있기 때문입니다.

Call by reference를 사용해야 할 때

• 매개변수의 데이터 크기가 포인터보다 크고 함수 내부에서 값을 수정해야 한다면은 Call by reference를 사용하는 것이 좋습니다.
  그 이유는 데이터 복사에 대한 오버헤드를 줄일 수 있고 함수 내부에서 매개변수의 값을 수정하여 외부에 영향을 줄 수 있기 때문입니다.

해싱 ( hashing ) 이란?

• 입력된 데이터를 복호화를 목적으로 하지 않으면서 고정된 길이로 데이터를 변조하는 것을 말하며, 이를 통해 얻어낸 값을 해시 값 이라고 합니다.

해시 값의 사용처

• DB에 패스워드를 해시하여 저장하거나 해시 테이블 자료구조 및 여러 알고리즘에서 사용됩니다.

해시 테이블 ( Hash Table )

• 위 사진에서 나오는 것처럼 입력된 key를 index로 사용할 수 있도록 해시하여 해시 테이블에 key, value를 저장합니다.

• 해시 테이블은 O(1) 의 검색 시간 복잡도를 보장하지만, 해시 충돌이 발생될 경우 그만큼 검색 시간 복잡도가 상승합니다.

해시 충돌 ( Hash Colision )

• 불규칙적인 길이의 입력 데이터를 해시할 경우 동일한 해시 값이 발생될 수 있는데, 동일한 해시 값이 나오는 경우를 해시 충돌 ( Hash Colision ) 이라고 합니다.

체이닝 ( Chaining ) 해시 충돌 해결 방법

• 해시 충돌이 발생될 것을 고려해서 버킷을 list 또는 레드-블랙 트리로 하여 데이터를 추가적으로 삽입할 수 있도록 할 수 있습니다. 하지만, 데이터가 중복으로 삽입되었기 때문에 key를 한 번 더 비교하는 작업이 추가적으로 수행되어야 합니다.

해시 테이블 만들기

#include <iostream>
#include <vector>
#include <map>

template <class T>
class CHashTable 
{
public:

    CHashTable(int len)
        :mLen(len)
    {
        mTable.resize(mLen);
    }

    ~CHashTable(){}

    CHashTable(const CHashTable&) = delete;
    CHashTable& operator=(const CHashTable&) = delete;

    void Insert(const std::string& key, T value) 
    {
        const int idx = getHashIndex(key);
        mTable[idx].insert(std::make_pair(key, value));
    }

    bool Erase(const std::string& key)
    {
        const int idx = getHashIndex(key);
        if (mTable[idx].erase(key) == 0) 
            return false;

        return true;
    }

    bool Find(const std::string& key, T** outValue)
    {
        int idx = getHashIndex(key);
        auto& tempSet = mTable[idx];
        
        auto iter = tempSet.find(key);
        if (iter == tempSet.end())
            return false;

        *outValue = const_cast<T*>(&(iter->second));

        return true;
    }

private:

    int getHashIndex(const std::string& key) 
    {
        int retval = 0;
        const int len = key.length();
        for (int i = 0; i < len; ++i) 
        {
            retval += static_cast<int>(key[i]);
        }
        return retval % mLen;
    }

    const int mLen;

    std::vector<std::map<std::string,T>> mTable;
};

int main()
{
    CHashTable<std::string> hash(10);

    hash.Insert("test1", "value1");
    hash.Insert("test2", "value2");
    hash.Insert("test3", "value3");
    hash.Insert("test4", "value4");
    hash.Insert("test5", "value5");
    hash.Insert("test6", "value6");
    hash.Insert("test7", "value7");
    hash.Insert("test8", "value8");
    hash.Insert("test9", "value9"); 
    hash.Insert("test10", "value10");

    std::string* p;

    if (hash.Find("test9", &p))
        std::cout << *p << std::endl;

    if (hash.Find("test10", &p))
        std::cout << *p << std::endl;

    if (hash.Erase("test9"))
        std::cout << "Erase Success\n";

    if (hash.Find("test9", &p) == false)
        std::cout << "Find Failed\n";

    if (hash.Find("test10", &p) == true)
        std::cout << *p;

    return 1;
}

• 해시 충돌이 발생될 경우 체이닝 방식을 이용하였으며 버킷은 O(logN) 의 검색 시간 복잡도를 가진 map을 사용했습니다.