자료구조 - 해시테이블, 트리, 힙

자료구조에는 꼭 익혀야하는 독수리 5형제가 있다. 연결리스트, 스택, 큐, 해시테이블, 힙

그 중 해시테이블, 힙에 대해서 공부해보자.

해시테이블(HashTable)

해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조이다. (Dictionary를 생각하면 편하다.)

빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.

이때, 각각의 Key 값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 예를 들어 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다면, index = 해시함수("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "521-1234"로 전화번호를 저장하게 된다.

이러한 해싱구조로 데이터를 저장하면 Key 값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. -> O(1)

트리(Tree)

트리는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙(최대힙, 최소힙) 등 매우 다양한 트리가 있지만, 이진 트리와 완전 이진 트리에 대해서 알아보자.

 

이진 트리(Binary Tree)는 바로 각 노드가 최대 두 개의 자식을 가지는 트리이고, 완전 이진 트리는 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. 즉, Leaf 노드를 제외하고는 두 개의 자식 노드를 가지고 있어야 한다.

 

트리 구조는 완전 이진 트리를 쓰는 경우에 배열로 저장할 수 있다.(편의성을 위해 0번째 인덱스는 사용되지 않는다.)

Level 0 -> [None, A]

Level 1 -> [None, A, B, C]

Level 2 -> [None, A, B, C, D, E, F, G]

Level 3 -> [None, A, B, C, D, E, F, G, H, I] 를 넣으면 된다.

 

역으로 이 배열을 활용해서 트리 구조를 분석해보자.

 

1. 왼쪽 자식의 인덱스 : 현재 인덱스 * 2

2. 오른쪽 자식의 인덱스 : 현재 인덱스 * 2 + 1

3. 부모의 인덱스 : 현재 인덱스 //2 (나눗셈 몫)

 

각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k 개이다. 만약 높이가 h인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는 2^(h+1) -1 개이다.

즉, 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log2(N+1) -1 이므로 이진 트리 높이는 최대 O(log(N))이구나!를 알 수 있다. => 이후에 힙의 시간복잡도 계산에 사용된다 !

힙(Heap)

힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리이다. 

항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료 구조로, BST(이진탐색트리)와 다르게 좌, 우 자식의 위치가 대소관계를 반영하지는 않는다.

데이터 삽입 시, 다음과 같이 이루어진다.

1. 원소를 맨 마지막에 넣는다.

2. 부모 노드와 비교하여 만약 자식이 더 크다면 자리를 바꾼다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때 까지 2. 과정을 반복한다.

 

결국, 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있다. 즉, 힙의 원소 추가는 O(log(N))만큼의 시간복잡도를 가진다! 

 

데이터 추출(삭제) 또한, 다음과 같이 이루어진다.

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 반환 및 삭제한다.

3. 변경된 노드를 더 큰 자식 노드와 비교한다. (왼쪽 자식과 오른쪽 자식 중 더 큰 자식과 변경한다.)

4. 가장 아래 레벨에 도달할 때까지 3.을 반복한다.

 

원소 추출 또한, O(log(N)) 만큼의 시간복잡도를 가진다.

2주차 과제

후위 표기법 계산하기

후위표기법은 3+5*2 => 352*+ , 3*5+2 => 35*2+ 처럼 이미 연산자 간 우선순위가 모두 고려된 상태이다. 이를 위해서는 피연산자를 저장할 스택이 필요하다.

• 피연산자(숫자)는 스택에 넣는다.
• 연산자는 스택에서 두 개의 숫자를 꺼내서 계산한다.
• 연산된 숫자는 스택에 다시 넣는다.

 * 공백을 기준으로 숫자가 구분되어 있으므로, num이라는 변수에 숫자를 저장했다가 공백을 만나면 스택에 저장해주었다.

#Q2-2. 후위표기법 계산하기
inputStr = input()
stack = []
num = ''
operations = ['+','-','*','/']
for char in inputStr:
    # 공백인 경우
    # num이 있는 경우 숫자를 stack 에 push
    # num이 없는 경우(연산자 다음 공백) continue
    if char == ' ': 
        if len(num)<=0 : continue
        stack.append(int(num))
        num = ''
    # 연산자인 경우
    # 스택에서 두 개의 숫자를 pop 한 후 , 연산
    # 연산된 숫자를 스택에 push
    elif char in operations : 
        num1 = stack.pop()
        num2= stack.pop()
        if char == '+': stack.append(num2+num1)
        if char == '-': stack.append(num2-num1)
        if char == '*': stack.append(num2*num1)
        if char == '/': stack.append(num2/num1)
    # 숫자인 경우
    # num에 추가
    else: num+=char
print(int(stack.pop()))

중복 문자 없는 가장 긴 부분 문자열 찾기

먼저, 브루트포스로 접근해보면 start 포인터마다 end 포인터를 다 돌면서 해당 문자열의 중복여부을 체크하는 O(N^3) 방법이 있다. 물론 브루트포스보다 더 나은 방법을 생각해야한다.

 

해당 문제는 투포인터와 해시테이블을 이용하는 문제이다. 투포인터는 대표적으로 특정한 합을 가지는 부분 연속 수열 찾기 문제가 있는데, 시작점과 끝점을 모두 첫 번째 원소를 가르키도록 하고, 현재 부분합이 M보다 큰지 작은지에 따라 시작점과 끝점을 이동시키는 예제이다. 해당 문제 또한 substring을 뽑아내야하기 때문에 두 개의 포인터를 사용하여야 한다.

• start 포인터와 end 포인터 모두 0 인덱스부터 시작한다.
• end 포인터를 +1을 한다.
• used 해시테이블에 존재하는 알파벳이면(used.keys에 존재하고, 해당 Value 값이 start 보다 같거나 큰 경우)
  • start 인덱스를 used[char]+1로 갱신한다.
  • used 해시테이블을 갱신한다.
  • maxLength와 curLenth를 갱신한다.
• 중복되지 않은 알파벳이라면
  • curLength와 maxLength를 갱신한다.
  • used 해시테이블을 갱신한다.

#Q2-2. 중복 문자 없는 가장 긴 부분 문자열 찾기
inputStr = input()

# 투포인터(start,end)와 해시테이블(used), 그리고 maxLength를 초기화한다.
start = 0
end = 0
maxLength = 0
used = {}

if len(inputStr) == 0: 
    print(maxLength)

else:
    used[inputStr[end]] = end
    maxLength = 1
    curLength = 1

    # end가 문자열 끝까지 갈 때까지 반복문을 돌린다.
    while end<len(inputStr)-1:
        # end+=1을 한다.
        end+=1
        # used 해시테이블에 있는 문자인지 확인한다.
        if inputStr[end] in used.keys() and used.get(inputStr[end])>=start:
            # 중복된 문자이면 start 인덱스와 maxLength를 갱신한다.
            start = used.get(inputStr[start]) + 1
            used[inputStr[end]] = end
            if maxLength<curLength : maxLength = curLength
            curLength = end - start + 1
        else:
            # 중복되지 않은 문자이면 curLength와 used 해시테이블을 갱신한다.
            curLength+=1
            used[inputStr[end]] = end
            if maxLength<curLength : maxLength = curLength

print(maxLength)

 

reference) https://www.youtube.com/watch?v=cFUgQKyTda4