What is Pointer ?

in Study on C/C++

포인터는 한마디로 해서, 주소를 저장하고 있는 바구니라고 생각 하면 된다, 주로 포인터 사이즈는 64 비트 기준으로 8 바이트이다. 일단 사용하는 방법은 TYPE* VAR_NAME 이런 식으로 사용하면 된다. 그러면 딱 코드를 봤을때 어떻게 생각하면 되냐? 뭔가 *(Asterisk) 이게 등장했다하면 포인터 = 주소라고 생각하면된다. 아래와 같이 number 라는 variable 은 Stack Memory 에 저장이 되어있는데, 이 Stack Memory 에 주소값을 ptr 로 받아주는 느낌이라고 생각하면 된다. 그렇다면 주소의 값은 어떻게 받냐? 라고 하냐면 & (ampersand) 이렇게 받으면된다. 다시말하자면 *ptr 이라는건 주소를 저장하는 형식의 바구니라는거라고 생각하면 된다.

int number = 1;
int *ptr = &number;

그렇다면 이 주소를 가지고 있는 바구니가지고 뭘할수 있을까 라고 생각이든다. 값을 가지고 오는 방법은 뭐가있을까? 일단 그러기전에 변수선언(variable declartion)을 한상태에서, 사용할때는 마치 포틀을 타고 순간이동을 한거나 마찬가지라고 생각을 하면된다. 왜 갑자기 포탈이라고 생각할수 있는데. 만약 메모리를 까보면 이런식으로 되어있다. 위의 코드를 봤을때 ptr 의 값을 &ptr 이런식으로 가게되면 주소값이 저장된걸 확인할수 있고, 그 값을 통해서 가면 number 의 주소로 향하고 있다는걸 확인 할수 있다. 또한 아래의 코드를 보자면, ptr 을 타고 들어가서 그 값은 주소값이니까, 그주소로 가면 2로 변경된걸 확인 할수 있다. 즉 포탈을 타고 가서 값을 변경하는것이다. 이걸 타입면에서 생각을 해보았을때 * 가 있다면 ptr 을 가면 int 가 있다고 생각해도 된다. 그런데, 타입 캐스팅이 가능하기 때문에, 메모리 오염을 시킬수 있다.

int value1 = *ptr;
*ptr = 2

// but let's think about this way
// what if type is differnet
__int64* ptr2 = (__int64*)&number;
*ptr = 0x0000AABBCCDDEEFF; // this wil contaminate the memory since it will allocate extra space.

아래와 같은 예제는 함수에 사용될때의 예시인데, main() 안에 stack memory 에 올라간 hp 를 SetHp로 인자를 넘겨줬을때, 값은 변화하지 않는다. 값을 변화시킬려면 stack memory 안에 있는 hp 의 주소를 던져줘서 hp value 를 바꿀수 있는 예제이다.

void SetHp(int *hp)
{
    *hp = 100;
}

int main()
{
    int hp = 1;
    SetHp(&hp) // give the address.
    return 0;
}

Pointer Operation

포인터 연산에는 아래와 같이 나누어진다.

  1. 주소 연산자 : ampersand(&)
  2. 산술 연산자
  3. 간접 연산자
  4. 간접 멤버 연산자

주소 연산자 같은 경우는 & 사용해서 주소값을 가지고 올때 사용한다. 즉 해당 변수 타입에 따라서 TYPE* 을 return 한다. 산술 연산자 같은 경우 + 와 - 를 사용한다. 다만 나눗셈과 곱셈 연산은 사용되지 않는다. + 나 - 를 했을때 그 타입의 사이즈를 따라서 그 주소 뒤에 가거나 앞으로 간다고 생각하면 된다. 즉 타입만큼의 크기만큼 이동하는거라고 생각하면 된다. 간접 연산자 같은경우는, 우리가 포인터를 생성할때 * 사용했었다. 포인터란 다시말해서, 포탈을 타고가라 라고 생각하면 됬었다 했었다. 그렇다면 간접 멤버 연산자는 뭘까? 정담은 이 친구 -> 이다. 아래의 예제 코드를 보면, player 의 객체의 주소를 playerPtr 향하게 했었다. 그말은 playerPtr 에는 player 의 주소가 담겨져 있다 라고 생각하면 된다. 그래서 player 의 멤버 변수인 _hp 와 _damage 를 바꾼다고 가정했을때 아래와 같이 할수 있다. 그럼 간접연산자를 어떻게 사용할수 있을까는 그 다음 코드 segment 로 사용해도 똑같다. 즉 * 와 . 을 합친게 -> 라고 생각하면 쉽다.

class Player()
{
public:
    int _hp;
    int _damage;
}

int main()
{
    int number = 1;
    int* ptr = &number;

    Player player;
    player._hp = 100;
    player._damage = 30;

    Player* playerPtr = &player;

    //pointer
    (*playerPtr)._hp = 200;
    (*playerPtr)._damage = 40;

    // indirect member op
    playerPtr->_hp = 300;
    playerPtr->_damage = 50;
    return 0;
}

예제 코드는 아래, resource 에 있다.

Reference

이걸 말하기전에 바로 코드로 넘어가보자. StatInfo 라는 struct 를 만들어서 pointer 값을 CreateMonster 함수 에서 parameter 로 받았을때, hp, attack, and defence 는 각각 4 바이트씩 차지하고 있을거다. 그래서 CreateMonster 함수에서 인자로 넘겨줄때는 주소값(address)를 넘겨주는걸 확인할수 있다. 하지만 만약 CreateMonster 함수의 paramater 를 StatInfo info 이런 식으로 signature 가 저장이 되어있다면 어떻게 될까? 라고 생각을 하자면, 원본 데이터 즉 main 에 있는 info 가 인자값으로 돌아와 그 매개의 복사값을 생성하면서 값을 채워넣는다. 즉 CreateMonster 안에 있는 함수의 info 와 main 에 있는 함수는 별개의 것이며, info 라는 매개변수를 새로 생성해서 복사를 하는 형태가 된다. 즉 원본데이터를 수정하기 위해선 주소값을 넘겨주고, 인자선언은 pointer 로 받으면 된다는 뜻이다. 근데 결과물은 똑같다. 하지만 performance 에서 봤을땐 복사값을 만들어서 붙여넣기 하는 형태이고, 주소값을 보내는 친구는 그냥 딱 야 이거해 하는 느낌인거다.

struct StatInfo()
{
    int hp;
    int attack;
    int defence;
};

void CreateMonster(StatInfo* info)
{
    info->hp = 100;
    info->attack = 9;
    info->defence = 5;
}

int main()
{
    StatInfo info;
    CreateMonster(&info);
    return 0;
}

reference 놈을 알아보자. reference 는 c 에 없고 c++ 에 있는 친구인데. 일단은 low level (assembly) 단에서보면 pointer 와 동일하게 작동한다. 일단 정의 부터 알아보자. reference 를 하고 싶다면, 아래와 같이 하면되는데. 이렇게 생까하면 된다 number 라는 바구니에 reference 라는 다른 이름을 지어줄께. 라고 생각하면 된다. 뭐야? reference 가 더쉽잖아. 왜 구지 포인터를 쓰면서 까지 저렇게 해 라고 되물을 수 있다. 근데 여기서 중요한건 pass_by_reference 와 pass_by_pointer 라고 생각하면 된다. 즉 함수에서 문법이 달라진다.

int number = 3;
int& reference = number;

아래의 코드와 같이 문법이 살짝 달라진다고 알수 있다. pass_by_reference 같은경우 pass_by_pointer 와 달리 info 값을 넣어준걸 확인 할수 있고, pass_by_pointer 는 info 의 주소값을 던져주는걸로 알수 있다. 즉 결론을 말하자면 pass_by_reference 와 pass_by_pointer 를 assembly 언어로 까보면 동작은 똑같다. 즉 performance 측면에서는 똑같다. 하지만 문법이 다른것으로 알수있으며 pass_by_reference 는 약간 야매로 pass_by_value 와 pass_by_pointer 의 중간지점이라고 생각하면 편할것같다.

struct StatInfo()
{
    int hp;
    int attack;
    int defence;
}

void PrintInfoByValue(StatInfo info)
{
  cout << "_________________" << endl;
  cout << info.hp << endl;
  cout << info.attack << endl;
  cout << info.defence << endl;
}

void PrintInfoByPtr(StatInfo* info)
{
  cout << "_________________" << endl;
  cout << info->hp << endl;
  cout << info->attack << endl;
  cout << info->defence << endl;
}

void PrintInfoByRef(StatInfo& info)
{
  cout << "_________________" << endl;
  cout << info.hp << endl;
  cout << info.attack << endl;
  cout << info.defence << endl;
}

int main()
{
    // ...
    StatInfo info;
    PrintInfoByValue(info);
    PrintInfoByPtr(&info);
    PrintInfoByRef(info);
    return 0;
}

Pointer vs Reference

위에서 봤듯이 low level 에서는 pointer 와 reference 가 동일하다는 걸 체크를 했었다. 동일하다는 의미는 Performance 적으로는 확실히 동일하고, 편리성은 reference 가 더 편할수 있다는 말이다. 근데 편하다는건 항상 단점을 가지고 있다. 포인터는 주소를 넘기니 확실하게 원본을 넘긴다는 힌트를 주는데 예를 들어서, & 사용해서 넘겨준다. 하지만 참존는 자연스럼게 모르고 지나칠수 있다는 말이다. 예시를 들자면, 위의 코드에서 만약 함수의 이름이 다 동일한 케이스일 경우 들수 있다.

// 어떤 여러개 선언


int main()
{
    PrintInfo(&info)
    PrintInfo(info) // --> 이럴 경우에는 실제 원본을 건들이는건지, 복사를 하는건지 명확하지 않다.
    return 0;
}

즉 실제 원본을 건들이는건지, 아니면 복사를 하는건지 모를수도 있고, 원본을 훼손할 가능성이 티가 안날수 있다는것도 맞다. 그러면 어떻게 이걸 막을수 있는 방법이 뭘까? 라고 고민할수 있다. (즉 절대 수정하지마라!) 라는걸 어떻게 표현할까. 아래의 코드 처럼 const 를 쓰게 되면 info 가 read-only 로 만들수 있다.

void PrintInfo(SztatInfo *){};
void PrintInfo(const StatInfo& info){};

그렇다면 여기서 또 질문할수 있는게, pointer 앞에 const keyword 를 사용하면 어떤의미를 가지고 있을까도 생각할수 있다. pointer 에서 const 를 쓸때 앞에다가 붙이느냐, 뒤에다가 붙이느냐의 의미는 서로 다르다.

void PrintInfo(const StatInfo* info){}
void PrintInfo(StatInfo)

만약 앞에 const 라는 keyword 가 붙었더라면, info 가 가르키고 있는 메모리에 저장되어있는[바구니] 값을 바꿀수 없는 형태이며, 반대로 뒤에 const 가 붙인다면, info 라는 주소(바구니의 내용물)을 못바꾸는 형식으로 된다. 아래의 예제 코드를 봐보자.

즉 다시말해서, 원격 바구닌를 못바꾸냐, 직접적인 바구니를 못바꾸냐의 차이이다. 아래의 코드를 보면 info 안에 들고 있는 struct 의 member variable? 을 access 할수 없게 되는거며, 뒤에 const 가 바뀔시에는 info 라는 값을 못바꾸는 것이라고 생각하면된다. 즉 안정성을 보안할수 있다는게 중요하다. 그럼 reference 와 pointer 를 비교했을때, nullptr 을 체크해서 사용을 한다면 가끔씩 유용할수 있다는것과 쉽게 바구니의 다른 네이밍을 넘겨주는것도 편리성에서는 좋다는 것이다.

struct StatInfo()
{
    int hp;
    int attack;
    int defence;
};

StatInfo globalInfo;
void ConstantBehind(StatInfo* const info)
{
    info = &globalInfo; // redline (error)
}

void ConstantFront(const StatInfo* info)
{
    info -> hp = 1000; // redline
}

StatInfo* FindMonster()
{
    // TODO: HEAP 영역에서 뭔가를 찾아봄
    // 찾았다
    // return monster
    // if not 
    return nullptr
}

int main()
{
    StatInfo info;
    return 0;
}

또 넘어가보자. 오케이. 알겠어 reference 와 pointer 의 차이점을 이해가간다고 생각을한다면, 사실 맨처음에 다뤄야할게 이제 나온다. 바로 initialization 을 어떻게 할것인가가 문제이다.

참조 타입은 바구니의 2번째의 이름이라고 생각하면 된다. 포인터같은경우는 가르키는 바구니를 말을 하면 되는거다(어떤 ~ 주소 라는 의미). 즉 참조 타입 같은 경우 참조하는 대상이 없으면 안된다. 하지만 포인터 같은경우 가르키는 대상이 실존하지 않을수도 있다. 즉 Null 로 정의 될수 있다는 것이다. Intuitively 생각하자면, 참조 타입 같은 경우, NULL 이나 nullptr 로 initialization 이 없다라고 생각하면된다.

The Lecturer told that it’s case-by-case to use reference or pointer. For example, google uses the pointer, and Unreal Engine prefer the reference.

결국엔 선호에 따라서 달라져있는데, nullptr 처럼 유용하게 쓸수 있다고 고려한다면, pointer 를 사용하고. 바뀌지 않고 읽는 용도로만 사용한다면 const ref& 이런식으로 하고. 그 외 일반적으로 ref (명시적으로) 호출할때 OUT 을 붙여준다. 아래의 코드를 봐보면 될것이다.

// Unreal Engine
#define OUT
void ChangeInfo(OUT Statinfo &info)
{
    info.hp = 1000;
}

int main()
{
    ChangeInfo(OUT info);
    return 0;
}

참고) 포인터로 사용하던것을 reference 로 사용하려면 어떻게 해야되냐. 아래의 코드를 보면된다. 여기에서 ptr 을 그냥 주게 되면 에러가뜨게 된다 그말은 가르키는 주소를 던져준다라고 생각하면 되는데, 우리는 info 의 값을 바꾸고 싶으니까, info 로 가라 라는건 * 연산자를 통해서 가면 된다. 그리고 만약 이걸 반대로 생각해서 우리가 reference 값을 pointer 로 넘기는 방법은, & 를 사용해서 주소값을 넘겨줘라 라고 생각하면 된다.

struct StatInfo()
{
    int hp;
    int attack;
    int defence;
}

void PrintInfoByPtr(StatInfo* info)
{
  cout << "_________________" << endl;
  cout << info->hp << endl;
  cout << info->attack << endl;
  cout << info->defence << endl;
}

void PrintInfoByRef(StatInfo& info)
{
  cout << "_________________" << endl;
  cout << info.hp << endl;
  cout << info.attack << endl;
  cout << info.defence << endl;
}

int main()
{
    StatInfo = info
    StatInfo* ptr = nullptr;
    ptr = &info;
    PrintInfoByRef(*ptr);

    StatInfo &ref = info;
    PrintInfoByPtr(&ref)
    return 0;
}

Basic Array

배열이란 결국 우리가 1 층 아파트를 생각하면될것이다. 1 층 건물에 누구를 할당시킬것인가가 라고 생각하면 편하다 아래의 코드를 보자. 아래의 코드를 보자면 사실 comment 로 다 작성을 했었다. Pointer 로 작성 했었을때, 일단 포인터는 주소값이고 array 라고 생각하면, 제일 앞에를 가르키고 있을것이다. 그래서 pointer operation 을 통해서 + 를 사용해서 그다음 데이터를 고칠수 있을것이다. 그리고 initialization 같은 경우는 코드를 보면 될것이다.

struct StatInfo
{
    int hp;
    int attack;
    int defence;
};

int main()
{
    const int mCount = 10; // mosnter count
    StatInfo monsters[monsterCount] // how many monster will be in the array

    // Access Array with pointer
    StatInfo* ptr = monsters; // [monster 0] [monster 1] [monster 2] ... [monster 9]
    // ptr is initially in monster 0 location
    ptr->hp = 100;
    ptr->attack = 10;
    ptr->defence = 10;

    // what if we do the operation + 1 to pointer, that is going to be the next one
    StatInfo* ptr1 = ptr + 1;
    ptr1->hp = 200;
    ptr1->attack = 20;
    ptr1->defence = 10;

    // then what if I want to get the reference data using pointer, then this is going to be the second one
    StatInfo& ref = *(ptr + 2);
    ref.hp = 300;
    ref.attack = 30;
    ref.defence = 30;

    // what if I want to go full round
    for (int i=0; i < mCount; i++)
    {
        monsters[i].hp = 100 * (i+1);
        monsters[i].attack = 10 * (i+1);
        monsters[i].defence = (i+1);
    }

    // Array Initialization
    int arr[5] = {}; // the size is going to be 5(0-4), and all variable set to 0
    int arr1[10] = {1, 2, 3, 4}; // [1][2][3][4][0][0].. rest are going to be 0
    int arr2[] = {1, 2, 3, 4, 5, 6}; // depending on the elements in array, it will set to the number of elements

    return 0;
}

MultiPointer

이를 다중 포인터라고 하는데 예를 들어서 이런 예제 코드를 봐보자. 아래의 코드를 실행 시켰을때, 이상하게도 type 은 정확하게 넣었는데, 값이 “Hi” 로 안바뀐걸로 보이는다. 왜그럴까? 라고 생각해보자. 일단 stack 안에 있는 msg 가 parameter 로 SetMessage 로 들어가는데, 이때 a 값이 변하지 않는 이유는 SetMessage 안에 있는 a 의 값은 변경이되고 사라진다는 것이다. 그래서 a 를 고치려면 *a 식으로 가야한다. 근데 막상 돌려보면 이건 const char 이다. 그래서 그 아래의 코드로 변경을 해야 된다. 어 ** 이렇게 한다고 어이가 없을수 밖에 없다.

그러면 이거에 대해서 설명을 하겠다. msg 도 pointer 이다. msg 는 Hello 라는 값을 pointing 하고 있다. 그렇다면 이값을 변경하려면 msg 의 주소값을 들고 와야한다. 그러면 다시 pointer 의 개념으로 돌아가는것이다. 그 의미는 pointer 를 다시사용해서, 즉 두번사용해서 msg 를 가르키는 놈이 필요하다는것이다. 여기서 dpointer 가 하는 역활이 msg 의 주소값을 가지고 있어서 두번 와프를 타라는 것이다. 왜냐하면 거기에 hello 라는 놈이 있을테니. 그래서 **dpointer 로 msg 의 주소값을 가져오게 되면, msg 가 hello 를 가르키고 있기때문에 가지고 올수 있는것이다. 그 이후에 parameter 로 SetMessageDiff 에 넘겨주게 된다면, a 라는 놈을 한번 타고 들어가서 값을 변경시키면 될것이다.


void SetMessage(const char *a)
{
    a = "Hi";
}

void SetMessageDiff(const char **a)
{
    *a = "Bye";
}

int main()
{
    const char* msg = "Hello";
    SetMessage(msg);

    const char **dpointer = &msg;

    SetMessageDiff(&msg);
    cout << msg << endl;
    return 0;
}

MultiDimension Array

Array section 에서 본것 같이 multi-Dimension Array 란 이제 층수가 달라진다는것이다. 예를 들어 코드를 봐보자

int main()
{
    for (int floor = 0; floor < 2; floor++) {
        for (int room = 0; room < 5; room++) {
            int num = apartment[floor][room];
        }
    }
    return 0;
}

이런식으로 배열이 되어있다면, unit number 은 5 개라는거고 층의 개수는 2개라고 생각하면 될것이다. 그래서 이렇게 배열을 indexing 할수 있는거다. 그렇다고 하면 pointer 로 어떻게 access 를 할수 있을까가 질문인것이다.

2 차원 배열과 다중포인터로 어떻게 사용할수 있을까? 라는 생각이든다. 이렇게 생긴 코드를 한번 보자. pp [ 주소1 ] –> 주소1[주소2] –> 주소2[] 이렇게 하면 될까? 라는 생각이든다. 하지만, 실제로 보면, *pp 만 해도 덩그러니 1 이라는 값이 있는걸 생각할수 있다. 즉 pp[ 주소1 ] 을 타고 들어갔더니 주소1[ value ] 가 있는것이다. 그래서 프로그램이 뻗어버린다. 즉 다중 포인터와 다중 배열은 완전 다른 타입이다.

int **pp = arr2;

그래서 이 코드를 보면 된다, 그러기전에 꼭 타입을 한번 확인해보자. 그러면 int(*)[2] 라고 확인할수 있다. 그러면 이걸 어떻게 해석하면 되냐. p2 로 타고 들어갔더니 int()[2] 2차원 배열이 있다고 생각하면 된다. 근데 이렇게 구지 할필요는 없을거다. 그냥 arr2[0][0] indexing 을 해도 충분하다.

int (*p2)[2] = arr2;
cout << (*p2)[0] << end;
cout << (*p2)[1] << endl;
cout << (*(p2 + 1))[0] << endl;
cout << (*(p2 + 1))[1] << endl;

Resoure

Source Code

Black Panther : Wakanda Forever

in Reviews on Movie

사실 그렇게 Marble 영화를 좋아한다고 하기에는 굉장히 논란거리가 많다고 생각한다. 나는 아이언맨 1, 2, 헐크, 토르1, 2 만 보았고 전체적인 스토리에대해서 전혀 모른다. 마블의 광팬이라면, 뭔가 내가 해리포터를 굉장한 팬처럼 생각하는것 처럼 그렇겠구나라는 생각이든다. 항상 마블하면 생각하는건 미국에 있었을때 였다. 뭔가 엔드게임을 보자는 친구들이 많아서, 나를 대신해서 티케팅을 해줘서 그냥 따라 갔던 기억이 난다. 그때는 뭔가 영어를 알아들어도, 무슨 스토리인지 감이 안와서 생각없이 보았던 영화였는데 하면서 봤던건데 기억나는 장면은 갑자기 모든 주인공이 나타나 싸우질 않나, 갑자기 캡틴 아메리카가 토르의 망치를 가지고 오면서 싸우는 장면이 띄어졌을때, 온 사람이 “WoW! YEAH! OMG!” 이런 반응에 뭐지? 한것도 기억이 난다. 그리고 마지막은 정말 슬펐던 장면, 아이언맨이 죽고 나서, 아이언맨의 딸에게 최애의 음식이 치즈버거 였다는 말까지 밖에 기억이 안났었다. 그게 나의 마지막 마블영화였던것 같다.

블랙팬서 1도 비행기 타면서 봤었는데 너무 지루하고, 무슨 이야기가 돌아가는지 몰라서 잤었던것 밖에 기억이 안났는데, 이걸 어찌보냐 이런생각 밖에 안들었었다. 그런데, 주인공이 죽었다라는 소식을 듣기는 들었었어서 마냥 완전 새로운 스토리겠지 하면서 봤었다. 스포를 싫어하는 사람들을 위해서 말을 하자면, 결론은 딱이거다. 새로운 블랙팬서가 나타났다. 그게 여동생이다라는 말을 할수 밖에 없는것 같다. 뭔가 영화를 보면서, 조금 음 뚱딴지 같다라는 생각이드는데, 나중에 나의 최애 캐릭터가 있었던거 같다. 의리와 재치가 넘치는 음바쿠! 음바쿠라는 캐릭터 설정이 진짜 재밌어 보였는데, 사실 내가 영어를 많이 않쓰다보니 영어 듣기 실력이 줄었겠지 하지만, 이 친구가 말하는건 웬지 너무 잘들리고, 뭔가 내 이미지와 맞는것 같아서 계속 그냥 들렸던것 같다.

하.. 딱히 영화리뷰라고 할것도 없다. 아무 생각없이 보기엔 정말 좋은 영화였다. 스토리 라인은 그냥 조금 그랬었던것 같았다.

You Make Your Own Boat

in Etcs on Logs

이제 BootCamp 를 다녀온지 한달이 지나갔다. 참 시간이라는게 빠르면 빠르고 붙잡고 싶어도 붙잡아지지 않는다. 군대에 나오고 나서, 되게 사람들의 말을 끊어버리는 이상한 습관이 하나 생긴것같다. 가끔씩은 나의 그런 모습이 참 보기 싫어졌다는 생각이든다. 왜 그럴까? 내가 군대 가기전에 그렇게 여유로운 삶을 누렸는데, 왜 이제는 다를까? 라는 생각도 많이 들게 된다. 뭔가 포옹력이 사라진것 같기도 하고, 내가 지금 아직도 한국 적응중인가도 많이 생각 하게 된다. 최근 들어서 그 트라우마라고 생각하는 4월과 5월이 생각난다. 하지만 그랬던 시절도 이제는 그립기 시작했다.

내 친구와 함께 토요일에 밥을 먹었다. 원래는 술도 한잔 하려고 했었는데, 점심으로 약속이 잡히자, 그럴 생각도 금쪽같이 사라졌다. 사실 이 친구와 알기 시작한건 2016년 부터 시작해서, 우리 둘이 인생극장 을 찍을정도로 같이 붙어있었고 너무 잘맞는 친구였다. 그 친구와 친해지기까지는 생각보다 오래걸렸었고, 술을 마시고 나서 “우리 힘내보자! 할수 있잖아!”라는 말을 외치면서 미국 집앞에서 소리 친적이 있다. 그때는 되게 민폐라고 생각했지만, 우리 서로 사정이 있었고 힘들었던 시기에 만난거라 그 무엇보다도 큰 힘이 되었었다. 하지만, 이렇게 당당했던 친구와 나의 모습은 없었고, 둘다 미국이 그립다는 이야기만 엄청했었다. 그 친구와 나의 인생의 절반은 다른 대륙에서 살아갔었고, 한국에 들어오고 싶지 않았던 우리는 우리가 내렸던 결론에 끝을 잘 맺치지 못했던것 같다. 물론 과거는 과거였고, 추억은 추억으로 남겨져간다. 하지만 그 과거에 지금의 우리를 만들었던 좋은 추억들은 쉽사리 사라져가진 않는다는건 분명하다. 늘 우리는 서로의 생일을 챙겨주고, 맛있는 밥도 같이해서 유학생 다웠던 삶을 살아갔었다. 항상 웃어서 행복했고, 나의 아파트 발코니에서 나무와 고속도로를 넘어서 담배피면서, 맥주 한캔 했던 그런 여유로움을 나름 즐겼다. 하지만, 미국의 삶도 호락호락 하진 않았다. 나 나름 영어를 잘한다고 생각하지만, 막상 발표나 친구들과 이야기할때는 흐름이 비슷하고, 백인들과 흑인들 사이에서 콕 파묻힌 느낌도 들때도 많았지만, 그렇게 다양한 인종들끼리 친구가 됬었고, 차별을 당한적은 있지만, 그때는 그런가보다 하면서 넘겨갔던게 많았고, 풀리지 않은 문제들은 정말 혼자서 끊임 없이 붙잡으려고 포기 하지 않았다. 그랬던 삶들은 점차 점차 사라져가며, 이제는 밖에 나가면, 음식집 앞에서 사람들의 소리들이 들린다.

물론 한국의 삶은 다른 형들과 사람들의 말로는, 바쁘게 살아가고, 포기하며 살아가고, 여유롭게 살아가지 못하고 있는것 같다. 되게 호락호락 하지 않는 반면에 나는 최대한 이 미국에서 받아온 여유로움이 아직은 남아있는것 같다. 나와 친구가 했던 말이 생각난다. “우리의 몸은 한국에 있는데, 정신은 미국에서 살고 있다고.” 이 말이 정말 정확하게 맞다. 나는 이제 한국 산지 반년이 지나간다. 처음에는 적응하느라, 일하느라, 전화만 했었던 가족들이 진짜로 나의 인생에 들어오고, 많이 힘들었던건 사실이다. 그리고 책상에는 아직도 “좋은 개발자나 연구자가 되려면, 모든 순간에 열심히, 끊임없이 살아가야된다” 써놓은 포스트잇이 아직 붙여있다. 마음 한편으로는 내가 지금 살만하니까 이런 저런 잡생각들이 많아진건가? 라는 생각이든다. 사실 제일 힘든 사람은, 이런 글을 쓸수도 없을것이다. 아마 피곤해서 그냥 누워버리겠지 라는 생각이 들겠지. 하지만, 이런 잡생각도 쓰는게 나의 Life Log 아닌가? 라는 생각에 글을 쓰면서 뭔가 마음으로 안정이된다.

사실은 요즘 이런 생각이든다. 더 좋은 사람이 되어야지 라는 생각. 구체적이진 않다. 하지만, 이 좋은 사람이 된다는건 약간 이런 방향인것 같다. 사람의 말에 귀기울여 줄수 있고, 나의 고민거리를 먼저 다가서는게 아니라, 다른 사람 고민거리를 먼저 들어주고, 내 이야기를 잘 물들일수 있는 사람, 계속 몸에 여유로움이 남아 있는 사람 그리고 기다려줄수 있는 사람. 나의 과거의 모습에 이런 글을 본다고 한다면, 참 너 뭐하냐? 이런 생각이 들기도 하지만, 이제는 나이가 들어간다. 그리고 나이가 들면 들수록, 점점더 wise 한 사람이 되려면, 이런 저런것을 많이 해봐야된다고 생각한다. 그래서 지금 하고 싶은 것들이 많이 생각나다. 이거는 이번년의 나의 목표이자 하고 싶은것이다. 2022 년 12 월 31 이 되면 꼭 내 스스로에게 확인을 해보고 싶은 사항이다.

Check List

  1. 캐나다에 있는 Panoram Ridge에 꼭 가보기 []
  2. 한국에 있는 페러글라이딩 해보기 []
  3. 미국에 이번엔 여행객으로 방문해보기 [X]
  4. 북 유럽 여행 가보기 []

뭔가 4번은 뭔가 불문명 하지만, 꼭 부딫쳐 봐야한다. 그리고 나에게 하고 싶은 말이 있다. 너는 지금까지 잘해왔고, 분명 좋은 사람으로 거듭나기 위한 지금의 과정을 지나치고 있는거야. 책도 많이 읽어서 사람에게 너의 감정을 쉽게 들키지 말고, 슬픈것과 화나는것의 차이를 분명히 알아야될거고, 좀더 진정성있고 여유로운 사람이 될수있기를 바래. 과거는 과거일뿐이고 현재를 열심히 살아가렴. 너가 분명 이런저런 Transition 을 겪고 있는건 알지만, 이것도 하나의 step 이야, 너를 더 사랑해줄수 있는 그런 기회이며, 남들을 더 사랑을 나눠줄수있고, 귀를 열수 있는 그런 사람이 되길 바래.

아직 나는 20 대 이고, sometimes you gotta say fuck to the world. It’s fine to be that way, just kin on your instinct okay?! Also, just forgot to mention I love you Nick! Keep working hard alright!

Boot Camp(3.17 ~ 4.7)

in Etcs on Logs

나는 3/17 - 4/7 일까지 논산훈려소로 3주 하는 훈련소를 갔다왔다. 사실 3.10 일 쯤 이미 마음의 준비는 끝났었지만, 가기전에 코로나가 걸려서 3.17 으로 미뤄졌다 전문연구요원으로 훈련소 가는 준비는 여기를 참고하면서 준비물을 준비했지만. 마음도 마음인지라 시계도 챙겨가지 않았다. 불침번이라걸 내가 할까? 라는 생각에… (속히 말해 뺑뺑히 돌릴것같았는데 아니였다. 그래서 결국 분대원들의 시계를 빌려서 불침번을 섰지만) 결론적으로 말하자면 되게 불편한것도 많았지만, 나름 뜻깊은 경험이며 좋은 인연을 만났다고 생각한다. 글을 쓰면서 생각이 잘 정리는 안되지만, 최대한 느낌을 글에 잘녹여들이고 싶다.

엄마와 같이 11 시쯤 출발했을거다. 엄마는 늘 걱정하지만, 티를 안내는 성격이라 말하면서 느꼈다. 그래도, 걱정을 덜어드리려구 “엄마, 이건 거의 그냥 캠프 갔다오는거니까, 걱정하지마” 라는 말을 하고 연무대 근처에서 제대로 인사 못하고, 엄마와 안녕을 했다. 코로나 기확진자여서 따로 나뉘어서 그룹이 정해졌었다. 그렇게 기다리는 중에, 주변에 있는 사람들은 많은 긴장을 한듯해보였다. 한 2-3 시간 지나고 나서야 연대를 나누기 시작했고, 그렇게 기다리다가 캐리어를 끌고 30 연대로 향하게 되었다. 내가 갔던곳은 30 연대 12 중대 2 소대 1 분대 였으며, 번호는 1 번이다. 그렇게 1번이라는 번호는 어렸을때 부터 제일 싫어 하는 번호 였으며, 부담스러운 번호였지만 어떻게든 되겠지 하며, 분대 안에 들어갔다.

사실 우리 분대원의 나이는 조사할때 부터 알고 있어서 나보다 위 93 두명 제외하고 다 어렸다는 생각을 계속하고 있었다. 물론 나이를 생각하는게 지금 생각해보면 조금 꼰대 같았지만, 뭔가 내공있는 모습을 보여주고 싶어서 바로 나는 분대원들이랑 인사와 자기소개를 먼저 해서, 점차 점차 친해졌었다. 처음에 분대안에서 보급품을 나눠주는데, 모포 와 베게를 주는데.. 와 역시 군대구나 어떻게 잘까? 라는 생각이 들었고, 관물대 안에는 헬멧, 물통, 등 이있었다. 그때서야 나는 군대에 들어왔구나라는 생각이 들었다.

코로나 기확진자여서, 10일 정도 격리를 하며, 밥은 식판에 식비늘을 끼어서 밥을 먹었었다. 참고로 군대밥은 나쁘지 않았다(밥을 너무 많이 줘서 문제였지만). 또 뭔가 습관처럼 국에다가 밥을 말아먹는 습관이 생기더라, 참 이상하게 국물이 없으면, 아침에 6시반에 밥이 넘어가지 않았었다. 불침번은 총 14명이 돌아가면서 홀수 번호로 돌아갔었다. 그 말은 즉슨 첫날에 내가 불침번을 섰었다는거다… 완전 1시간 반동안 계속 서있는건 WOW..

격리중에 여러가지 책을 받았었는데, 하나는 학습장이였고, 다른 하나는 잘 기억은 안나지만 그것은 약간 현역들에게 주어지는 날짜 카운트식으로 일기를 쓰도록 하는 책이였다. 사실 그 책은 두껍기도 하고 별로 쓰고싶지 않았다. 그래서 나는 학습장에 매일 매일 일기를 쓰기 시작하며, 편지도 쓰기 시작했다. 조금 아쉽고, 조금 서운하기도 한건 가족들이나 친구들에게 인편을 받지 못했다는 점인데, 사실 보니까 내가 연대나 중대를 말하지도 않아서 못보냈다고 한다. 또 지금 생각해보면, 딱히 서운할게 없는게 매일 10 분 정도 휴대폰을 받았다는거 였다. 마지막주에는 주지도 않았지만, 그 끝나기전 3일에 주긴 했지만.

막상 PCR 2차 검사를 한 이후에, 격리가 풀려서 모든게 자유로울것 같았지만 분대장(조교)들이 절반 가까이 코로나에 걸렸다고 한다. 와 그때는 정말 안심과 아쉬움이 있었다. 일단 조금 두려웠던 각개는 하기 싫었지만, 체력 시험? 에 팔굽혀 펴기 1 급과 윗몸일으키기 는 1급을 받고 싶어서 매일 분대원과 돌아가면서 40 개 해서 하루에 200 개 정도 했었고, 또 나의 29의 목표에 맞게 뭔가 이루고 싶었는데 이런 부분에서는 되게 아위웠다. 분대장들이 코로나에 걸리니, 밖같에는 여러 책들이 있었다. 이미 가지고 온 2 책은 다읽었었고, 다른 책을 찾아보다가, 소설을 보게되었는데, 그 소설의 이름은 “불편한 편의점”. 내가 사실 소설을 별로 유용하지도 않고, 뭐 정보같은것도 안주기때문에 좋아하진 않았는데, 그 책은 내가 읽기에 너무 편안한 느낌도 있었고, 흠 거의 평점을 5 점만점에 5 점을 주고 싶었다. 그리고 다른 한 책은 Metaverse 라는 책이였는데, 이 책도 되게 괜찮았다. 딱 잘 주제 별로 잘 나눠졌었고, 나름 코로나가 한창인 이 시대에 되게 걸맞는 정보를 담고 있던 책이였다. 이상하게 군대에서 할게 없어서, 계속 책보는게 웬지 모르게 나의 과거를 돌아보게되고, 생각이 깊어지기도 하면서, 감정적으로 여러생각을 하게 되서, 내가 가지고 있던 편입견들이 점점 없어지고 좀 더 부드러워지는 느낌이였다.

잠은 항상 12 시에서 1 시에 자서, 10시에 자는게 되게 힘들었었다. 아무생각 안하고 코를 고는 분대원들이 조금 부럽기도 했지만, 나는 항상 일기를 썼었다. 생각을 매일 정리한다는 느낌이, 생각많은 나에게 짐을 덜어주었었다. 그리고 매일 같이 기도 했다. 특정한 사람들을 위해서, 보살펴주고 계속 지켜봐달라고, 힘들때 나의 넘쳐나는 에너지를 전해달라고, 이 3주 훈련 잘 보낼수 있게 도와달라며, 기도를 했었다. 사실 조금 기독교와 먼 삶을 살아오긴 했지만, 그래도 기도하는건 나의 걱정들을 조금씩 덜어주긴했다.

조금 현타왔던건 PX 를 가는데, 벛꽃이 정말 많이 폈었다. 계속 분대내에서 있다보니 현타가 씨게 왔지만 그 나름대로 걷는게 즐거웠다. PX 는 총 두번을 갔는데, 왜 그때는 R.O.K.A 티가 너무 이뻐보이더라… 그래서 4벌이나 사버렸다.. 그리고 부모님과 친구들 선물로 화장품에 관련된거 샀었다… 총 금액은 한 15 만원 정도 샀는데, 진짜 지금 오면 좋은 추억이 될것 같다.

사실 이 글을 쓰다보니까, 여런 저런 추억들이 있는데, 너무 많기도 하고, 여런저런 면에서 귀찮기도 하다. 하지만, 이 추억들은 되게 소중히 간직될것같다. 고생도 안했고, 거의 격리만 한것같은데도 불구하고, 이런저런 면에서 분대원 동생들에게 배우고, 내가 이때까지 생각했던것들이 어느정도 정리된 느낌도 있었으며, 몸도 한츰 건강해진것 같아서 정말 좋은 경험이였다.

LeetCode 217. Contains Duplicate [Easy]

in Study on C/C++, Algorithm

Description

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

If we sort this, the duplicates must be adjacent each other. The built-in function for sort() in c++ is based on Quick Sort() the average time complexity is n*log(n). The worst case for quick sort can be n^2 which is the brute force way.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++){
            if(nums[i] == nums[i - 1])
                return true;
        }

        return false;
    }
};

Can we make it better ? We can use HashSet because to insert, and look up takes O(1). The process are following: we push the data to the set. if we have seen the data for incoming element, return true, otherwise keep inserting. Time Complexity in this case would be O(N), space would be O(N) as well, but worst case would be all unique elements

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for (int num : nums){
            if(set.count(num) > 0){
                return true;
            }
            set.insert(num);
        }

        return false;
    }
};

Separate Chaining

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Separate Chaining: A Collision Resolution Technique in Hashing

Separate chaining is indeed one of the most common collision resolution techniques used in hash tables. As a technical engineer who has implemented this in several projects, I can confirm it’s both elegant and efficient when properly configured. This algorithm can be seen as an extension of bucket sort.

Let’s break down how it works: Hash Function: We use a hash function to determine which slot a key should go into. For example, if we have a value 0.84, we might use a floor operation as our hash function, resulting in slot 8. Collision Handling: However, hashing can lead to collisions. For instance, values like 0.32, 0.39, and 0.31 would all hash to slot 3 using our floor operation. This is where collision resolution comes in.

Separate Chaining vs Open Addressing:

In Open Addressing, when a collision occurs, we would need to find open spots for each value, often by probing linearly through the table. Separate Chaining takes a different approach. Instead of linear probing, it allows multiple keys to be stored in the same slot using a linked list. This is why it’s called “separate chaining” - each slot in the hash table can chain together multiple values in a separate linked list. This approach efficiently handles collisions by allowing multiple elements to exist at the same index of the hash table. There are also different chaining technique like cuckoo hashing (which results O(1) if implemented properly)

The key advantage of separate chaining is that it degrades gracefully under a high load factor and doesn’t require the frequent resizing that open addressing might. However, it does require additional memory for the linked list pointers.

How Separate Chaining Works

In separate chaining, each slot of the hash table points to a linked list that stores all elements hashing to the same location. When a collision occurs (multiple keys map to the same index), we simply add the new element to the linked list at that particular index

Implementation

#include <iostream>
#include <iomanip>
#include <string>

using namespace std;
struct Node
{
    string key;
    int val;
    Node* next;
};

class HashTable 
{
public:
    HashTable(int _size) : size(_size)
    {
        hash_table = new Node * [size];
        for (int i = 0; i < size; i++) {
            hash_table[i] = nullptr;
        }
    }

    ~HashTable() 
    {
        for (int i = 0; i < size; i++)
        {
            Node* p = hash_table[i];
            if (p != nullptr) {
                Node* chain = p->next;
                while (chain != nullptr) {
                    Node* target = chain;
                    chain = chain->next;
                    delete target;
                }

                delete p;
                hash_table[i] = nullptr;
            }
        }

    }

    Node* insert(string key, int val)
    {
        Node* new_node = new Node();
        new_node->key = key;
        new_node->val = val;

        int idx = hash(key, size);
        new_node->next = hash_table[idx];
        hash_table[idx] = new_node;
        return new_node;
    }

    bool remove(string key) 
    {
        int idx = hash(key, size);

        if (hash_table[idx]->key.compare(key) == 0)
        {
            Node* target = hash_table[idx];
            hash_table[idx] = hash_table[idx]->next;
            delete target;
            return true;
        }

        for (Node* p = hash_table[idx]; p->next != nullptr; p = p->next)
        {
            if (p->next->key.compare(key) == 0)
            {
                Node* target = p->next;
                p->next = p->next->next;
                delete target;
                return true;
            }
        }
        return false;
    }

    Node* get(string key) 
    {
        int idx = hash(key, size);
        for (Node* p = hash_table[idx]; p != nullptr; p = p->next) {
            if (p->key.compare(key) == 0)
                return p;
        }
        return nullptr;
    }

    void display(std::string msg)
    {
        cout << msg << endl;

        // Traverse the entire hash table
        for (int i = 0; i < size; ++i) {
            cout << "  +--------+--------+" << endl;
            cout << i << " |";
            Node* p = hash_table[i];
            if (p == NULL) {
                // NULL record, print empty
                cout << " " << setw(6) << "" << " | " << setw(6) << "" << " |";

            }
            else {
                // Print the record from the table
                cout << " " << setw(6) << left << p->key << " | " << setw(6) << right << p->val << " |";

                // Traverse and print the chain
                for (p = p->next; p != NULL; p = p->next) {
                    cout << " --> " << "[ " << p->key << " | " << p->val << " ]";
                }
            }
            cout << endl;
        }
        cout << "  +--------+--------+" << endl << endl;
    }

private:
    int hash(string key, int size)
    {
        int hash = 0;
        for (int i = 0; i < key.size(); i++) {
            hash += key[i];
        }
        return hash % size;
    }

    Node** hash_table;
    int size;
};

int main()
{
    HashTable customers(8);

    // Insert key-value pairs
    customers.insert("Alice", 101);
    customers.insert("Bell", 102);
    customers.insert("Max", 103);
    customers.insert("Evin", 104);
    customers.insert("Ana", 105);
    customers.insert("Dave", 106);
    customers.insert("Leo", 107);
    customers.display("HASH TABLE after insertion of customers 'Alice', 'Bell', 'Max', 'Evin', 'Ana', 'Dave', and 'Leo'.");

    // Delete key-value pairs
    customers.remove("Dave");
    customers.remove("Ana");
    customers.remove("Max");
    customers.display("HASH TABLE after deletion of customers 'Dave', 'Ana', and 'Max'.");
}

Time Complexity

Average Case

  • Search: O(1 + α) where α is the load factor (number of elements divided by table size)
  • Insertion: O(1 + α)
  • Deletion: O(1 + α)

For a successful search, approximately 1 + (α/2) links need to be traversed on average.

Worst Case

  • Search: O(n) when all keys hash to the same bucket
  • Insertion: O(n) in the pathological case where all elements end up in one chain
  • Deletion: O(n) since deletion requires searching first

Resource

Youtube Youtube

Count All Occurence

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Problem Statement

정렬되어 있는 배열 안에 어떤 값이 몇번 들어있는지를 세는 알고리즘을 작성하시요

Input: Array: 1, 2, 3, 3, 3, 5, 6, 6, 7, 16 Target: 3 Output: 3

int CountAllOccurence(int arr[], int n, int x) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) count++;
    }
    return count;
}

Time complexity would be O(N).

Two Pointer

int countSpecficElement(const std::vector<int>& vec, int target) {
    if (vec.empty()) { return 0; }

    int n = vec.size();
    int i = 0;

    while(i < n && vec[i] <= target) {
        if (vec[i] == target) {
            int j = i;

            while(j < n && vec[j] == target) {
                j++;
            }

            return j - i;
        }

        i++;
    }
    return 0;
}

Time Complexity would be O(N).

int BinarySearch(const vector<int>& vec, int lo, int hi, int x){
    while(lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (vec[mid] < x) lo = mid+1;
        else if (vec[mid] > x) hi = mid-1;
        else return mid;
    } 
    return -1;
}

The Time complexity would be O(logN + count)

Two Binary Search (Range Method)

I called this as range is because we find the first occurence(location within the range) from left to right, and second occurence from right to left, then we return the total count from that range.

int Count(const vector<int>& vec, int x) {
    const int n = vec.size();
    int i = BinarySearch(vec, 0, n-1, x);
    if (i == -1) return;

    // we find the first one
    int count = 1;
    int left = i - 1;
    while (left >= 0 && arr[left] == x) {
        count++;
        left--;
    }

    int right = i + 1;
    while(right < n; && arr[right] == x) {
        count++;
        right++;
    }
    return count;
}

This guarentees the time complexity to be O(logN)

Radix Sort

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Radix Sort is similar to Counting Sort, but it handles different types of inputs. Consider the array vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };. If we were to sort this array using comparison-based sorts like Merge Sort or Quick Sort, we would achieve a time complexity of O(N log N). However, as we know from Counting Sort, we can achieve a linear time complexity of O(N) under certain conditions.

How it works

Radix Sort leverages a similar approach to achieve efficient sorting. The key idea is to sort numbers digit by digit, starting from the least significant digit (ones place) to the most significant digit. To do this, we need a placeholder for each digit (0 through 9). We iterate through each digit position (ones, tens, hundreds, etc.) and sort the numbers based on that digit.

Let’s implement Radix Sort similarly to Counting Sort. The crucial part is indexing each digit. The expression count[a / exp % 10] returns the index for each digit. We then increment this count. After counting, we accumulate these counts to determine the positions where each number should be placed, just like in Counting Sort.

Finally, we iterate through the array from right to left (last index to first). For each number, count[temp[i] / exp % 10] - 1 gives us the index where the number should be assigned in the sorted array. We subtract 1 because array indices start at 0.assigned.

void CountingSort(vector<int>& arr, int k, int exp)
{
	vector<int> temp = arr; // copy
	
	vector<int> count(k + 1, 0);
	for (auto a : arr)
		count[a / exp % 10] += 1;

	for (int i = 1; i < count.size(); i++)
		count[i] += count[i - 1];

	Print(count);

	for (int i = arr.size() - 1; i >= 0; i--)
	{
		arr[count[temp[i] / exp % 10] - 1] = temp[i];
		count[temp[i] / exp % 10]--;
	}
}

void RadixSort(vector<int>& arr)
{
	int k = 9; // from 0 to 9
	int m = *max_element(arr.begin(), arr.end());

	for (int exp = 1; m / exp > 0; exp *= 10)
	{
		CountingSort(arr, k, exp);
		Print(arr);
	}
}

vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
RadixSort(arr);

LeetCode - Roman to Integer [Easy] - 13

in Study on C/C++, Algorithm

How to Solve

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

Now what we want is basically convert Romans to Integer. How can we solve it. If we have all those unique values stored in some dictionary, then we can check whether we could use those integer and sum it up. The special case would be two letter associated for example IV which is 4. (V - I). With this logic, we can solve it by two approaches.

If we have all those unique values stored in dictionary, then we need to handle the single one, then the two letter one. The time complexity would be the string size (N).

class Solution {
public:
    int romanToInt(string s) {
        std::map<string, int> roman = {
            {"I", 1}, {"V", 5}, {"X", 10}, {"L", 50}, {"C", 100}, {"D", 500}, {"M", 1000}, 
            {"IV", 4}, {"IX", 9}, {"XL", 40}, {"XC", 90}, {"CD", 400}, {"CM", 900}};
        
        if (s.length() <= 0 && s.length() > 16)
            return 0;
    

        int i = 0;
        int sum = 0;
        while (i < s.length())
        {
            // Two String Handle
            if (i < s.length() - 1){
                string doubleStr = s.substr(i, 2);
                
                if (roman.count(doubleStr)){
                    sum += roman[doubleStr];
                    i+=2;
                    continue;
                }
            }

            // OneString
            string singleStr = s.substr(i, 1);
            sum += roman[singleStr];
            i+=1;
        }

        return sum;
    }
};

Okay, let’s think further more. For example, if we have DXCI, then we can calculate D + (C - X) + I or CMXCIV = (M - c) + (c - x) + (v - i), which is very useful in the logic. Also, let’s not use all those special cases which are the two letters combination.

class Solution {
public:
    int romanToInt(string s) {
        std::map<char, int> roman = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
        
        if (s.length() <= 0 && s.length() > 16)
            return 0;

        int sum = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if(roman[s[i]] < roman[s[i+1]])
                sum -= roman[s[i]];
            else
                sum += roman[s[i]];
        }

        return sum + roman[s[s.length()-1]];
    }
};

If we have MCMXCIV, when we think about this problem, we can see that M + (M - C) + (C - X) + (V - I). This case, the constraint is if [i+1] > [i], then we subtract [i], else we add. Then, we can simply get the code above.

Bucket Sort

in Study on C/C++, Algorithm

  • Reviewing what I studied, how this work will be explained as well.

Bucket Sort is a sorting algorithm that is similar in concept to Radix Sort and Counting Sort, but it is designed to handle floating-point numbers. Like these other algorithms, Bucket Sort uses placeholders to sort elements efficiently. However, unlike Radix Sort, which sorts integers digit by digit, Bucket Sort distributes floating-point numbers into buckets and then sorts each bucket individually.

Time Complexity

The time complexity of Bucket Sort can vary depending on the distribution of the input data. In the best case, where the numbers are uniformly distributed, the time complexity can be O(N + K), where N is the number of elements and K is the number of buckets. However, if the numbers are not well-distributed and most elements end up in a single bucket, the time complexity can degrade to O(N^2) due to the sorting algorithm used within each bucket.

Steps to Implement Bucket Sort

  1. Divide Data into Buckets: If there are N data points, divide them into K buckets. Ideally, K should be close to N for optimal performance.
  2. Distribute Elements into Buckets: Place each element into its corresponding bucket based on its value.
  3. Sort Each Bucket: Use a sorting algorithm like Insertion Sort to sort the elements within each bucket.
  4. Merge Sorted Buckets: Combine the sorted elements from all buckets to produce the final sorted array.

Implementation

Here’s an example implementation of Bucket Sort for floating-point numbers. We’ll consider a simple case with 10 buckets and the input array { 0.78f, 0.17f, 0.39f, 0.26f, 0.72f, 0.94f, 0.21f, 0.12f, 0.23f, 0.67f }.

// Insertion Sort
void InsertionSort(vector<float>& bucket)
{
	for (int i = 1; i < bucket.size(); ++i) {
		float key = bucket[i];
		int j = i - 1;
		while (j >= 0 && bucket[j] > key) {
			bucket[j + 1] = bucket[j];
			j--;
		}
		bucket[j + 1] = key;
	}
}

void BucketSort(vector<float>& arr, int num_buckets)
{
	vector<vector<float>> buckets(num_buckets);

	// Put Bucket
	for(auto& a : arr)
	{
		int index = int(a * num_buckets);
		buckets[index].push_back(a);
	}

	for (int i = 0; i < buckets.size(); i++) {
		InsertionSort(buckets[i]);
    }

    // update arr from sorted bucket
	int index = 0;
	for (int i = 0; i < buckets.size(); i++)
	{
		for (int j = 0; j < buckets[i].size(); j++)
		{
			arr[index++] = buckets[i][j];
		}
	}
}

Pagination