자료구조와 알고리즘에 관한 질문들

소트 종류 아는대로 설명하시고, 좋아하는 소트가 있습니까? 설명하고 손코딩 한번 해 봐라.

선형 소트와 비선형 소트로 나눠서 설명드려야 할 것 같다. 선형 소트는 시간 복잡도가 O(n) 에서 O(n^2)에 이르는 소트로써 원소를 하나 하나 비교하거나 순회한 후 다시 정렬하는 과정이기 때문에, 발상 자체는 간단하지만 시간 복잡도에서 손해를 크게 본다.

흔한 예로 버블 소트와 선택 소트(selection sort)를 들 수 있을 것 같다.

버블 소트는 n번째 원소와 n + 1번째 원소를 비교한 후 작은 것을 앞으로 오게 자리를 바꾸는 것이다. 원소의 숫자만큼 작업을 수행해야 하기 때문에 O(n!)의 시간복잡도가 발생한다.

선택 소트는 리스트의 크기를 하나씩 줄여나가면서 해당 리스트 안에서 가장 작은 원소를 가장 앞으로 빼는 정렬이다. O(n^2)가 발생한다.

소트에서 시간복잡도를 줄이려면 비선형 소트를 사용하는 것밖에 방법이 없다. 이른바 3대 소트라고 공부하기도 하는데 퀵소트, 머지소트, 힙소트가 꼽힌다. 셋 다 O(log n)의 시간복잡도를 갖는다.

제가 가장 좋아하는 퀵소트부터 설명드리면 우선 리스트에서 pivot 값을 고른 후에 리스트의 원소들을 비교하며 계속 재귀호출해 값을 정렬하는 것이다. 다만 이 때 pivot 값이 비효율적으로 설정되면 시간복잡도는 N^2 까지 치솟을 수도 있다.

제가 제일 좋아하는 소트니까 간단하게 손코딩을 보여드리겠다.

def quick(array):
    
    if len(array) < 2:
        return array

    pivot = array[len(array) // 2]

    less = []
    more = []
    equal = []

    for number in array:
        if number > pivot: 
            more.append(number)
            continue

        if number < pivot:
            less.append(number)
            continue
        
        equal.append(number)

    return quick(less) + quick(equal) + quick(more)

VS Code에서 짰으니까 손코딩이나 진배없다.

검색 종류 아는대로 말씀해 보시고, 좋아하는 검색이 있습니까? 설명하고 손코딩 한 번 해봐라.

검색도 마찬가지로 선형과 비선형으로 나눌 수 있겠다. 선형 검색은 O(n)의 시간복잡도가 발생한다.

가장 단순하게 생각할 수 있는 방식은 이런 것일 것 같다.

def search(array, n):

    for i in range len(array):
        if array[i] == n:
            return i
        
    return -1

한번씩 다 순회하는 방법인데 그리 효율적이지는 않다. 제가 좋아하는 검색은 이진 검색이다.

이진 검색은 퀵소트와 메카니즘이 참 비슷한데 중위값을 정해놓은 다음 목표값이 중위값보다 크면 중위값의 오른쪽 원소들로 검색 범위를 한정해서 다시 재귀 호출하고, 만약 작으면 왼쪽 원소들로 한정해서 똑같이 하는 것이다.

눈치채셨겠지만 이진 검색의 가장 큰 전제조건은 리스트가 정렬돼있다 는 것이다. 정렬되지 않은 리스트에서는 이진 검색을 사용할 수 없다.

만약 운이 정말 좋아 타겟값과 중위값이 일치한다면 시간복잡도는 O(1) 로도 빠질 수 있다. 그러나 말 그대로 이건 운이 좋은 경우고 평균적으로 O(log N)의 복잡도가 발생한다.

def binary(array, target, start, end):
    
    middle_index = (start + end) // 2

    if middle_index < start or middle_index > end:
        return -1

    if array[middle_index] == target:
        return middle_index

    if target > array[middle_index]:
        return binary(array, target, middle_index, end)

    if target < array[middle_index]:
        return binary(array, target, start, middle_index)

    return -1

당신은 자바 Backend 직무를 수행하게 될 것이다. Python으로 손코딩한 이유는?
- 저는 자바를 무척 좋아하고 사랑한다. 제가 개발을 시작한 언어이기도 하고 가장 자신있는 언어이기도 하다.
- 손코딩 중 다른 언어를 사용해 죄송합니다만 저는 그동안 자료구조 / 알고리즘 학습이나 예제 구현에 있어 Python 언어를 즐겨 사용해왔다. 가장 큰 이유는 Main 메소드가 없어도 되고, 두번째 이유는 클래스 바깥에서 함수를 선언할 수 있어 알고리즘 작성에 효율성이 좋았기 때문이다.
- 제가 아는 만큼 정확하고 빠르게 보여드리기 위해 보일러플레이트를 최대한 소거시킨 Python 코드를 보여드린 것이다. 개념 이해가 중요하다고 생각했다.
이진 탐색과 이진 탐색 트리가 이름이 비슷한 것 같은데 트리는 뭐가 달라요?
- 이진 탐색 트리란 이진 트리를 기반으로 구현한 것이다.
- 처음 입력되는 값을 부모로 하고, 작으면 왼쪽 크면 오른쪽 자식으로 놓는다.
- 이런 식으로 데이터를 정렬한 후, 트리를 중위 순회하면 값을 오름차순으로 정렬할 수 있다.
중위 순회는 뭔가요? 순회가 뭐죠?
- 순회는 트리 자료 구조를 탐색하며 데이터를 조회하는 순서에 관한 방법론이다.
- 전위 순회: 부모부터 시작해 왼쪽 자식을 주욱 조회한 다음, 오른쪽 자식을 조회한다.
- 중위 순회: 왼쪽 - 부모 - 오른쪽 순서로 순회한다.
- 후위 순회: 왼쪽 - 오른쪽 - 부모 순으로 순회한다.

해시의 개념에 대해 설명해 보세요.

해시는 데이터를 정수 형태의 코드로 바꾸는 것이다. 데이터를 이렇게 바꿔주는 함수를 해시 함수라고 칭한다.

해시 함수는 나름의 알고리즘을 사용해서 데이터를 정수로 바꾸는데 모듈러(modulo) 연산이 가장 흔하고 간단한 예시일 것 같다. 데이터가 갖고 있는 필드 값 중 하나를 모듈러 연산 수행해서 그 나머지를 해시코드로 삼는 것이다.

같은 데이터가 같은 해시함수를 거친다면 항상 같은 결과가 보장돼야 하지만, 해시코드가 같다고 해서 해당 객체의 동등성까지 보장할 순 없다. 서로 다른 객체가 같은 해시코드를 갖게되는 것을 해시 충돌(hash collision) 이라고 부른다. 해시 코드를 인덱스로 삼아 객체를 저장하는 해시테이블에서 이와 같은 해시 충돌은 큰 제약 사항이 될 수도 있다.

해시 충돌을 해결하는 방법에는 크게 두 갈래가 있다.

Open Addressing
Chaining

먼저 오픈 어드레싱이란 원래 충돌이 발생했던 위치로부터 정해진 규칙에 따라 이동해서 새로운 인덱스에 객체를 보관하는 것이다. 여기엔 또 세 가지 기법이 있다.

linear probing: 선형 프로빙. n 번째 인덱스에서 해시 충돌이 발생했다면 n + 1, n + 2 순서대로 계속 빈 자리를 찾아 헤매는 것이다.
quadratic probing: 지수함수의 형태로 인덱스를 탐색한다.
double hashing: 해시 충돌이 발생하면 다른 해시함수를 한번 더 돌린다.

chaining이란 충돌이 발생한 인덱스에 링크드리스트와 같은 다른 자료구조를 적용해 같은 자리에 여러개의 값을 보관하는 것이다.

Open Addressing법의 단점은 최초 충돌이 발생한 위치의 데이터가 더이상 필요없게 되어도 계속 그 자리를 잡고 저장돼있어야 한다는 점이다. 만약 데이터가 필요없게 되었다고 그냥 메모리에서 해제하면 이 데이터를 기준으로 저장된 충돌이 발생한 다른 데이터들로 탐색을 수행할 수가 없다. entry point가 사라지는 것이다.

chaining법은 이런 문제는 없지만 해당 인덱스에 부가적인 자료구조가 더해지므로 공간 복잡도가 올라가는 단점이 있다.

오픈어드레싱, 체이닝 둘 다 시간복잡도는 O(n) 이다.

java.util.HashMap은 체이닝을 사용한다.

링크드리스트와 배열의 차이에 대해 말씀해보세요.

배열은 대표적인 선형 자료구조이다. 메모리에서 연속된 공간이 배열의 크기만큼 확보되어야 한다. 이는 데이터의 실제 존재 유무와는 무관하다. 때문에 인덱스를 알고 특정 데이터를 조회하는 작업의 시간 복잡도는 O(1)이다. 해당 인덱스에 바로 접근할 수 있기 때문이다.

그 대신 배열 요소의 삽입 / 삭제에는 큰 비용이 든다. 중간에 새로운 값이 들어왔다면 그 뒤의 원소들의 인덱스가 모두 수정돼야 한다. 삭제도 마찬가지다. 따라서 이런 작업들은 O(n) 의 복잡도가 소요된다.

한 번 값을 쓰고나면 크게 수정할 일이 없고, 인덱스값을 기준으로 객체를 조회할 일이 많을 때 적합한 자료구조이다.

링크드리스트는 원소가 다음 원소로 가는 참조를 보관한다. 뒤로만 보관하고 있으면 싱글 링크드리스트, 앞뒤로 다 보관하고 있으면 더블 링크드리스트이다. 더블 링크드리스트로는 뎈(deque)과 같은 원형 자료구조를 구현할 수 있다.

링크드리스트는 자료가 중간에 삽입되더라도 참조만 바꿔주면 되므로 O(1) 을 유지할 수 있다. 빈번한 삽입 삭제가 필요한 경우엔 링크드리스트를 사용해야 한다.