[DAY 72] 코딩테스트 연습 - Binary Search Tree, DFS, BFS, Sorting algorithms

Binary Search Tree와 DFS, BFS의 개념을 이해한 후, 코드로 구현했다.

Selection sort, Insertion sort, Merge sort, Quick sort도 다루었다.

워밍업 문제

1. 정수 원소로 이루어진 리스트 numbers에 특정 정수 n이 포함된 횟수 카운트

from collections import Counter

Counter(numbers).get(n, 0)

collections 모듈의 Counter 함수를 사용하면 각 원소의 빈도를 반환한다.

numbers = [1,3,4,4,5,5,5,6]
Counter(numbers)

# 실행 결과
Counter({1: 1, 3: 1, 4: 2, 5: 3, 6: 1})

여기에 빈도수를 구하길 원하는 정수를 get 메소드의 인자로 넣어 값을 구하는 형태다.
두 번째 인자는 key 값이 존재하지 않는 경우 반환하는 default 값인 None을 반환하지 않고 원하는 값을 반환하도록 지정하는 것이다. 찾는 정수가 없는 경우 0을 반환하도록 지정했다.

numbers.count(n)

물론 위와 같은 형태로 더 간단하게 할 수 있지만, 의도적으로 collections 모듈 사용을 경험했다.


2. 정수 원소로 이루어진 리스트 numbers에서 특정 정수 n보다 큰 값 개수 카운트

len(list(filter(lambda x: x > n, numbers)))

filter, lambda를 활용했다. 두 함수는 코딩 테스트에서 활용도가 매우 높다고 한다.

numbers = [100, 130, 150, 190, 210, 250]
n = 190
len(list(filter(lambda x: x > n, numbers)))

# 실행 결과
2

numbers에서 190보다 큰 값의 개수는 2개다.


3. 정수 number의 각 자리 숫자 합계 (예시 : 4567 -> 22)

sum(map(int, str(number)))

각 자리 숫자를 더하기 위해 문자열로 변환을 생각해야한다. 그리고 map 함수를 사용했다.

sum(map(int, str(91115)))

# 실행 결과
17

9 + 1 + 1 + 1 + 5의 결과인 17이 출력된다.


4. 영어 소문자 혹은 숫자로 이루어진 문자열 alpha_num_string에서 숫자만 골라서 오름차순 리스트로 출력

answer = [int(s) for s in my_string if s.isdigit()]
sorted(answer)

list comprehension을 사용하여 숫자만 추출한 리스트를 answer에 저장하고 오름차순 정렬했다.

alpha_num_string = 'hi7hello3 world5'
answer = [int(s) for s in alpha_num_string if s.isdigit()]
sorted(answer)

# 실행 결과
[3, 5, 7]

숫자 7, 3, 5만 골라지며 오름차순 정렬되었다.

트리(Tree)

탐색을 위한 자료구조인 트리의 깊이, 레벨, 차수, 노드 등 개념을 익히고 BST(Binary Search Tree, 이진 탐색 트리)를 배웠다. 빠르게 지나갔어도 전공 지식으로 알던 내용이라 다행이었다.

출처 : https://blog.penjee.com/

BST와 정렬된 배열에 각각 같은 값이 들어있으며 27을 탐색하고 있다.
그러나 BST에선 3 steps, 정렬된 배열에선 10 steps로 BST가 탐색 시 훨씬 효율적임을 확인할 수 있다.

DFS(Depth First Search, 깊이 우선 탐색)과 BFS(Breadth First Search, 너비 우선 탐색)을 배운 후 파이썬 코드로 구현했다.

class Node:
    
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    
class Tree:
    
    def __init__(self, data):
        init = Node(data)
        self.root = init
        self.node_count = 0
    
    def __len__(self):
        return self.node_count
    
    def insert(self, data):
        new_node = Node(data)
        current = self.root
        
        while current:
            if data == current.data:
                return
            if data < current.data:
                if not current.left:
                    current.left = new_node
                    self.node_count += 1
                    return
                current = current.left
            if data > current.data:
                if not current.right:
                    current.right = new_node
                    self.node_count += 1
                    return
                current = current.right
        
    def DFS(self):
        # 깊이우선탐색, DFS(Depth First Search)
        # Stack 이용!
        result = [] # 방문경로
        stack = [self.root]
        while len(stack) != 0:
            dfs_current = stack.pop()
            if dfs_current.right:
                stack.append(dfs_current.right)
            if dfs_current.left:
                stack.append(dfs_current.left)
            result.append(dfs_current.data)
        return result
    
    def BFS(self):
        # 깊이우선탐색, BFS(Breadth First Search)
        # Queue 이용!
        result = []  # 방문경로
        queue = [self.root]
        while len(queue) != 0:
            bfs_current = queue.pop(0)
            if bfs_current.left:
                queue.append(bfs_current.left)
            if bfs_current.right:
                queue.append(bfs_current.right)
            result.append(bfs_current.data)
        return result

아래 코드를 통해 5, 3, 8, 1, 4, 6, 9를 차례로 insert한다.

t = Tree(5)
t.insert(3)
t.insert(8)
t.insert(1)
t.insert(4)
t.insert(6)
t.insert(9)

코드의 결과로 아래 그림과 같은 바이너리 트리가 생성된다.

 

t.DFS()  # [5, 3, 1, 4, 8, 6, 9]
t.BFS()  # [5, 3, 8, 1, 4, 6, 9]

깊이 우선 탐색과 너비 우선 탐색의 순회 순서를 꼭 이해하자. 코딩 테스트의 단골이다.

Sorting algorithms(정렬 알고리즘)

Selection sort(선택 정렬)
정렬 전 배열에서 최솟값을 찾는 것을 반복하여 정렬
성능이 좋지 않다

def get_min_index(origin_list):
    min_index = 0
    for i in range(1, len(origin_list)):
        if origin_list[i] < origin_list[min_index]:
            min_index = i
    return min_index

def selection_sort(origin_list):
    result = []
    while origin_list:
        min_index = get_min_index(origin_list)
        result.append(origin_list.pop(min_index))
    return result

Insertion sort(삽입 정렬)
정렬 전 배열에서 하나씩 꺼내 결과 배열에서 알맞은 위치를 찾아 삽입함으로써 정렬
성능이 좋지 않다

def get_insert_index(sorted_list, value):
    for i in range(len(sorted_list)):
        if value < sorted_list[i]:
            return i
    return len(sorted_list)

def insertion_sort(origin_list):
    sorted_list = []
    while origin_list:
        value = origin_list.pop(0)
        insert_index = get_insert_index(sorted_list, value)
        sorted_list.insert(insert_index, value)
    return sorted_list

Merge sort(병합 정렬)
Divide and Conquer(분할과 정복) 방식으로 정렬
성능이 좋다 : Best case, Worst case 모두 O(nlogn)

def merge_sort(origin_list):
    # divide
    if len(origin_list) <= 1:
        return origin_list
    
    middle = len(origin_list) // 2
    group1 = merge_sort(origin_list[:middle])
    group2 = merge_sort(origin_list[middle:])
    result = []
    
    # conquer
    while group1 and group2:
        if group1[0] < group2[0]:
            result.append(group1.pop(0))
        else:
            result.append(group2.pop(0))
    if group1:
        result.extend(group1)
    if group2:
        result.extend(group2)
    
    return result

Quick sort(퀵 정렬)
피봇값(pivot)을 기준으로 정렬
보통의 경우 성능이 좋으나 Worst case에서 O(n**2)

def quick_sort(origin_list):
    if len(origin_list) <= 1:
        return origin_list
    pivot = origin_list[-1]
    group1 = []
    group2 = []
    
    for i in range(len(origin_list)-1):
        if origin_list[i] < pivot:
            group1.append(origin_list[i])
        else:
            group2.append(origin_list[i])
            
    return quick_sort(group1) + [pivot] + quick_sort(group2)

강사님이 정렬을 시각적으로 확인할 수 있는 사이트를 알려 주셨다.
https://visualgo.net/en/sorting
Sorting 말고도 Linked list, Hash table, Tree 등도 애니메이션으로 보여주는 정말 유용한 사이트인 것 같다.