자료구조와 알고리즘

1. 시간복잡도

---

시간복잡도란?

시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 게 좋은 소스입니다.

빅-오 표기법

시간 복잡도에는 여러 개념이 있지만 '아무리 많이 걸려도 이 시간 안에는 끝날 것'의 개념이 제일 중요합니다. 최악의 경우를 계산하는 방식을 빅-오 표기법이라고 부릅니다.

• 설명

(1) O(1) : 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.

(2) O(log₂ n) : 입력 데이터의 크기가 커질 수록 처리 시간이 로그만큼 짧아지는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.

(3) O(n) : 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있습니다.

(4) O(n log₂ n) : 데이터가 많아질 수록 처리시간이 로그 배만큼 더 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 됩니다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적입니다.

(5) O(n²) : 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프가 대표적입니다.

(6) O(2ⁿ) : 데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.

• 시간복잡도 줄이는 법

  시간 복잡도에서 반복문이 가장 시간 소모에 큰 영향을 미칩니다. 그렇기에 시간 복잡도를 줄이는 방법은 반복문의 숫자를 줄이는 것입니다.

  또 다른 방법은 자료구조를 적절하게 이용하는 방법입니다.

  마지막 방법은 알고리즘을 적절하게 이용하는 것입니다. 대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등이 있습니다.

2. 배열과 링크드 리스트의 차이

---

결론은 데이터의 접근과 탐색이 중요하다면 배열을 써야하고 데이터의 추가, 삭제가 중요하다면 연결리스트를 써야합니다.

• 연결리스트와 배열의 차이

  먼저 배열은 정적인 자료구조입니다. 왜 정적이냐면 배열을 만들기 위해서는 미리 그 크기를 정해놔야하기 때문입니다. 한번 크기를 정해놓으면 크기 수정이 불가하고 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있습니다. 하지만 연속된 메모리 주소를 할당받기 때문에 생기는 큰 장점이 있는데, 데이터가 순차적으로 저장되기 때문에 데이터가 인덱스를 가지게 되면서 임의 접근이 가능해집니다.

  반면에, 연결리스트는 동적인 자료구조입니다. 정적이 아닌 동적인 이유는 연결리스트는 크기를 미리 정할 필요가 없기 때문입니다. 연결리스트에는 노드가 존재하는데, 그 노드에는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소를 가지고 있습니다. 따라서 데이터들이 배열처럼 연속적으로 메모리에 저장되어 있지 않고 서로 떨어져 있어도 선형구조로 데이터를 저장할 수 있다는 장점이 있습니다. 이 장점은 곧 크기의 제한이 걸리지 않는다는 점이 되고 이 때문에 데이터 추가, 삭제가 굉장히 자유로워집니다. 하지만 연결리스트는 배열처럼 연속적으로 메모리 주소를 할당받지 않기 때문에 임의 접근이 불가능합니다. 때문에 연결리스트가 데이터를 탐색하는 방식은 순차접근 방식을 사용합니다.

• 연결리스트와 배열의 시간복잡도 차이

  경우에 따라 연결리스트와 배열 중 더 좋은 성능이 결정됩니다.

  1) 데이터 탐색

  연결리스트 : 순차 접근 방식을 사용하기 때문에 어떤 한 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 합니다. 따라서 O(n)의 시간복잡도를 가집니다.

  배열 : 임의 접근 방식을 사용하기 때문에 데이터를 탐색할 때 처음부터 찾을 필요가 없습니다. 인덱스 번호가 있기 때문에 인덱스를 통해서 매우 빠르게 탐색할 수 있습니다. 이 때 배열은 O(1)의 시간복잡도를 가집니다.

  2) 데이터 추가, 삭제

  연결리스트 : 데이터를 추가하는 행위 자체의 시간복잡도는 O(1)입니다. 노드가 가지고 있는 메모리 주소 값만 갈아 끼워주면 되기 때문입니다. 다만, 추가하려는 데이터의 위치가 맨 처음이 아니고 그 이후라면 순차적으로 탐색하면서 해당 위치까지 가야합니다. 이 때 발생하는 시간복잡도가 O(n)입니다. 따라서 크게 두가지로 나눠볼 수 있습니다.

  1. 추가하려는 데이터의 위치가 맨 앞이라면, O(1)의 시간복잡도를 가진다.

  2. 추가하려는 데이터의 위치가 맨 앞 그 이후라면 O(n)의 시간복잡도를 가진다.

     ---

     배열 : 배열의 경우에는 데이터들이 순차적으로 저장되어있습니다. 따라서 맨 처음이나 그 이후에 데이터가 추가될 경우 그 뒤에 있는 데이터들을 전부 한 칸씩 뒤로 미뤄야 합니다. 여기서 시간복잡도가 O(n)입니다. 만약에 배열에 공간이 남아 있고 데이터를 맨 뒤에 추가한다면 이 때는 O(1)입니다.

  3. 추가하려는 데이터가 맨 뒤가 아니라면, 추가되는 데이터 위치 이후에 있는 모든 데이터들을 한 칸씩 미뤄야하므로 O(n)의 시간복잡도를 가집니다.

  4. 추가하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면, O(1)의 시간복잡도를 가집니다.

3. Hash Function, HashTable에 대해서 설명해주세요.

---

해시 테이블이란? 연관 배열의 일종으로, 키를 값에 매핑할 수 있는 자료구조입니다.

장점 : 삽입, 삭제, 탐색 시간이 빠릅니다.

단점 : 순서가 보장되지 않습니다.

• 해시 테이블 관련 용어

  해시 테이블 : 연관 배열의 구현 형태로 해시, 해시 함수, 해싱, 버킷, 슬롯 등의 개념을 포함합니다.

  버킷과 슬롯 : 해시 테이블에서 값은 버킷(bucket)과 슬롯(slot)으로 이루어진 형태의 테이블에 저장된다.

  (이 테이블 자체를 버킷이라고 표현 하기도 함)

  • 버킷(bucket) : 여러개의 슬롯을 저장하는 레코드 형태의 자료 구조로, 버킷의 갯수는 고정적이다.

  • 슬롯(slot) : 해시와 매핑되는 값이 저장되어 있는 공간으로, 하나의 버킷 안에는 여러개의 슬롯이 존재할 수 있다. 슬롯은 하나 이상의 값을 저장할 수 있다.

    해시(hash) : 해시 함수를 통해 얻는 값으로, 해시를 인덱스 또는 주소로 삼아 직접 접근이 가능하도록 합니다. 해시를 이용해서 해시 테이블의 버킷(bucket) 또는 슬롯(slot)에 접근한 뒤 탐색, 삽입, 삭제 등의 연산을 수행한다.

    해시 함수(hash function) : 임의의 길이의 데이터(key)를 고정된 길이의 데이터(해시)로 매핑하는 함수.

    이 때, 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시(hash)라고 한다. 즉, key -> hash로 매핑 시켜주는 함수를 해시함수라 한다.

    좋은 해시 함수의 조건

  • 해시 값이 해시 테이블 주소 영역 내에서 고르게 분포 되어야 한다.

  • 충돌이 적어야 한다. (중복값 최소화)

  • 계산이 빨라야 한다.

    해싱 : key -> hash -> value로 값을 탐색하는 과정으로, 해시 함수를 사용한 탐색을 가리켜 해싱이라고 한다. 해싱은 매우 빠른 검색을 위한 용도로 많이 사용된다. 평균적으로 O(1)의 탐색 시간을 갖는다. (충돌이 많을 경우 더 느려질 수 있다.)해싱의 성능은 해시 함수의 성능과 해시 테이블의 크기에 따라 달라진다.

    해시 충돌(hash collision) : 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 경우로,

    h(k1) == h(k2) 성립하면 해시 충돌이 발생 했다고 한다. (h : 해시함수. k1, k2 : 임의의 key값) 이때, k1, k2 를 동의어(synonym)라 한다. 해싱을 할 때, 해시 충돌이 발생할 수 있기 때문에 해시 충돌에 대한 처리가 반드시 필요하다.

    매우 큰 집합(ex : 가능한 모든 사람 이름)을 비교적 작은 크기의 공간(hash table size)에 매핑 시킬 때, 해시 충돌이 발생할 수 있다. 이 경우 table size가 입력 가능한 집합의 크기보다 작기 때문에 완전히 해시 충돌을 피할 수 있는 알고리즘은 존재하지 않는다. (비둘기집 원리)

• 해시 충돌 처리 방법

  1. Chaining : 해시 충돌이 일어나면 연결 리스트 형태로 이어 나가 충돌을 처리하는 기법

  2. Open adressing : 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식

     Chaining : chain처럼 연결되어 이어나간다는 의미로, 해시 충돌이 발생했을 경우 연결 리스트 형태로 이어 나간다. 충돌이 일어날 경우, 노드를 연결 시켜주시키 때문에 크기 제한에 있어서 자유롭다.

     Open adressing : 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 open addressing이라고 하는듯 하다. Closed hashing 이라고도 한다.Open hashing과 반대로 Slot 개수가 정해져 있어서(닫혀있는 형태라) Closed hashing이라고 하는듯하다.

     종류

  • 선형 조사법(Linear probing) : 해시충돌 시 고정폭(ex : 1칸)을 옮겨 다음 버킷을 조사하는 방법
  • 이차 조사법(Quadratic probing) : 해시충돌 시 제곱수 만큼 건너 뛰어 버킷을 조사하는 방법(1,4,9,...)
  • 이중 해싱(Double hashing) (or rehashing) : 충돌 시 다른 해시 함수를 적용하는 방법