개발자의 논리적 사고와 문제 해결 ‘Set 구현 과정’ 따라가기
개발자의 논리적 사고와 문제 해결 ‘Set 구현 과정’ 따라가기 관련
개발자에게 필요한 논리적인 사고와 문제 해결력이란 무엇일까요? 기능을 뚝딱뚝딱 만들고 코드를 빠르게 짤 수 있는 것으로, 논리적으로 문제를 해결하고 있다고 말할 수 있을까요? 또한 면접에서는 면접관들이 여러분의 논리적 사고력을 어떻게 확인할 수 있을까요? 반대로 여러분의 논리적 사고력을 잘 보여주기 위해 무엇을 할 수 있을까요? 예상 면접 질문을 보고, 열심히 외우는 것만으로 과연 논리적 사고력을 증명해 낼 수 있는 걸까요?
이번 글에서는 ‘논리적 사고’가 무엇인지를 알아보기 위해, 자료 구조 하나를 구현해 볼 것입니다. 코딩 실력을 보는 것이 아니기 때문에 실제로 코드를 쓰지는 않지만, 코드를 작성하기 전에 꼭 거쳐야 할 논리적 사고 과정을 살펴보겠습니다.
우리가 개발할 때 사용하는 많은 자료 구조 중, 이번에 구현해 볼 자료 구조는 바로 Set(집합)입니다. 많은 언어에서 기본적으로 제공되는 자료 구조인 만큼 아마 사용해 본 경험이 있을 텐데요. 사용하면서 Set이 어떻게 구현되는지 고민해 본 적 있으신가요?
Set을 구현하는 방식은 대표적으로 해시(Hash)로 구현하는 방식과 트리(Tree)로 구현하는 방식이 있습니다. 그중 오늘은 트리로 구현하는 방식을 살펴볼 건데요. C++, Java, Rust 등 많은 언어가 Set을 트리 형태로 제공하고 있습니다. Set이 어떻게 트리를 이용해 구현되는지, 그 과정을 한 번 고민해 보고, 논리적 사고 과정을 따라가 보겠습니다.
Set의 특징과 세 가지 기본 연산
Set 인터페이스
Set은 프로그래밍에서 가장 기본적인 자료 구조 중 하나로, 데이터를 중복 없이 담을 수 있습니다. 담고 있는데 데이터 간 순서를 유지하지 않기 때문에 순서는 중요하지 않지만, 중복을 제거하고자 할 때 사용됩니다.
예를 들어, 중복되지 않는 숫자를 여러 개 뽑고 싶을 때 Set을 사용하면, Set의 크기가 원하는 개수만큼 도달할 때까지 랜덤한 숫자를 뽑아 추가하는 것을 반복하면 됩니다.
Set의 세 가지 연산
1. 검색(Search)
검색은 Set에 특정 원소가 존재하는지 확인하기 위한 연산입니다. 검사하려는 원소가 Set에 포함되어 있으면 true, 그렇지 않으면 false를 반환합니다.
2. 삽입(Insert)
삽입은 특정 원소를 Set에 추가하는 연산입니다. 만약 해당 원소가 이미 Set에 포함되어 있으면 아무런 작업도 하지 않습니다.
3. 삭제(Delete)
특정 원소를 Set에서 삭제합니다. 해당 원소가 Set에 포함되어 있지 않다면 아무런 작업도 하지 않습니다.
이 세 가지 연산은 Set 인터페이스를 어떻게 구현하는지에 따라, 효율성과 유리한 상황이 달라집니다. 그렇다면 가장 기초적인 구현부터 시작해 문제점을 해결하며, 구현체를 발전시켜 나가는 과정을 함께 짚어볼게요.
배열로 구현하기
Set이 원소를 담는다는 것을 고려했을 때 가장 먼저 떠오르는 것은 배열입니다. 실제로 배열을 활용하면, 작게나마 Set을 구현할 수 있습니다. 배열과 담고 있는 원소의 개수를 이용해 Set의 세 가지 연산을 구현해 볼게요.
검색은 배열을 순회하며 찾고자 하는 원소가 배열에 들어있는지를 확인함으로써 쉽게 구현할 수 있습니다. 이 방식은 선형 탐색이므로 의 시간 복잡도가 됩니다.
원소를 삽입하기 위해서 그냥 배열 맨 뒤에 원소를 넣어야 한다고 생각할 수 있습니다. 하지만 Set은 원소의 중복을 허용하지 않기 때문에, 삽입하려는 원소를 이미 담고 있는지를 확인해야 합니다. 이 과정은 위의 검색 연산을 활용해 구현할 수 있습니다. 만약 삽입하려는 원소를 이미 포함하고 있지 않으면 배열의 가장 뒤에 원소를 넣고, 크기를 하나 늘려줍니다. 이 과정은 검색 연산이 수행되어야 하므로 의 시간 복잡도를 가지게 됩니다.
삭제를 하기 위한 원소를 우선 찾아야 합니다. 이 과정에서 선형 탐색을 수행하여 삭제하고자 하는 원소의 인덱스를 찾습니다. 만약 찾고자 하는 원소가 포함되어 있지 않다면, 연산은 종료됩니다. 인덱스를 찾으면 배열의 마지막 원소를 해당 인덱스로 옮기고, 담고 있는 원소의 개수를 하나 줄여줍니다. 이 방식 또한 선형 탐색이 수행되므로 의 시간 복잡도를 갖습니다.
이와 같이 배열로 구현한 Set은 간단하지만 크기가 고정된다는 한계가 있고, 효율성이 너무 떨어집니다. 세 연산 모두 의 시간 복잡도를 가지게 됩니다. 이와 같은 시간 복잡도를 갖는 방식을 추가와 삭제가 빈번히 발생하는 Set으로 활용하면, 심각한 효율성 저하를 일으킬 수 있습니다.
정렬된 배열로 구현하기
조금 더 발전된 구현 방식으로 배열을 정렬된 상태로 유지해 놓는 방식이 있습니다. 정렬된 배열을 이용하려면 필연적으로 중간에 원소를 삽입하거나, 삭제할 때 원소 간 순서를 유지하기 위해 원소를 한 칸씩 밀거나 당겨주어야 하므로 성능 향상을 기대하기 어렵습니다. 하지만 검색 연산에서는 효율성을 증가시킬 수 있는 방식이 됩니다.
배열이 정렬되어 있으므로 선형 탐색을 할 필요가 없습니다. 정렬된 배열에서는 이분 탐색을 이용해 의 시간 복잡도로 검색을 구현할 수 있습니다.
새로운 원소를 삽입할 때는 전과 같이 배열의 맨 뒤에 추가할 수 없습니다. 원소가 들어가야 하는 적절한 위치를 찾고, 해당 위치와 그 뒤에 있는 원소들을 한 칸씩 뒤로 밀어 주어야 합니다. 이 과정에서 위치를 찾는데 , 원소들을 한 칸씩 뒤로 밀어주는데 의 소요되어 총 의 시간 복잡도가 소요됩니다.
삭제 연산도 삽입과 마찬가지로 삭제하려는 원소의 위치를 이분 탐색으로 찾고, 원소들을 한 칸씩 당겨 주어야 합니다. 이 과정에서 의 시간 복잡도가 소요됩니다.
배열이 정렬된 상태로 유지하게 되면, 삽입 과정에서 시간 복잡도를 줄일 수 있습니다. 그러나 여전히 충분히 효율적이지 못하고, 크기가 고정된다는 한계가 있습니다. 데이터를 얼마나 넣을지 모르는 범용적인 자료 구조를 설계하는 이상, 크기가 고정되는 것은 큰 단점이 됩니다.
링크드 리스트로 구현하기
링크드 리스트로 Set을 구현하면 담는 원소의 개수에 따라 크기를 동적으로 변경할 수 있습니다. 하지만 링크드 리스트를 이용하면, 배열에서는 상수 시간이 소요되는 random access가 이 소요되기 때문에 이분 탐색을 적용할 수 없습니다. 따라서 링크드 리스트의 원소들을 정렬해 놓는 것은 사실상 의미가 없습니다.
이를 고려하면 링크드 리스트를 활용하여 Set의 세 가지 연산은 다음과 같이 구현됩니다.
링크드 리스트에는 이분 탐색을 적용할 수 없기 때문에 선형 탐색을 수행해야 합니다. 따라서 이 소요됩니다.
링크드 리스트이기 때문에, 어떤 위치에서든 상수 시간 안에 원소를 삽입할 수 있습니다. 하지만 중복 검사를 위한 선형 탐색에서 이 소요되므로 전체 시간 복잡도는 이 됩니다.
삽입과 마찬가지로 링크드 리스트에서 하나의 노드를 삭제하는 연산 자체는 상수 시간이 소요되지만, 삭제하고자 하는 원소를 찾아야 하므로 이 소요됩니다.
위에서 살펴본 것처럼 링크드 리스트를 이용하면, 데이터의 개수에 제약받지 않는 Set을 구현할 수 있지만, 다시 세 연산들의 효율성이 떨어지게 됩니다. 앞에서 배열을 정렬시켜 효율성을 향상시켰던 것처럼 여기서도 무언가 효율성을 위해, 링크드 리스트와 정렬의 개념을 합친 방식이 필요해 보입니다.
이진 탐색 트리로 구현하기
링크드 리스트만으로는 정렬 상태를 유지할 수 없습니다. 하지만 트리를 도입한다면 정렬 상태를 유지할 수 있습니다. 여기서 이진 탐색 트리가 등장합니다. 이진 탐색 트리는 하나의 노드가 최대 두 자식을 갖는 이진 트리의 일종으로, 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큰 상태를 유지하여, 전체적으로 정렬된 상태를 유지하는 자료 구조입니다.
이진 탐색 트리는 평균적으로 의 높이를 가지고 있기 때문에 Set의 세 연산을 다음과 같이 구현할 수 있습니다.
이진 탐색 트리에서 해당 원소의 존재 여부를 검색할 수 있습니다. 이 과정은 루트 노드부터 시작하여 찾고자 하는 원소를 노드의 값과 비교합니다. 이때 작다면 왼쪽 자식 노드, 크다면 오른쪽 자식 노드로 이동하는 것을 반복하여 찾을 수 있습니다. 이 과정은 이진 탐색 트리의 평균 높이에 비례하는 시간 복잡도인 에 수행됩니다.
이진 탐색 트리의 삽입 과정과 거의 같습니다. 삽입하려는 원소의 값에 따라 적절한 위치를 찾아 삽입합니다. 하지만 Set이기 때문에 위치를 찾는 과정 중 중복이 발생한다면, 아무 작업도 하지 않습니다. 이 과정 또한 에 수행됩니다.
이진 탐색 트리의 삭제 과정과 같습니다. 삭제하려는 원소의 값에 따라 노드를 삭제합니다. 의 시간 복잡도를 갖습니다.
이진 탐색 트리를 활용하여 효율성을 끌어올렸습니다. 의 특성상 매우 큰 개수의 데이터도 무리 없이 처리할 수 있는 자료 구조가 되었습니다. 하지만 기본적인 이진 탐색 트리를 활용했기 때문에 최악의 경우 여전히 의 시간 복잡도가 소요될 수 있습니다.
예를 들어, 1, 2, 3, 4, 5를 순서대로 삽입하면 다음과 같은 그림이 됩니다.
이처럼 한쪽으로 쏠린 이진 탐색 트리에서는 세 연산이 모두 의 시간 복잡도를 갖습니다. 이를 해결하기 위한 방안을 찾아보겠습니다.
균형 잡힌 이진 탐색 트리로 구현하기
위에서 살펴 본 이진 탐색 트리의 한계는 원소들이 한 쪽으로 쏠리게 되었을 때 발생합니다. 이 문제를 해결하기 위해 균형 잡힌 이진 탐색 트리가 등장합니다. 원소를 추가하거나 삭제할 때, 단순히 대소를 비교하여 찾은 위치를 그대로 이용하는 것이 아니라, 트리의 균형을 유지하기 위해 추가적인 작업을 해주는 것입니다.
균형 잡힌 이진 탐색 트리를 이용하면 트리의 높이를 항상 으로 유지할 수 있게 됩니다. 실제로 많은 Set이 균형 잡힌 이진 트리를 활용하여 구현되고, 세 연산에 의 시간 복잡도를 갖습니다.
균형 잡힌 이진 탐색 트리에는 균형을 잡기 위한 방식별로 여러 종류가 있으며, 각각 장단점이 존재합니다.
레드-블랙 트리
균형을 유지하기 위해 노드 별로 레드 혹은 블랙의 색을 이용합니다. 이 방식은 균형을 잡기 위한 조건이 비교적 엄격한 편이 아닙니다. 그러므로 다른 종류의 균형 잡힌 이진 탐색 트리보다 높은 경우가 발생할 수 있습니다. 그럼에도 불구하고 에 비례하는 높이를 가지기 때문에 실제로 큰 성능 차이를 보이지는 않습니다.
레드-블랙 트리는 이 완화된 균형 조건으로 인해, 균형을 유지하기 위해 필요한 추가 연산의 횟수가 적은 편입니다. 그렇기 때문에 원소의 추가, 삭제 등 변경 점이 생기는 상황이 많아야 할 때 유리합니다.
또한 구현이 간단하고 범용적인 자료 구조로, C++, Java 등 많은 언어에서 레드-블랙 트리로 Set을 구현하여 제공하고 있습니다.
AVL 트리
AVL 트리는 더욱 엄격한 균형 조건을 가지고 있습니다. 이로 인해 항상 트리의 높이를 이상적인 높이로 유지할 수 있습니다. 이는 원소의 추가, 삭제 등 변경 점이 생길 때 레드-블랙 트리보다 추가적인 연산을 요구하여, 성능이 떨어질 수 있습니다.
반면, 트리의 높이를 이상적으로 유지하기 때문에 검색의 효율성은 살짝 더 높다고 할 수 있습니다. 물론 레드-블랙 트리에서 언급한 것처럼 큰 차이는 아니지만, 원소의 추가, 삽입이 발생할 확률이 적습니다. 또한 상대적으로 검색 연산의 비율이 매우 큰 상황에서는 AVL 트리를 고려해 볼 만합니다.
하지만 Set을 이용하는 많은 경우, 원소의 추가, 삭제가 빈번히 발생하는 상황이므로 실제로 AVL 트리로 구현된 Set을 제공하는 언어는 거의 없습니다.
B-트리
B-트리는 하나의 노드가 여러 개의 자식 노드를 가지기 때문에 이진 트리는 아니지만, 위에서 살펴본 것과 같은 맥락으로 원소의 순서를 유지하면서 Set을 구현합니다.
B 트리는 대용량 데이터를 처리할 때 유리합니다. 디스크에 쓰여진 데이터를 관리한다던가, 매우 큰 데이터를 처리할 때, 혹은 데이터의 범위 검색을 해야 할 때 활용할 수 있습니다. 이러한 특징으로 Rust와 같이 메모리 관리에 특화된 언어들이 B-트리로 Set을 구현해 제공하는 경우가 많습니다.
논리적인 사고와 문제 해결
이렇게 Set을 구현하기 위한 여러 방법을 떠올려보면서, 현재 언어들이 어떻게 Set을 구현하게 되었는지까지 도달하게 되었습니다. 사실 각 과정을 하나하나 떼어놓고 보면 별로 어려운 내용이 아니었을 겁니다. 배열, 정렬, 링크드 리스트, 이진 탐색 트리 등은 이미 알고 있거나, 적어도 들어 본 개념들로 범용적이고 강력한 Set을 구현해 낼 수 있습니다.
Set을 처음 구현하라는 요구를 들었을 때는 막막한 감정이 들 수 있습니다. 처음부터 효율적이고 어디에서나 쓸 수 있는 완벽한 Set을 구현하려고 했기 때문입니다. 배열로 해볼까 하다가도 왠지 비효율적일 것 같고, 크기 제약이 있으니 넘어가고, 다른 방식을 떠올려봐도 한계가 보여 그만두게 됩니다. 이러한 과정을 반복하다가 결국 Set 구현은 어려운 것이라는 인식이 박혀 포기하게 됩니다.
그러나 위에서 살펴보았듯 Set의 구현은 이미 여러분이 어렴풋하게나마 알고 있는 내용의 조합입니다. 중요한 것은 이러한 내용을 어떻게 적재적소에 꺼내 활용하느냐입니다. 그리고 이러한 능력이 바로 ‘논리적인 사고’입니다.
논리적으로 사고하고, 문제를 해결하기 위해서는 우선 작은 해결책이라도 떠올려보고, 그 해결책이 왜 마음에 들지 않는지 따져야 합니다. 그렇게 해서 발견한 문제점들을 하나씩 해결해 나가는 것이 바로 ‘논리적 문제 해결’입니다.
주변에서 면접을 준비하는 분들에게 항상 하는 이야기가 있습니다. 아는 질문이 나오면 좋고, 모르는 질문이 나오면 더욱 좋은 기회라고 이야기합니다. 아는 질문에 대한 답변은 여러분이 그동안 얼마나 열심히 공부했는지를 보여줄 수 있습니다. 그러나 결국 찾아보면 다 나오는 내용이고, 암기만 열심히 해도 잘 대답할 수 있는 내용이죠.
반면 면접에서 모르는 질문이 나온다면, 여러분이 평소에 공부하거나 프로그래밍할 때 얼마나 논리적으로 접근하는 사람인지 보여줄 수 있습니다. 단순히 모르겠다에서 끝나는 것이 아니라, 문제를 해결하는 논리적인 과정을 그대로 보여줄 수 있는 것입니다.
면접관으로 참여하는 개발자들은 이렇게 논리적으로 문제를 해결하는 과정에 상당한 흥미를 느낍니다. 단순히 “잘 외워 왔군”으로 끝나는 것이 아니라, 여러분의 논리를 파악하고 그 논리를 파헤치려 듭니다. 논리의 약점을 찾으면 그 약점에 대한 꼬리 질문을 던질 것이고, 약점이 없는 정답이라면 더할 나위 없이 좋을 것입니다. 그 프로세스 안에서 여러분과 면접관은 논리적인 대화를 나누며, 인상 깊은 시간을 보내게 되겠죠.
마치며
이번 글에서는 자주 사용하는 자료 구조인 Set을 어떻게 구현하는지, 문제 해결 과정을 살펴보았습니다. 평소에 프로그래밍하면서 자주 사용하지만, 무심코 지나갔던 여러 자료 구조와 알고리즘, 심지어 기능을 어떻게 구현할 수 있을지까지, 매 순간 여러 옵션을 열어두고 장단점을 비교하는 것으로 논리적인 사고력을 키워보세요. 당장은 느릴 수도 있지만 어느 순간 사고의 깊이가 깊어지고, 논리적으로 상황을 판단하여 해결해 나가는 모습을 발견할 수 있을 겁니다.
