20240208_기술면접 회고

오늘의 TIL은 오늘 실시했던 기술면접에 대한 회고 내용이다.

 

1. Array를 이용해서 Stack 구현하기

프로그래밍을 하면서 자주 사용하는 Stack을 Array로 구하는 문제가 주어졌는데,

이 문제의 경우에는 Stack에 대한 기본적인 이해를 묻는 문제에 더해서

Array를 이용해서 해당 기능을 구현할 수 있는지를 묻는 문제이다.

 

우선 Stack에 대한 기본적인 지식을 정리하면,

 

1) Stack은 후입선출의 구조를 갖는다.

즉, 데이터가 순서대로 있다면, 데이터를 순서대로 넣고

(Push 한다면 순서대로 데이터를 넣고)

 

빼는 경우에는 가장 마지막에 넣었던 데이터를 빼는 방식으로 구현해야한다.

(Pop 한다면 현재 집어넣은 index의 값을 반환해야 한다)

 

2) 실제로 구현하기

이 과정은 기술면접으로 진행하면서 구술하는 방식으로 진행되었기에 글로만 구현하면,

 

임의로 길이가 10인 데이터를 배열을 이용해서 스택을 구현한다면

길이가 10인 배열을 선언하고 초기 인덱스를 0으로 선언한다.

 

push를 구현하면 현재 인덱스에 집어넣을 데이터를 집어넣고, 인덱스를 1 더한다.

 

pop을 구현하면 현재 인덱스의 데이터를 꺼내고, 인덱스를 1 빼준다.

 

이러한 방식으로 인덱스를 이용하여 해당 인덱스의 값을 더하거나 빼주는 식으로 구현할 수 있다.

 

 

2. 피보나치 수열 구현하기

피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 으로

 

지금의 값은 이전의 두 값의 합으로 표현되는 수열인데,

 

이를 함수로 표현하면 Fibo(n) = Fibo(n - 2) + Fibo(n - 1) 로 표현할 수 있는 함수이다.

 

이를 구현하는 것이 문제였는데, 이 때는 직접 코드를 작성할 수 있었다.

 

작성한 코드는 아래와 같다.

static private int Fibo(int n)
{
    // 0 1 1 2 3 5 8 13 21 34

    int a = 0;
    int b = 1;
    int tmp = 0;
    int cnt = 1;
    
    while (cnt <= n)
    {
        tmp = a + b;
        a = b;
        b = tmp;
        cnt++;
    }

    return tmp;
}

 

원래는 재귀함수를 이용하여 구현하려 하였으나, 생각이 나지 않아 위와 같이 while 문을 사용하여 구현하였다.

 

위의 함수 Fibo(n)을 사용하면 피보나치 수열의 n번째 값을 구할 수 있다.

 

while 문 안의 식을 살펴보면,

tmp 값을 선언한 뒤에 피보나치 수열의 1번항과 2번항을 더한 뒤에,

1번항은 2번항으로, 2번항은 3번항으로 이동하는 과정을 거친다. 그 후에 카운트를 1 늘려준다

 

따라서 이 과정을 거치면 한 단계마다 두 항을 더하고, 더해지는 항의 위치를 한 칸씩 오른쪽으로 이동 시킨다.

즉, Fibo(1) + Fibo(2) 를 한 후에는 Fibo(2) + Fibo(3)을 하고, Fibo(3) + Fibo(4)를 하는 방식으로 작동한다.

 

 

이를 원래 구현하고자 했던 재귀함수를 이용해서 구현하면 아래와 같다.

static int Fibonacci(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

 

아까는 튜터님의 질문에 당황하여 완성하지 못했지만,

 

지금와서 시간을 갖고 고민하니 n이 1이하인 경우의 예외처리가 되지 않아서 생겼던 문제였던거 같다.

 

구술로 코드를 설명하는 것이 직접 작성하는 것보다 훨씬 어렵다는 것을 깨달을 수 있었던 기회라고 생각한다.

 

 

3. List와 Dictionary의 차이점 설명하기

리스트와 딕셔너리의 기본적인 설명은 넘어가고 둘의 차이점을 살펴보면,

리스트의 경우 데이터 하나의 값만 저장하는 시스템이고

딕셔너리의 경우에는 데이터를 저장하는데 이를 찾는 키값도 함께 저장하는 두 요소를 함께 저장하는 시스템이다.

 

다시말해서 리스트의 경우에는 데이터를 찾는데 인덱스가 필요하지만,

딕셔너리의 경우에는 인덱스를 대신하여 키가 있는 것이다.

 

즉, 아래와 같이 정리할 수 있다.

리스트 - 순서대로 자동으로 지정되는 인덱스

딕셔너리 - 개발자가 원하는대로 인덱스를 지정

 

즉, 딕셔너리의 경우에는 개발자가 이미 키(인덱스)를 알고 있기 때문에 이 데이터에 빠르게 접근할 수 있다.

 

딕셔너리는 데이터에 빠르게 접근해야되는 필요가 있는 경우,

각 요소들이 유일한 식별자(키)를 가지는 경우에 유용하게 사용할 수 있다.

 

단, 만약 해시 충돌이 일어난다면 딕셔너리는 리스트보다 비효율적일 수 있다.

(해시 값이란 키를 통해 데이터(값)에 접근할 때 내부적으로 사용되는 중간 단계인데,

 이 해시 값이 둘 이상의 데이터에 접근할 수 있는 상태가 되는 것이 해시 충돌이다)

 

해시 충돌이 일어난다면, 딕셔너리에서는 사용하려고 했었던 해시 값의 데이터가 동일한지 검사한다.

만약 데이터가 다르다면(해시 값이 같지만 데이터가 다른 경우)

딕셔너리는 이 충돌을 해결해야되는데

예를 들면 링크드 리스트와 유사한 자료구조를 이용해서 해당 해시 값에 대한 데이터들을 저장한다.

이렇게 중복되는 해시 값들은 그 안에서 소규모 그룹으로 데이터들을 연결하여 저장한다.

 

이 해시 값에 해당하는 키를 조회하면 우선 이 해시 값에 도달하게 되고,

해시 값에서 링크드 리스트를 순회하면서 데이터를 찾게된다.

(즉, 해시 값에 대한 시간 복잡도가 1에서 2로 늘어나게 된다.

따라서 같은 해시 값이 많아지면 시간 복잡도는 계속 증가하게 된다)

해시 충돌이 많아지면, 더욱 길어지는 링크드 리스트가 생기게 되고,

이는 특정 키를 찾기 위해 더 많은 비교 연산을 수행하게 된다.

그로 인해 검색 성능에 영향을 끼치게 된다.

 

위와 같이 딕셔너리의 문제점을 가지고 리스트와의 차이점을 설명할 수 있다.

 

 

오늘은 기술면접을 진행하면서 기존과는 다른 방식으로 좀 더 심층적으로 면접을 보는 느낌으로 진행했는데

 

오늘 받았던 질문들은 좀 더 머리 속에 남을 것 같고 중요한 지식들이니 이렇게 정리하며 회고했다.