티스토리 뷰

1. 알고 있는 자료구조의 종류에 대해 이야기 해보세요.

List(리스트), Linked List(링드 리스트), Array(배열), Stack(스택), Queue(큐), Dequeue(디큐), Tree(트리), Heap(힙), Graph(그래프)

2.Linked List에 대해 설명 해보세요

Linked List는 데이터와 다음 데이터를 가리키는 정보를 저장하고 있는 자료구조 입니다. 데이터를 추가 하기에 좋지만 데이터를 찾을(탐색) 때 순차적으로 찾아야 하기 때문에 검색 하는 것은 느립니다.

그래서 데이터의 입출력이 많을 때 Linked List를 사용 하는 것이 좋습니다.

3.Linked List를 구현 해보세요.

Linked List Class(클래스)를 구현 해보겠습니다.

기능은 add(), length(), display(), find(n), delete(n)를 구현 해보겠습니다.

add()에서는 먼저 값을 가지고 있는 node를 만들고 거기에 값을 먼저 넣습니다. 그리고 node를 Linked List에 넣습니다.
length()를 구현하는 이유는 Linked List의 길이를 알아야 길이보다 큰 index를 client가 요청 했을 때 처리를 할 수 있습니다.
display()는 Linked List에 어떤 data들이 들어있는지를 보여주는 기능입니다.
find(n)은 Client가 요청한 n번째 인덱스에 있는 값을 찾아서 return해줍니다.
delete(n)는 Client가 요청한 n번째 인덱스에 있는 값을 찾아서 지워줍니다.

https://github.com/Kyeongrok/python_algorithm/blob/master/chapter08_data_structure/01_linked_list/01_linked_list.py

Linked List Source Code는 위 링크에 있다.

4. Stack

Stack은 First In Last Out의 구조로서 나중에 넣은 것부터만 꺼낼 수 있습니다. 스택은 push(), pop(), top(), empty()이렇게 4가지 연산이 있습니다.

집어넣는 push()와 값을 빼는 pop()만 있으면 될 것 같지만 그렇지 않습니다. push()는 데이터를 집어넣는 것이라서 그냥 집어넣으면 됩니다만 pop()은 데이터를 빼는 것이라서 데이터를 못빼는 경우가 있기 때문에 이 경우를 처리 해주어야 합니다.

class Stack1():
    arr = []  # 스텍은 배열을 확장한 기능으로 배열을 선언해줍니다.

    def __init__(self, size=10000):
        self.st = [None] * size

만약 stack에 넣은게 아무것도 없는데 pop()연산을 하면 무언가 문제가 있겠지요? 그래서 pop()연산을 하기전에 stack이 비었는지를 먼저 확인 해주어야 이상이 없습니다. 파이썬에 기본으로 구현이 되어 있는 Stack은 없습니다. 대신 비슷하고 자주 사용 되는 deque가 있어서 deque를 예를 들어보면 deque에 데이터를 넣은 것이 없을 때 pop()을 하면 아래와 같은 에러가 납니다.

Traceback (most recent call last):
  File "C:/git/python/python_algorithm/stack/03_implement_stack.py", line 49, in <module>
    print(deque.pop())
TypeError: descriptor 'pop' of 'collections.deque' object needs an argument

그래서 보통은 스텍을 구현하는 연습을 할 때는 empty() 함수도 같이 만들어 줍니다.

먼저 push함수는 값을 받아서 stack에 넣는 함수가 되겠습니다.

def push(self, value):
    self.arr.append(value)

.push() 함수를 이렇게 만들어 보는 것을 생각 해볼 수 있습니다. append()를 쓰면 array의 길이를 size=10000과 같이 기본값을 만들어줄 필요도 없고 기본값을 줄 필요도 없습니다. 하지만 왜그랬을까요? 꼭 생각 해보시기 바랍니다.

스텍이라는 자료구조는 필요하기 때문에 만들어낸 것입니다. 풀이나 나무같이 자연적으로 이미 있었던 것은 아닙니다. 스텍이전에는 배열이 있었습니다. 배열만 있고 스텍은 없었습니다. 개수가 자연적으로 늘어나는 List자료구조는 배열 다음에 만들어진 것입니다.

배열은 원래 개수가 정해져 있는 것이 배열입니다. 그래서 위에서 1만개를 선언한 arr이라는 배열에 1만개가 가득 찼으면 더이상 넣을 수 없고 에러가 납니다. 위와 같이 arr.append()이 함수가 arr에 1만개가 가득 차있는 경우 실행되면 에러가 나겠지요. 근본적으로 arr에는 append함수가 없습니다. 특정 인덱스를 지정해서 넣어주는 기능 밖에 없습니다.

그래서 설계를 배열만 가지고 해야 합니다.

def push(data):
    self.arr[self.size] = data # size는 데이터를 넣기 이전의 값이므로 마지막번째 배열을 가리킬 수 있습니다
    self.size += 1    # 값을 넣었으니 size를 늘려줍니다.

그 다음은 pop함수 입니다.

def pop():

위와 같이 맨 위에 있는 값을 뽑는 것이기 때문에 parameter가 없습니다.

def pop():
    data = stack[self.size - 1] # 맨 위에 있는 값을 뽑아 줍니다
    self.size -= 1 # size에서 한개를 빼줍니다.
    return data

그런데 위와 같이 구현 하면 stack에 아무것도 없을 때 위에서 난 에러가 날 수 있습니다. 그래서 empty()연산을 만들어줘서 stack이 비어있는지를 check하는 함수를 구현 해줍니다.

def empty(self):
    if self.size <= 0:
        return True
    else:
        return False

위 empty함수는 size로 True False를 알려줍니다.

class Stack1():
    arr = []
    size = 0

    def __init__(self):
        self.arr = [None] * 10000

    def push(self, data):
        self.arr[self.size] = data
        self.size += 1

    def pop(self):
        if not self.empty():
            data = self.arr[self.size - 1]
            self.size -= 1
            return data
        else:
            return -1

    def top(self):
        if self.empty():
            return -1
        else:
            return self.arr[self.size - 1]

    def empty(self):
        if self.size <= 0:
            return True
        else:
            return False

실행

st = Stack1()

st.push(100)
print(st.empty())
print(st.top())
print(st.pop())
print(st.pop())
print(st.pop())

결과
False
100
100
-1
-1

 

스택 구현 동영상

www.youtube.com/watch?v=uasm-Rkwf7k&lc=UgzxL_KRVHqEvH5XNdZ4AaABAg

5. Hash Table에 대해 설명 해보세요.

자료를 저장하는 자료 구조입니다. 속도가 O(1)입니다.

def _get_hash(self, key):
    hash = 0
    for char in key:
        hash += ord(char)
    return hash % self.MAX

Hash함수로 데이터를 찾아주는 자료구조입니다. 위 hash함수는 array에 어떤 index에 저장되어 있는지 찾아주는 함수입니다. 위 function은 hash 를 lenth로 나눈 나머지를 return해줍니다.

 

파이썬 해쉬 내장 함수

name = 'chulsoo'

# hash() 내장 함수
result = hash(name)
print('hash():', result)

결과

hash(): 4693593564486633238

 

중복된 값이 있을 경우

names = ['a1', 'a2', 'a3', 'a1']

for name in names:
    print(hash(name))

 

결과


-7959435397520759096
-1514478829985476864
-3789710225198767182
-7959435397520759096

 

결과 해석

중복된 값이 있으면 같은 hash값이 나옵니다.

 

6. HashMap과 TreeMap의 차이점에 대해 설명 해보세요

HashMap은 Array의 index를 hash 함수를 통해 계산 합니다. 그래서 접근 속도가 O(n)입니다.

TreeMap은 Tree에 데이터를 저장 합니다. 속도는 O(log N)입니다.

TreeMap은 주소나 사전을 저장하는 경우에 사용하면 좋습니다. 아래 포스트에 Tree에 대해 조금 더 자세히 써놓았습니다.

krksap.tistory.com/1739

[

Python에서 주소로 Tree만들기 법정동코드, 행정동코드 바꾸는 예제

개요 자료구조로 tree를 쓰는 이유는 탐색 속도를 빠르게 하기 위함입니다. Tree를 쓰면 어떻게 빨라지는가 하면 내가 이미 타고온 반대쪽은 탐색을 하지 않아도 되기 때문에 속도가 O(log n)이 되는

krksap.tistory.com

](https://krksap.tistory.com/1739)

7. List와 Set의 차이점과 사용해본 경험

List에는 중복되게 들어갈 수 있지만 Set은 중복이 허용이 되지 않습니다다. List에 있는 데이터를 Set에 넣으면 중복이 제거됩니다. DB의 distinct연산을 하는 효과가 있습니다. 중복이 제거되기 때문에 set에 들어 있다면 고유성이 보장 됩니다. 그래서 중복에 대한 처리를 안해줘도 됩니다.

데이터를 수집, 처리 할 때 중복된 자료들이 수집이 될 수 있습니다. 하지만 결과는 중복되지 않아야 합니다. 그러면 중복된 데이터들을 set에 넣으면 중복이 된 데이터가 있더라도 set안에 들어가면 중복이 없어지기 때문에 중복이 없다는 것이 보장이 됩니다.

대상 id가 저장이 되어 있는 list와 완료된 id가 저장이 되어있는 list가 있을 때 완료가 되지 않은 id만 뽑을 때 대상이 저장이 되어 있는 list와 완료된 id가 저장이 되어있는 두개의 list를 한개의 set으로 합치면 중복을 제거 할 수 있습니다.

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함