writerq1

A star algorithm은 길찾기 알고리즘으로 유다시티 수업 마지막 프로젝트로도 나왔다.

생각보다 재밌는 알고리즘 이었다.

그리디 알고리즘으로도 길찾기 문제는 해결할 수 있는데, 사실상 효율적이지 않다는 문제가 있다.

start node 중심에서 원형으로 모든 가능성에 대해서 길찾기를 하게 됨으로

방향성을 가지고 길찾기를 할 수 있도록, 알고리즘에 약간의 수정을 해야 한다.

function = g + h

g = cost of the path

h = estimated distance to the goal

위의 function의 값이 최소화가 되는 방향으로 알고리즘을 짜는 문제다. 

아래는 내가 프로젝트로 냈었던 문제다. 피타고라스정리를 이용해서 거리를 계산해가고 있으며

그리디 알고리즘에 h 요소를 집어넣어 문제를 해결할 수 있었다.

def shortest_path(M,start,goal):
    explored = []
    frontiers = {}

    for neighbour in M.roads[start]:
        route = [start, neighbour]
        distance_from_start = math.sqrt((M.intersections[start][0] - M.intersections[neighbour][0])**2 + (M.intersections[start][1] - M.intersections[neighbour][1])**2)
        distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
        total_distance = distance_from_start + distance_to_goal
        frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    explored.append(start)

    while frontiers:
        smallest_frontier = sorted(frontiers.items(), key=lambda x: x[1].total_distance)[0]
        smallest_fron_key = smallest_frontier[0]
        explored.append(smallest_fron_key)
        if smallest_fron_key == goal:
            print("shortest path called")
            return smallest_frontier[1].route

        for neighbour in M.roads[smallest_fron_key]:
            if neighbour not in explored:
                route = smallest_frontier[1].route.append(neighbour)
                distance_from_start = smallest_frontier[1].distance_from_start + math.sqrt(
                    (M.intersections[smallest_fron_key][0] - M.intersections[neighbour][0])**2 + (M.intersections[smallest_fron_key][1] - M.intersections[neighbour][1])**2
                    )
                distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
                total_distance = distance_from_start + distance_to_goal
                if frontiers.get(neighbour) != None and total_distance > frontiers[neighbour].total_distance:
                    continue
                frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    if not frontiers:
        return -1

knapsack Problem

item 마다 weight 과 value가 있고, 정해진 weight limitation 하에 최적의 value를 구하는 문제.

모든 경우의 수를 다 따지려면 2의 n제곱 만큼의 time complexity가 필요하다.

dynamic programming은 문제를 나누어서 접근하는 방법으로 divide and conquere과도 비슷하다.

보통의 경우 lookup table을 두는데,

subproblem에 대한 solution들을 저장해 둔다.

추가 되는 경우의 수마다 최적값을 업데이트 해나가는데,,

내 생각에 이는 greedy 알고리즘과도 비슷하게 느껴졌다.

문제의 핵심은 problem을 subproblem으로 break down 할 수 있느냐는 부분.

def knapsack_max_value(knapsack_max_weight, items):
    
    # Initialize a lookup table to store the maximum value ($) 
    lookup_table = [0] * (knapsack_max_weight + 1)


    # Iterate down the given list
    for item in items:
        
        # The "capcacity" represents amount of remaining capacity (kg) of knapsack at a given moment. 
        for capacity in reversed(range(knapsack_max_weight + 1)):
            
            if item.weight <= capacity:
                lookup_table[capacity] = max(lookup_table[capacity], lookup_table[capacity - item.weight] + item.value)

    return lookup_table[-1]

What is graph

node(or vertex)사이의 관계를 나타낼 수 있는 자료구조.

tree도 graph의 한 종류라고 할 수 있다.

node 사이에는 연결선 (edge)가 존재한다.

graph는 root이 따로 없고, circle형태도 가능하다.

edge역시 data값을 지닐 수 있다. (보통 strength of connection, 예를 들어 거리)

**A star 알고리즘에서처럼 길찾기 알고리즘을 구현할 때 유용한 자료구조.

Directions and cycles

edge는 direction을 지닐 수 있고 아닐 수도 있다. (한방향만으로만 연결된 node)

cycle은 infinite loop의 가능성을 준다.

Connectivity

모든 노드가 edge로 연결되어 있어야 하는 것이 아니기 때문에,

연결이 끊긴 node가 있을 수 있다. disconnected graph.

연결이 끊긴 node끼리 그래프를 만들수도 있다.

최소한으로 몇개의 edge를 끊으면 disconnected graph가 되는지 개수를 세어서,

connectivity의 strength를 체크해볼 수 있다.

Graph representation

Object oriented language 를 사용하는 경우라면 node(vertex)나 edge를 object 형식으로 만들수 있다.

list 형식으로도 관리할 수 있는데

예를 들면 edge list, [[1,3],[2,4],[3,6] .... ]

노드의 아이디넘버를 통해 엣지를 리스트화 하는 방법.

adjacency list

[[1], [0,2,3], [1,3] ...]

리스트의 인덱스가 node 역할을 해서 인접한 노드를 list로 정리하는 방법.

adjacency matrix

3d 형태로 list안에 list를 넣는 방식.

Searching의 경우 tree와 비슷하게 stack와 queue를 활용할 수 있다.

DFS

def dfs_search(root_node, search_value):
    visited = set()                         # Sets are faster for lookups
    stack = [root_node]                     # Start with a given root node
    
    while len(stack) > 0:                   # Repeat until the stack is empty
            
        current_node = stack.pop()          # Pop out a node added recently 
        visited.add(current_node)           # Mark it as visited

        if current_node.value == search_value:
            return current_node

        # Check all the neighbours
        for child in current_node.children:

            # If a node hasn't been visited before, and not available in the stack already.
            if (child not in visited) and (child not in stack):         
                stack.append(child)

BFS

def bfs_search(root_node, search_value):
    visited = set()                           # Sets are faster while lookup. Lists are faster to iterate.
    queue = [root_node]
    
    while len(queue) > 0:
        current_node = queue.pop(0)
        visited.add(current_node)

        if current_node.value == search_value:
            return current_node

        for child in current_node.children:
            if child not in visited:          # Lookup
                queue.append(child)

매 step 마다 최적의 해를 구하면 최종적인 방식도 최적이 되는 재밌는 알고리즘.

매 스텝마다 최적의 해를 구한다는 의미로 greedy라는 표현을 쓴 것 같은데, 곰곰히 들여다볼수록 재미있는 부분이 많다.

코드를 확인해 보면, 결국 매step의 선택이 가장 최선의 선택임을 알 수 있다.

import sys

'''Find the shortest path from the source node to every other node in the given graph'''
def dijkstra(graph, source):
    
    result = {}
    result[source] = 0                 
    
    for node in graph.nodes:
        if (node != source):
            result[node] = sys.maxsize
            
    unvisited = set(graph.nodes)  
    
    path = {}

    '''THE GREEDY APPROACH'''
    # As long as unvisited is non-empty
    while unvisited: 
        min_node = None    
        
        # 1. Find the unvisited node having smallest known distance from the source node.
        for node in unvisited:
            if node in result:
                
                if min_node is None:       
                    min_node = node
                elif result[node] < result[min_node]:
                    min_node = node

        if min_node is None:
            break
            
        # known distance of min_node
        current_distance = result[min_node]
        
        # 2. For the current node, find all the unvisited neighbours. 
        # For this, you have calculate the distance of each unvisited neighbour.
        for neighbour in graph.neighbours[min_node]:
            if neighbour in unvisited:
                distance = current_distance + graph.distances[(min_node, neighbour)]
            
                # 3. If the calculated distance of the unvisited neighbour is less than the already known distance in result dictionary, update the shortest distance in the result dictionary.
                if ((neighbour not in result) or (distance < result[neighbour])):
                    result[neighbour] = distance

                    # 4. If there is an update in the result dictionary, you need to update the path dictionary as well for the same key.
                    path[neighbour] = min_node
        
        # 5. Remove the current node from the unvisited set.
        unvisited.remove(min_node)

    return result

bubble sort

매우 기본적인 sorting algorithm 이지만 time complexity가 좋진 않다.

log(n*2) 의 time complexity를 갖는다.

모든 element를 한번씩 다른 모든 element에 대하여 비교를 해야하기 때문에.

Merge sort

*divide and conquere 알고리즘의 일종으로도 볼 수 있다.

자료를 2개의 element끼리 나누어 comparison을 한 뒤에

합쳐서 4개의 그룹으로 만들고 다시 8개의 그룹으로 만드는 방식이다.

time complexity nlog(n)으로 bubble sort에 비해서 효율적.

def mergesort(items):

    if len(items) <= 1:
        return items
    
    mid = len(items) // 2
    left = items[:mid]
    right = items[mid:]
    
    left = mergesort(left)
    right = mergesort(right)
    
    return merge(left, right)
    
def merge(left, right):
    
    merged = []
    left_index = 0
    right_index = 0
    
    while left_index < len(left) and right_index < len(right):
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1

    merged += left[left_index:]
    merged += right[right_index:]
        
    return merged

Quick sort

pivot이 되는 element를 정한 후에

그 기준으로 크고 작음만 나누고, 해당 작업을 반복하는 알고리즘

worst case 에서는 n*2 의 time complexity가 걸리지만

average case 에서는 nlog(n)만큼 걸린다.

따라서 주어진 조건에 따라서 average case가 많이 발생할 만한 상황이면 유용할 수 있고,

더욱이 time은 merge sort에 비해서 많이 걸릴 수 있지만, space를 추가적으로 차지 하지 않는다는 장점이 있다. 

def sort_a_little_bit(items, begin_index, end_index):    
    left_index = begin_index
    pivot_index = end_index
    pivot_value = items[pivot_index]

    while (pivot_index != left_index):

        item = items[left_index]

        if item <= pivot_value:
            left_index += 1
            continue

        items[left_index] = items[pivot_index - 1]
        items[pivot_index - 1] = pivot_value
        items[pivot_index] = item
        pivot_index -= 1
    
    return pivot_index
    
    
 def sort_all(items, begin_index, end_index):
    if end_index <= begin_index:
        return
    
    pivot_index = sort_a_little_bit(items, begin_index, end_index)
    sort_all(items, begin_index, pivot_index - 1)
    sort_all(items, pivot_index + 1, end_index)
    
def quicksort(items):
    sort_all(items, 0, len(items) - 1)

Heap sort

heap tree와 heapify를 이용해서 루트에 있는 max 숫자를 가장 끝에 넣고

heapify후 나오는 그 다음 max를 그 다음에 넣고 계속 반복하는 방법.

강의자료가 잘 되어 있기 때문에 굳이 여기에 옮겨 쓰진 않음.

*sorting 폴더가 아니라 heap 폴더에 강의자료 있음

Binary Search

-기존의 array를 half로 나눠가며 search하는 algorithm

time complexity는 따라서 log(n)이다 (로그의 밑변은 2)

-array가 sorting 되어 있다는 전제하에 사용되며, 그렇지 않은 경우에는 sorting algorithm을 활용해서 먼저 sorting을

해주어야 한다.

-같은 로직으로 반복적으로 half로 쪼개기 때문에 recursive function을 활용하기 좋다.

Trie

-사전형식의 단어 저장이나, 자동완성, url 주소 정리에 좋은 자료구조

나의 경우에는 trie로 url 주소 정리를 하니 편했었다.

Heaps

tree의 한 종류로서 parent가 child보다 무조건 크거나(max heap) 작아야 한다.(min heap)

반드시 binary tree일 필요는 없으나 보통 binary를 가정하고,

complete tree임을 가정한다. (node가 하나의 레벨별로 왼쪽에서 오른쪽으로 늘어나는 형태)

heapify

- insertion이 있는 경우에 max나 min의 property가 깨지는 경우가 있다. 이러한 경우에 tree rotation이 일어나는데 이를 heapify 라고 한다.

Complete tree이므로 array 형식으로도 표현할 수 있다.

heapify 는 상당히 복잡한 형태의 로직인데 강의 쥬피터노트북과 아래 코드를 다시 정독해볼것.

class Heap:
    def __init__(self, initial_size=10):
        self.cbt = [None for _ in range(initial_size)]  # initialize arrays
        self.next_index = 0  # denotes next index where new element should go

    def insert(self, data):
        # insert element at the next index
        self.cbt[self.next_index] = data

        # heapify
        self._up_heapify()

        # increase index by 1
        self.next_index += 1

        # double the array and copy elements if next_index goes out of array bounds
        if self.next_index >= len(self.cbt):
            temp = self.cbt
            self.cbt = [None for _ in range(2 * len(self.cbt))]

            for index in range(self.next_index):
                self.cbt[index] = temp[index]

    def remove(self):
        if self.size() == 0:
            return None
        self.next_index -= 1

        to_remove = self.cbt[0]
        last_element = self.cbt[self.next_index]

        # place last element of the cbt at the root
        self.cbt[0] = last_element

        # we do not remove the elementm, rather we allow next `insert` operation to overwrite it
        self.cbt[self.next_index] = to_remove
        self._down_heapify()
        return to_remove

    def size(self):
        return self.next_index 

    def is_empty(self):
        return self.size() == 0

    def _up_heapify(self):
        # print("inside heapify")
        child_index = self.next_index

        while child_index >= 1:
            parent_index = (child_index - 1) // 2
            parent_element = self.cbt[parent_index]
            child_element = self.cbt[child_index]

            if parent_element > child_element:
                self.cbt[parent_index] = child_element
                self.cbt[child_index] = parent_element

                child_index = parent_index
            else:
                break

    def _down_heapify(self):
        parent_index = 0

        while parent_index < self.next_index:
            left_child_index = 2 * parent_index + 1
            right_child_index = 2 * parent_index + 2

            parent = self.cbt[parent_index]
            left_child = None
            right_child = None

            min_element = parent

            # check if left child exists
            if left_child_index < self.next_index:
                left_child = self.cbt[left_child_index]

            # check if right child exists
            if right_child_index < self.next_index:
                right_child = self.cbt[right_child_index]

            # compare with left child
            if left_child is not None:
                min_element = min(parent, left_child)

            # compare with right child
            if right_child is not None:
                min_element = min(right_child, min_element)

            # check if parent is rightly placed
            if min_element == parent:
                return

            if min_element == left_child:
                self.cbt[left_child_index] = parent
                self.cbt[parent_index] = min_element
                parent = left_child_index

            elif min_element == right_child:
                self.cbt[right_child_index] = parent
                self.cbt[parent_index] = min_element
                parent = right_child_index

    def get_minimum(self):
        # Returns the minimum element present in the heap
        if self.size() == 0:
            return None
        return self.cbt[0]

Red Black tree

-self balancing tree 중에 가장 유명한 tree

여러 성질을 부여해서 unbalance 되지 않도록, complete한 형태로 유지되도록 한다.

자세한 사항은 jupyter notebook과 강의 동영상 참고할것. (여기에 정리해놓을 필요는 없어 보임)

What is tree?

실제 Tree처럼 root와 branch와 같은 node로 구성되어 있는 자료구조.

*사이클이나, 연결이 안된 node가 있으면 안된다.

Level(각각의 층위) Root(가장 꼭대기 node), Leaf(가장끝단의 node), Height(leaf로 부터의 높이), depth(root로 부터의 깊이)

Tree traversal

-Depth First Search

각 node의 children 부터 먼저 search 하는 것이 priority가 된다.

-Breadth First Search

각 레벨부터 순차대로 search하는 순서다.

-Binary tree

tree where parent node can have two childeren at most.

-Search

보통 모든 노드를 다 지나가야 하기 때문에 O(n)의 time complexity를 갖는다.

-Delete

delete의 경우 leaf가 아닌 node를 지울 경우에 childeren을 어떻게 다시 연결할 것인지 로직을 정해야 한다.

-Insert

비어있는 node를 발견해서 insert하는 방식

Binary Search Tree

-childe node가 2개 이하여야 하는 binary tree인데, 추가적으로 왼쪽의 노드가 오른쪽의 노드보다 무조건 작아야 한다.

-Search에 걸리는 시간이나 insert를 위해서 자리를 찾아가는 time complexity가 O(log(n))으로 효율화 된다.

Actual Code Practice

-DFS (아래와 같이 stack을 이용해서 tracking을 해서 구현할 수 있다.)

def pre_order_with_stack(tree, debug_mode=False):
    visit_order = list()
    stack = Stack()
    node = tree.get_root()
    visit_order.append(node.get_value())
    state = State(node)
    stack.push(state)
    count = 0
    while(node):
        if debug_mode:
            print(f"""
loop count: {count}
current node: {node}
stack:
{stack}
            """)
        count +=1
        if node.has_left_child() and not state.get_visited_left():
            state.set_visited_left()
            node = node.get_left_child()
            visit_order.append(node.get_value())
            state = State(node)
            stack.push(state)

        elif node.has_right_child() and not state.get_visited_right():
            state.set_visited_right()
            node = node.get_right_child()
            visit_order.append(node.get_value())
            state = State(node)

        else:
            stack.pop()
            if not stack.is_empty():
                state = stack.top()
                node = state.get_node()
            else:
                node = None
            
    if debug_mode:
            print(f"""
loop count: {count}
current node: {node}
stack:
{stack}
            """)
    return visit_order

recursive function을 활용하면 아주 간단히 구현이 가능하다.

def pre_order(tree):
    
    visit_order = list()
    
    def traverse(node):
        if node:
            # visit the node
            visit_order.append(node.get_value())
            
            # traverse left subtree
            traverse(node.get_left_child())
            
            # traverse right subtree
            traverse(node.get_right_child())
    
    traverse(tree.get_root())
    
    return visit_order

반면에 bfs 같은 경우에는 queue 구조를 활용해서 구현이 가능하다.

def bfs(tree):
    q = Queue()
    visit_order = list()
    node = tree.get_root()
    q.enq(node)
    while(len(q) > 0):
        node = q.deq()
        visit_order.append(node)
        if node.has_left_child():
            q.enq(node.get_left_child())
        if node.has_right_child():
            q.enq(node.get_right_child())

    return visit_order

binary search tree의 경우 comparison function을 넣음으로써 구현 가능하다.

# Solution
class Tree():
    def __init__(self):
        self.root = None
        
    def set_root(self,value):
        self.root = Node(value)
        
    def get_root(self):
        return self.root
    
    def compare(self,node, new_node):
        """
        0 means new_node equals node
        -1 means new node less than existing node
        1 means new node greater than existing node 
        """
        if new_node.get_value() == node.get_value():
            return 0
        elif new_node.get_value() < node.get_value():
            return -1
        else:
            return 1
    
    def insert(self,new_value):
        new_node = Node(new_value)
        node = self.get_root()
        if node == None:
            self.root = new_node
            return
        
        while(True):
            comparison = self.compare(node, new_node)
            if comparison == 0:
                # override with new node
                node = new_node
                break # override node, and stop looping
            elif comparison == -1:
                # go left
                if node.has_left_child():
                    node = node.get_left_child()
                else:
                    node.set_left_child(new_node)
                    break #inserted node, so stop looping
            else: #comparison == 1
                # go right
                if node.has_right_child():
                    node = node.get_right_child()
                else:
                    node.set_right_child(new_node)
                    break # inserted node, so stop looping
                    
                    
    def search(self,value):
        node = self.get_root()
        s_node = Node(value)
        while(True):
            comparison = self.compare(node,s_node)
            if comparison == 0:
                return True
            elif comparison == -1:
                if node.has_left_child():
                    node = node.get_left_child()
                else:
                    return False
            else:
                if node.has_right_child():
                    node = node.get_right_child()
                else:
                    return False

Recursion

자료구조는 아니지만, 자료구조나 알고리즘과 같이 활용하기에 유용한 툴이다.

특히나 Tree searching 같은 경우에 recursion을 이용하면 아주 효율적으로 코드를 짤 수 있다.

(아주 신기했음)

function recursive(input):
	if input <=0:
		return input
	else:
		output = recursive(input -1)
		return output

첫 두줄이 base code 아래 두 줄이 recursion call이라고 볼 수 있다.

base code에는 주로 recursion이 끝나는 조건이 들어가 있다.

아래는 재밌었던 문제 중에 가장 재밌었던 staircase 문제

Q. Suppose there is a staircase that you can climb in either 1 step, 2 steps, or 3 steps. In how many possible ways can you climb the staircase if the staircase has n steps?

def staircase(n):
    if n <= 0:
        return 1
    
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    
    return staircase(n - 1) + staircase(n - 2) + staircase(n - 3)

경우의 수를 항상 3가지로 나누어생각해 볼 수 있는데,

마지막 스텝에 1칸을 움직이느냐, 혹은 2칸, 3칸을 움직이느냐로 나눠볼 수 있다.

이 세가지 경우의 수는 서로 겹치지 않는 경우의 수이기 때문에,

이를 응용해서 recursive function을 만들면 경우의 수를 쉽게 구할 수 있다.

Stacks

영어 단어 그대로의 stack과 같다.

아래부터 쌓여 있는 자료구조로서, 가장 위에 있는 element를 pop하거나 push할 수 있다.

Last In First Out 구조이다.

stack 자료구조와 recursive function을 이용해서 stack을 reversing하는 예시

class LinkedListNode:

    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:

    def __init__(self):
        self.num_elements = 0
        self.head = None

    def push(self, data):
        new_node = LinkedListNode(data)
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.num_elements += 1

    def pop(self):
        if self.is_empty():
            return None
        temp = self.head.data
        self.head = self.head.next
        self.num_elements -= 1
        return temp

    def top(self):
        if self.head is None:
            return None
        return self.head.data

    def size(self):
        return self.num_elements

    def is_empty(self):
        return self.num_elements == 0

def reverse_stack(stack):
    holder_stack = Stack()
    while not stack.is_empty():
        popped_element = stack.pop()
        holder_stack.push(popped_element)
    _reverse_stack_recursion(stack, holder_stack)


def _reverse_stack_recursion(stack, holder_stack):
    if holder_stack.is_empty():
        return
    popped_element = holder_stack.pop()
    _reverse_stack_recursion(stack, holder_stack)
    stack.push(popped_element)

Queues

역시 영어 단어 그대로 queue라고 할수 있다.

First in First out의 자료구조다.

Head와 Tail을 계속 tracking 하며, enqueue할시에는 tail쪽에 add되고

dequeue의 경우 head가 delete된다.

Dequeue

라는 자료구조의 경우 head와 tail양쪽에서 모두 enqueue와 dequeue할수 있도록 되어있다.

queue와 stack을 합친 자료 구조라고 볼 수 있다.

Priority queue

개별 node에 priorty를 부여해서 remove하는 순서를 정해놓을 수 있다.

Queue자료 구조와 reverse하는 예시코드

class LinkedListNode:

    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:

    def __init__(self):
        self.num_elements = 0
        self.head = None

    def push(self, data):
        new_node = LinkedListNode(data)
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self.num_elements += 1

    def pop(self):
        if self.is_empty():
            return None
        temp = self.head.data
        self.head = self.head.next
        self.num_elements -= 1
        return temp

    def top(self):
        if self.head is None:
            return None
        return self.head.data

    def size(self):
        return self.num_elements

    def is_empty(self):
        return self.num_elements == 0


        
class Queue:

    def __init__(self):
        self.head = None
        self.tail = None
        self.num_elements = 0

    def enqueue(self, data):
        new_node = LinkedListNode(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.num_elements += 1

    def dequeue(self):
        if self.is_empty():
            return None
        temp = self.head.data
        self.head = self.head.next
        self.num_elements -= 1
        return temp

    def front(self):
        if self.head is None:
            return None
        return self.head.data

    def size(self):
        return self.num_elements

    def is_empty(self):
        return self.num_elements == 0

def reverse_queue(queue):
    stack = Stack()
    while not queue.is_empty():
        stack.push(queue.dequeue())

    while not stack.is_empty():
        queue.enqueue(stack.pop())

유다시티 수업 datastructure and algorithm의 study note입니다.

Arrays and python lists

array와 list의 가장 큰 차이점은 둘은 array의 경우 index가 있고, list는 없다는 것이다.

실제로 메모리를 할당받을때도 array는 메모리공간의 바로 옆에 데이터가 할당되고, list는 아무 공간에나 저장이 된다.

array의 경우 adding 이나 deleting 하는게 time complexity가 좋지 않다. (인덱스를 다 조정해주어야 하기 때문에)

*python에서는 list도 index를 갖기 때문에 그 구분이 애매하다.

Linked list

각각의 element가 다음 element에 대한 reference가 있다.

따라서 insertion이나 deleting할대 time complexity가 constant하다.

(모든 element를 iterate할 필요가 없고, reference만 pointing을 바꿔주면 되기 때문에)