로또 번호 뽑기로 이해하는 자료구조와 시간복잡도

About this offer

지난 주말, 로또 5등(5천 원)에 당첨됐다. 회사에서 이 얘기를 하다가 개발팀 팀원들과 “로또 번호 뽑아주는 로직 어떻게 구현하면 좋을까?” 라는 이야기가 나왔다. 생각의 흐름은 다음과 같았다. 1부터 45까지의 숫자를 랜덤하게 뽑으려면 어떻게 해야 할까? 여기서 중복까지 없애려면? 이 로직을 가장 효율적으로 구현하려면 어떤 자료구조가 좋을까? 번호가 뽑힌 순서까지 기억할 수 있을까? 이런 질문들을 따라가다 보니 자연스럽게 Set, 배열, Linked List, 이진 탐색 트리까지 이야기가 이어졌다. 로또 번호를 뽑는 상황을 예시로 Set, 배열, Linked List, 이진 탐색 트리의 특징과 시간복잡도를 정리해보자. 로또는 1부터 45까지의 숫자 중 중복 없이 6개의 번호를 뽑는다. 로또 난수는 어떻게 만들까? JavaScript에서 난수를 만들 때는 Math.random() 을 사용할 수 있다. Math.random() Math.random() 은 0 이상 1 미만 의 숫자를 반환한다. 따라서 1~45 사이의 정수를 만들려면 다음과 같이 작성할 수 있다. Math.floor(Math.random() * 45) + 1 예를 들어 Math.random() 의 결과가 0.52 라면, 0.52 × 45 = 23.4 Math.floor(23.4) = 23 23 + 1 = 24 최종적으로 24 라는 번호를 얻는다. 하지만 여기에는 문제가 있다. 3 → 17 → 3 → 22 처럼 이미 뽑은 숫자가 다시 나올 수 있기 때문이다. 따라서 새로운 숫자를 뽑을 때마다 이미 뽑은 숫자인지 확인하는 과정 이 필요하다. 가장 먼저 떠오른 방법, Set 사용하기 난수를 뽑은 뒤 중복을 제거하는 가장 간단한 방법으로 Set 을 사용할 수 있다. JavaScript의 Set 은 중복된 값을 허용하지 않는 자료구조 다. const numbers = new Set(); while (numbers.size < 6) { const number = Math.floor(Math.random() * 45) + 1; numbers.add(number); } 3 이 이미 들어 있는 상태에서 다시 3 을 추가해도 numbers.add(3); numbers.add(3); Set 에는 하나의 3 만 남는다. Set { 3 } 따라서 로또처럼 중복되지 않는 값을 뽑는 상황에서는 굉장히 간단하게 구현할 수 있다. 특정 값이 이미 들어 있는지 직접 확인하고 싶다면 has() 를 사용할 수도 있다. if (numbers.has(number)) { // 이미 뽑은 번호 } JavaScript의 Set 은 일반적으로 해시 기반으로 구현되기 때문에 add , has , delete 같은 연산을 평균적으로 O(1) 에 처리할 수 있다. 즉, 단순히 로또 번호 6개를 뽑는 것이 목적이라면 사실 다음 정도로도 충분하다. const numbers = new Set(); while (numbers.size < 6) { numbers.add(Math.floor(Math.random() * 45) + 1); } console.log([...numbers]); 여기서 이야기가 끝났다면 자료구조 이야기까지 가지 않았을 것이다...! Set을 사용하지 않고 직접 중복 여부를 관리한다면? 값을 더 빠르게 찾으려면 어떤 자료구조를 사용할 수 있을까? 이 질문을 시작으로 배열과 이진 탐색 트리까지 이야기가 이어졌다. 배열에서 이미 뽑은 숫자를 찾는다면 지금까지 다음 숫자를 뽑았다고 해보자. [3, 7, 12, 20] 새롭게 12 가 나왔다면 배열을 탐색하여 이미 존재하는 값인지 확인할 수 있다. 3 → 아님 7 → 아님 12 → 발견 일반적인 배열 검색은 최악의 경우 배열의 모든 원소를 확인해야 한다. 따라서 시간복잡도는 O(N) 이다. 여기서 중요한 점은 배열이라고 해서 모든 연산이 O(1)은 아니라는 것 이다. arr[3] 처럼 인덱스를 알고 직접 접근한다면 O(1) 이지만, arr.find(...) 처럼 특정 값을 찾는 작업은 O(N) 이 걸린다. 이진 탐색 트리를 사용하면? 숫자를 이진 탐색 트리(Binary Search Tree)에 저장할 수도 있다. 예를 들어 다음과 같은 구조가 있다고 하자. 12 / \ 7 20 / 3 7 을 찾는다면, 7 < 12 → 왼쪽으로 이동 → 7 발견 과 같이 탐색할 수 있다. 균형 잡힌 이진 탐색 트리라면 탐색 시간복잡도는 O(log N) 이다. 배열의 O(N) 탐색보다 빠르다. 다만 모든 이진 탐색 트리가 항상 O(log N) 인 것은 아니다. 트리가 다음처럼 한쪽으로 치우친다면, 3 \ 7 \ 12 \ 20 결국 Linked List와 비슷한 구조가 되고 탐색 시간이 O(N) 까지 증가할 수 있다. 따라서 정확하게는 균형 이진 탐색 트리의 탐색 시간이 O(log N) 이라고 이해하면 된다. 그런데 로또 번호라면 O(1)로 확인할 수 있다 로또 번호에는 중요한 특징이 있다. 숫자의 범위가 1~45로 정해져 있다는 것 이다. 그렇다면 굳이 배열 안에서 값을 검색하거나 트리를 만들 필요가 없다. 처음부터 번호별 공간을 만들어두면 된다. const picked = Array(46).fill(false); 예를 들어 7 이 뽑혔다면 picked[7] = true; 로 저장한다. 이후 다시 7 이 나왔는지 확인할 때는 if (picked[7]) { // 이미 뽑힌 번호 } 처럼 바로 접근하면 된다. 배열의 특정 인덱스로 직접 접근하는 작업은 O(1) 이다. 즉, 배열에서 값 검색 O(N) 균형 이진 탐색 트리 O(log N) 인덱스를 이용한 직접 접근 O(1) 순으로 탐색 속도를 줄일 수 있다. 이 방법이 가능한 이유는 찾으려는 값의 범위를 미리 알고 있기 때문 이다. 뽑힌 순서도 저장해야 한다면? picked 배열만 이용하면 특정 번호가 뽑혔는지는 빠르게 알 수 있다. 하지만 이것만으로는 실제 번호가 7 → 3 → 20 → 12 순서로 뽑혔다는 사실을 알 수 없다. 즉, "7이 뽑혔는가?" 와 "7이 몇 번째로 뽑혔는가?" 는 서로 다른 문제다. 여기서 두 가지 요구사항이 생긴다. 특정 번호가 존재하는지 빠르게 찾고 싶다. 번호가 뽑힌 순서도 그대로 유지하고 싶다. 이 두 가지를 각각 효율적으로 처리하기 위해 Tree와 Linked List를 조합하는 방법도 생각해볼 수 있다. 트리는 특정 값을 빠르게 탐색하는 역할을 하고, 12 / \ 7 20 / 3 Linked List는 실제로 번호가 뽑힌 순서를 유지하는 역할을 한다. 7 → 3 → 20 → 12 즉 같은 데이터를 서로 다른 목적의 자료구조로 관리하는 것이다. Tree → 특정 값 탐색 Linked List → 번호가 뽑힌 순서 유지 하나의 자료구조로 모든 요구사항을 해결하려고 하기보다, 필요한 연산에 따라 여러 자료구조를 조합할 수 있다. 그렇다면 여기서 순서를 유지하는 역할을 맡은 Linked List는 어떤 구조일까? Linked List 나와주세요 Linked List는 각각의 데이터를 노드(Node)로 만들고 서로 연결하는 자료구조다. [7] → [3] → [20] → [12] 일반적인 단방향 Linked List의 노드는 다음 정보를 가진다. Node ├─ value └─ next 양방향 Linked List라면 이전 노드도 저장한다. NULL ← [7] ↔ [3] ↔ [20] ↔ [12] → NULL 각 노드는 대략 다음 정보를 가진다. value prev next Linked List의 가장 큰 장점 중 하나는 삽입과 삭제 다. 예를 들어 7 ↔ 3 ↔ 20 ↔ 12 에서 20 을 삭제한다고 하자. 3 과 12 를 직접 연결하면 된다. 7 ↔ 3 ↔ 12 즉, 배열처럼 뒤에 있는 데이터를 한 칸씩 당길 필요가 없다. 삭제할 노드의 위치를 이미 알고 있다면 Linked List의 삽입과 삭제는 O(1) 에 가능하다. 반면 배열 중간의 값을 삭제하면 뒤쪽 원소들을 이동시켜야 하므로 일반적으로 O(N) 이 걸린다. 단, 여기서 주의할 점이 있다. Linked List에서도 삭제할 노드를 먼저 찾아야 하는 상황이라면 탐색에 O(N)이 추가된다. 따라서 Linked List 삭제는 무조건 O(1) 이라고 외우는 것보다 삭제할 노드의 위치를 이미 알고 있다면 O(1) 이라고 이해하는 것이 정확하다. Linked List에서 세 번째 값을 찾는다면? Linked List가 다음과 같이 구성되어 있다고 하자. 7 → 3 → 20 → 12 세 번째 값을 찾으려면 어떻게 해야 할까? Linked List에서는 보통 첫 번째 노드인 head 를 가지고 있다. head ↓ 7 → 3 → 20 → 12 따라서 세 번째 노드를 찾기 위해서는 1번째 → 7 2번째 → 3 3번째 → 20 처럼 연결을 따라가야 한다. 일반화하면 N번째 노드를 찾는 데 O(N) 이 걸린다. 반면 배열에서는 const numbers = [7, 3, 20, 12]; numbers[2]; 처럼 인덱스로 바로 접근할 수 있다. 따라서 배열의 N번째 원소 접근은 O(1) 이다. 이 부분이 Array와 Linked List의 대표적인 차이점이다. Linked List에서 N번째 값을 더 빠르게 찾으려면? Linked List의 삽입·삭제 성능은 유지하면서 특정 번째 노드에도 빠르게 접근하고 싶다면 다른 자료구조를 함께 사용할 수 있다. 예를 들어 Linked List가 7 ↔ 3 ↔ 20 ↔ 12 이고, 별도의 배열에 각 노드를 가리키는 정보를 저장한다고 해보자. index[0] → 7번 노드 index[1] → 3번 노드 index[2] → 20번 노드 index[3] → 12번 노드 그러면 세 번째 노드를 찾을 때 index[2] 로 바로 접근할 수 있다. 즉, O(1) 접근이 가능해진다. 물론 이 경우에는 Linked List 하나만 사용하는 것이 아니라 Linked List + Array 를 함께 관리해야 한다. 사실 로또 예제처럼 번호를 뽑을 때마다 순서대로 뒤에 추가만 하는 상황이라면, 굳이 이렇게 두 자료구조를 조합할 필요 없이 배열 하나만으로도 순서 유지와 O(1) 인덱스 접근을 동시에 만족시킬 수 있다. 이 조합이 진짜 의미를 가지는 건 중간에 있는 값을 삭제해야 하는 상황이 추가될 때 다. 중간 노드를 삭제해도 Linked List는 앞뒤 연결만 바꾸면 되니 O(1)을 유지할 수 있지만, 배열은 삭제된 자리를 채우기 위해 뒤쪽 원소들을 당겨야 해서 O(N)이 걸린다. 이런 경우에 "삭제는 Linked List로 O(1)에, 인덱스 접근은 별도 배열로 O(1)에" 처리하는 조합이 필요해진다. 앞에서 Tree + Linked List 를 조합해 특정 값 탐색과 순서 유지 라는 서로 다른 역할을 나눴던 것처럼, 여기서는 Array + Linked List 를 조합해 빠른 인덱스 접근과 연결 관계 유지 라는 역할을 나눌 수 있다. Tree + Linked List → 특정 값 탐색 + 순서 유지 Array + Linked List → 빠른 인덱스 접근 + 순서 및 연결 관계 유지 실제 자료구조에서도 하나의 자료구조만 고집하기보다, 필요한 연산에 따라 여러 자료구조를 조합해서 사용할 수 있다. 물론 실제 로또 번호 6개를 뽑는 정도라면 여기까지 복잡하게 구성할 필요는 없다. 단순한 문제에서 벗어나 자료구조 각각의 특징과 트레이드오프를 하나씩 짚어보는 이야기로 번져 있었다. 그래서 이번 예제에서는 로또 로직 자체를 최적화하는 것보다, 요구사항이 하나씩 추가될 때 어떤 자료구조를 떠올릴 수 있는지 생각해보는 과정에 더 의미가 있었다. 정리 각 자료구조의 특징을 간단히 정리하면 다음과 같다. 자료구조 특정 값 탐색 N번째 원소 접근 중간 삽입/삭제 Array O(N) O(1) O(N) Set 평균 O(1) 직접적인 인덱스 접근 없음 평균 O(1) Linked List O(N) O(N) O(1)* 균형 이진 탐색 트리 O(log N) 일반적으로 직접 접근 불가 O(log N) 직접 인덱싱 O(1) 용도에 따라 다름 O(1) * Linked List의 삽입/삭제 O(1)은 대상 노드의 위치를 이미 알고 있다는 전제다. 결국 중요한 것은 어떤 자료구조가 무조건 가장 빠른지를 찾는 것이 아니다. 어떤 연산을 자주 해야 하는지를 기준으로 자료구조를 선택해야 한다. Array : 몇 번째 데이터인지 알고 빠르게 접근하고 싶을 때 Set : 중복 여부를 간단하고 빠르게 확인하고 싶을 때 Linked List : 중간 데이터의 삽입과 삭제가 자주 발생할 때 Tree : 특정 값을 효율적으로 탐색하고 싶을 때 직접 인덱싱 : 값의 범위가 작고 정해져 있어 값을 인덱스로 바로 사용할 수 있을 때 로또 예제처럼 값의 범위가 1~45 로 작고 고정되어 있다면 복잡한 트리를 만드는 것보다 45개의 공간을 미리 만들어두고 인덱스로 직접 접근하는 방식이 훨씬 단순하고 빠르다. 자료구조는 결국 데이터를 어떻게 저장하느냐보다, 그 데이터를 앞으로 어떻게 사용할 것인가에 따라 선택하는 것이 핵심이다. 이렇게 로또 번호 뽑아주는 로직을 기반으로 자료구조에 대해 뚱땅 알아보았다. 이제 당첨만 되면 된다. 이상 일확천금을 노리는 어느 개발자의 기록이었다.