September 25, 2022

1. 큐

1.1 정의

큐(Queue)은 입력시 데이터에 대해서 순차적으로 저장합니다. 출력시 가장 먼저 저장된 데이터를 기준으로 출력됩니다. 이를 FIFO(First In First Out)구조로 저장하는 형식이라고 말합니다.

쉽게 이해하기 위해서 보통 줄서기를 예로 설명할 수 있습니다.
차례대로 줄을 서고(입력) 입장(출력) 순서는 가장 먼저 줄을 선 사람

입력을 ‘인큐(enqueue)’ 출력을 ‘디큐(dequeue)‘라고 표현합니다.

`python 사용법`	`설명`
queueList = [ ]	queue 생성
queueList.append(e)	입력
`queueList.pop(0)`	출력(가장 처음요소)

주의사항 List를 사용해 Queue를 사용하는 경우 출력시 가장 첫번째 요소를 출력하기 때문에 나머지 저장된 요소들이 모두 앞으로 한번 이동해야 되기 때문에 List의 크기가 크다면 비효율적입니다.

It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).
출처: Python 공식문서

따라서 자료집합의 형태가 크다면 collections의 사용을 고려해야 합니다.

from collections import deque
  queue = deque(["Eric", "John", "Michael"])
  queue.append("Terry")
  queue.append("Graham")
  print(queue.popleft())                 #'Eric'
  print(queue.popleft())                 #'John'
  print(queue)                           #deque(['Michael', 'Terry', 'Graham'])

1.2 코드구현

# 회문판단 Queue
"""
given :
  noPalindromeSentence = '기찻길'
  yesPalindromeSentence = '역삼역'

when :
  print(checkPalindromeWithQueue(noPalindromeSentence))
  print(checkPalindromeWithQueue(yesPalindromeSentence))

then :
  queue을 이용해 구현 되어야 하며
  반환값은 False, True가 되어야 한다

"""


def checkPalindromeWithQueue(sentence):

    queue = []
    reversedQueue = []
    for s in sentence:
        queue.append(s.lower())

    for s in reversed(sentence):
        reversedQueue.append(s.lower())

    while queue:
        if queue.pop(0) != reversedQueue.pop(0):
            return False

    return True


noPalindromeSentence = '기찻길'
yesPalindromeSentence = '역삼역'

print(checkPalindromeWithQueue(noPalindromeSentence))
print(checkPalindromeWithQueue(yesPalindromeSentence))

2. 스택

2.1 정의

스택(Stack)은 입력시 데이터에 대해서 순차적으로 저장합니다. 출력시 가장 나중에 저장된 데이터를 기준으로 출력됩니다. 이를 LIFO(Last In First Out)구조로 저장하는 형식이라 말합니다.

쉽게 이해하기 위해서 보통 접시 쌓기를 예로 설명할 수 있습니다.
차레대로 접시를 쌓고(입력) 꺼내기(출력) 순서는 가장 나중에 입력한 접시

입력을 ‘푸시(push)’ 출력을 ‘팝(pop)‘이라고 표현합니다.

`python 사용법`	`설명`
queueList = [ ]	stack 생성
queueList.push(e)	입력
`queueList.pop()`	출력(가장 마지막 요소)

2.1 코드구현

# 회문판단 Stack
"""
given :
  noPalindromeSentence = '기찻길'
  yesPalindromeSentence = '역삼역'

when :
  print(checkPalindromeWithStack(noPalindromeSentence))
  print(checkPalindromeWithStack(yesPalindromeSentence))

then :
  stack을 이용해 구현 되어야 하며
  반환값은 False, True가 되어야 한다

"""


def checkPalindromeWithStack(sentence):

    stack = []
    reversedStack = []
    for s in sentence:
        stack.append(s.lower())

    for s in reversed(sentence):
        reversedStack.append(s.lower())

    while stack:
        if stack.pop() != reversedStack.pop():
            return False

    return True


noPalindromeSentence = '기찻길'
yesPalindromeSentence = '역삼역'

print(checkPalindromeWithStack(noPalindromeSentence))
print(checkPalindromeWithStack(yesPalindromeSentence))

3. 딕셔너리

3.1 정의

딕셔너리(dictionary)은 키(key)와 값(value)으로 대응 관게를 저장하는 자료 구조입니다. Java의 HashMap과 유사합니다. HashTable을 기반으로 한 자료구조 입니다.

insertKey = Sandara Dee keys = 입력하고자 하는 전체 크기

위 그림처럼 입력하고자 하는 키에 대한 index는 index = hash_function(insertKey) % keys 통해서 index 값을 구해내고, buckets[keys]에 insertKey와 value를 저장합니다.

이러한 저장된 자료구조는 키에 대한 값을 찾을때 키를 기준으로 바로 index에 접근할 수 있기 때문에 O(1~n)의 시간복잡도를 가집니다. key를 기준으로 바로 접근하기 떄문에 시간복잡도는 O(1)이 됩니다. 하지만 hash_function을 통해 index를 구하는 과정에서 collistion(충돌)이 발생시 처리 과정에서 최악의경우 O(n)의 복잡도를 보이게 된다.

주의사항(collistion) python3.5 미만에서는 입력에 대한 key 삽입순서가 보장되지 않습니다. python dictionary의 collision(충돌) 처리 방식은 Open addressing방식 중 Linear Probing 방식을 사용하였기 때문에 key 입력에 대한 순서가 보장 되지 않습니다.

collistion : hash_function(insertKey) % keys의 값이 동일한 경우
Open addressing : 추가적인 메모리할당 없이 hash table array의 빈공간을 사용하는 방법입니다.
Linear Probing : Open addressing의 구현방식중 하나로 충돌이 발생했을 때, 충돌이 발생한 Index뒤에 버킷중 비어있는 곳에 할당하는 방식입니다.

d = {'a': 0, 'b': 1, 'c': 2}
l = d.keys()
print(l) #['a', 'c', 'b']

`python 사용법`	`설명`
dictionary = {}	dictionary 생성
dictionary[key] = value	해당 dictionary에 key가 있다면 value를 Update, 없다면 key,value를 Insert
del dictionary[key]	dictionary에서 해당 key삭제
dictionary.clear()	모든 key를 삭제합니다.

3.1 코드구현

"""
given :
  studentDict = {
      39: 'Justin',
      14: 'John',
      67: 'Mike',
      105: 'Summer',
  }

when :
  print(findNameById(39))

then :
  key가 존재하는경우 return true
  그렇지 않으면 false
"""
studentDict = {
    39: 'Justin',
    14: 'John',
    67: 'Mike',
    105: 'Summer',
}


def findNameById(key):
    if key in studentDict:
        return True

    return False


#print(findNameById(39)) # true
print(findNameById(20))  # false

4. 그래프

4.1 정의

노드(정점)과 에지(간선)를 이루어진 구조의 관계를 표현한 자료구조 입니다. 간단히 말하면 점 과 선 사이의 관계입니다.

그래프 용어정리

위 이미지를 참고 부탁드립니다.

`용어`	`설명`
정점(vertex)	노드(node),위치라 표현되며 실제 데이터가 저장되는 공간입니다. (A,B,C,D)
간선(edge)	노드 간의 관계. 즉, 노드(A,B,C,D)를 연결하는 선입니다.
인접 정점(adjacent vertex)	하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 말합니다. A의 인접 정점은 B, C, D 입니다.
차수(degree)	정점에 연결된 간선의 수를 뜻 합니다. 위 그래프에서 정점 A의 차수는 3입니다.
방향그래프	간선의 방향이 존재하는 그래프입니다. 해당 방향으로만 이동이 가능합니다.
진입차수(in-degree)	방향그래프에서 외부 노드에서 나가는 간선이 수를 뜻합니다.
진출 차수(out-degree)	방향그래프에서 외부 노드에서 들어오는 간선이 수를 뜻합니다.
인접 행렬 (Adjacency Materix)	그래프의 연결 관계를 이차원 배열로 나타내는 방식입니다.
인접 리스트 (Adjacency List)	그래프의 각 정점에 인접한 정점들을 연결리스트(Linked List)로 표현하는 방법이다.

4.2 코드구현

"""
# graph 인접행렬
given :
  정점  (A, B, C, D)
  무방향 간선 [(0,1),(0,2),(0,3),(2,3)
  주어졌을때

when :
  graph = adjacencyMatrix()
  graph.setVertex('A')
  graph.setVertex('B')
  graph.setVertex('C')
  graph.setVertex('D')

  graph.insertUndirectedEdge(0, 1)
  graph.insertUndirectedEdge(0, 2)
  graph.insertUndirectedEdge(0, 3)
  graph.insertUndirectedEdge(2, 3)

then :
  출력이 다음과 같아야 한다.
       A B C D

  A :  0 1 1 1

  B :  1 0 0 0

  C :  1 0 0 1

  D :  1 0 1 0

"""


class AdjacencyMatrix:

    def __init__(self):
        self.MAX_VTXS = 256
        self.size = 0
        self.vertices = []
        self.adjMatrix = []

    def getVertex(self, i):
        return self.vertices[i]

    def setVertex(self, node):
        if self.size > self.MAX_VTXS:
            return
        self.vertices.append(node)
        self.size = self.size + 1

    def getEdge(self, m, n):
        return self.adjMatrix[m][n]

    def setEdge(self, m, n, value):
        try:
            self.adjMatrix[m][n] = value
        except:
            self.adjMatrix.append([0 for i in range(len(self.vertices))])
            self.adjMatrix[m][n] = value

        try:
            self.adjMatrix[n][m] = value
        except:
            self.adjMatrix.append([0 for i in range(len(self.vertices))])
            self.adjMatrix[n][m] = value

    def insertUndirectedEdge(self, m, n):
        self.setEdge(m, n, 1)
        self.setEdge(n, m, 1)

    def drawGraph(self):
        print('    ', end=' ')
        for i in range(self.size):
            print(self.getVertex(i), end=' ')

        for i in range(self.size):
            print('\n')
            print(self.getVertex(i), ': ', end=' ')
            for j in range(self.size):
                print(self.getEdge(i, j), end=' ')
        print('\n')


#정점 삽입 (A, B, C, D)
graph = AdjacencyMatrix()
graph.setVertex('A')
graph.setVertex('B')
graph.setVertex('C')
graph.setVertex('D')

graph.insertUndirectedEdge(0, 1)
graph.insertUndirectedEdge(0, 2)
graph.insertUndirectedEdge(0, 3)
graph.insertUndirectedEdge(2, 3)

graph.drawGraph()

"""
# graph 인접리스트
given:
  3개 vertex(정점)과 (0,1) (0,2) 간선(edge)가 주어졌을때
when:
  V = 3
  graph = AdjacencyList(V)
  graph.addEdge(0, 1)
  graph.addEdge(0, 2)
  graph.drawGraph()
then:
  출력이 다음과 같아야 한다.

  vertext:0
  0 -> 2 -> 1

  vertext:1
  1 -> 0

  vertext:2
  2 -> 0
"""


class AdjacencyList:

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [None] * self.V

    def getLinkNode(self, data, pointer):
        return {'data': data, 'pointer': pointer}

    def addEdge(self, source, target):

        self.graph[source] = self.getLinkNode(data=target,
                                              pointer=self.graph[source])
        #if it is an undirected graph.
        self.graph[target] = self.getLinkNode(data=source,
                                              pointer=self.graph[target])

    def drawGraph(self):

        for i in range(self.V):
            print('vertext:{0}\n{0}'.format(i), end="")
            temp = self.graph[i]

            while temp:
                print(" -> {}".format(temp['data']), end="")
                temp = temp['pointer']
            print(' \n')


V = 3
graph = AdjacencyList(V)
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.drawGraph()

'''
DFS(Depth First Search)

given:
  6개 vertex(정점)과 (0,1), (0,2), (0, 3), (1, 2),(1, 3),(1, 4),(2, 0),(2, 4),(3, 0),
  (4, 1),(4, 5),(5, 2),(5, 4) 간선(edge)가 주어졌을때

when:
  V = 6
  dfsGraph = dfsWithAdjList(V)
  dfsGraph.addEdge(0, 2)
  dfsGraph.addEdge(0, 3)
  dfsGraph.addEdge(1, 2)
  dfsGraph.addEdge(1, 3)
  dfsGraph.addEdge(1, 4)
  dfsGraph.addEdge(2, 0)
  dfsGraph.addEdge(2, 4)
  dfsGraph.addEdge(3, 0)
  dfsGraph.addEdge(4, 1)
  dfsGraph.addEdge(4, 5)
  dfsGraph.addEdge(5, 2)
  dfsGraph.addEdge(5, 4)
  print(dfsGraph.display(1))


then:
 [1, 4, 5, 2, 0, 3]
'''

class dfsWithAdjList():

    def __init__(self, V):
        self.vertex = V
        self.graph = [[] for i in  range(self.vertex)]

    def addEdge(self, source, target):
        self.graph[source].append(target)

    def display(self, startNode):

        visited = []
        stack = [startNode]
        while stack:
            '''
              dfs에서 stack을 사용하는 이유는
              시작 vertex가 1인경우 아래와 같이 진행된다. 따라서 수직적으로 검색하기 위해서 queue를 사용해야한다.
              1st
              visited = [1]
              queue = [2,3,4]

              2st
              visited [1,4]
              queue = [3,4,5]

            '''
            n = stack.pop()

            if n not in visited:
                visited.append(n)

                stack += set(self.graph[n]) - set(visited)
        return visited


V = 6
dfsGraph = dfsWithAdjList(V)
dfsGraph.addEdge(0, 2)
dfsGraph.addEdge(0, 3)
dfsGraph.addEdge(1, 2)
dfsGraph.addEdge(1, 3)
dfsGraph.addEdge(1, 4)
dfsGraph.addEdge(2, 0)
dfsGraph.addEdge(2, 4)
dfsGraph.addEdge(3, 0)
dfsGraph.addEdge(4, 1)
dfsGraph.addEdge(4, 5)
dfsGraph.addEdge(5, 2)
dfsGraph.addEdge(5, 4)
print(dfsGraph.display(1))

'''
#bfs
given:
  6개 vertex(정점)과 (0,1), (0,2), (0, 3), (1, 2),(1, 3),(1, 4),(2, 0),(2, 4),(3, 0),(4, 1),(4, 5),(5, 2),(5, 4) 간선(edge)가 주어졌을때

when:
  V = 6
  bfsGraph = bfsWithAdjList(V)
  bfsGraph.addEdge(0, 2)
  bfsGraph.addEdge(0, 3)
  bfsGraph.addEdge(1, 2)
  bfsGraph.addEdge(1, 3)
  bfsGraph.addEdge(1, 4)
  bfsGraph.addEdge(2, 0)
  bfsGraph.addEdge(2, 4)
  bfsGraph.addEdge(3, 0)
  bfsGraph.addEdge(4, 1)
  bfsGraph.addEdge(4, 5)
  bfsGraph.addEdge(5, 2)
  bfsGraph.addEdge(5, 4)
  print(bfsGraph.display(1))


then:
 [1, 2, 3, 4, 0, 5]

'''
from collections import deque


class bfsWithAdjList():

    def __init__(self, V):
        self.vertex = V
        self.graph = [[] for i in range(self.vertex)]

    def addEdge(self, source, target):
        self.graph[source].append(target)

    def display(self, startNode):

        visited = []
        '''
          bfs에서 queue을 사용하는 이유는 bfs는 기준 노드 기준으로 인접 노드들을 탐색하나가게 됩니다.
          시작 vertex가 1인경우 아래와 같이 진행된다. 따라서 수평적으로 검색하기 위해서 queue를 사용해야한다.
          1st
           visited = [1]
           queue = [2,3,4]

          2st
           visited [1,2]
           queue = [3,4,0]

        '''
        queue = deque([startNode])

        while queue:
            n = queue.popleft()
            if n not in visited:
                visited.append(n)

                queue += set(self.graph[n]) - set(visited)
        return visited


V = 6
bfsGraph = bfsWithAdjList(V)
bfsGraph.addEdge(0, 2)
bfsGraph.addEdge(0, 3)
bfsGraph.addEdge(1, 2)
bfsGraph.addEdge(1, 3)
bfsGraph.addEdge(1, 4)
bfsGraph.addEdge(2, 0)
bfsGraph.addEdge(2, 4)
bfsGraph.addEdge(3, 0)
bfsGraph.addEdge(4, 1)
bfsGraph.addEdge(4, 5)
bfsGraph.addEdge(5, 2)
bfsGraph.addEdge(5, 4)
print(bfsGraph.display(1))

Written by@JinhyeongKim

주 1회 작성하는 개발 블로그

GitHub

알고리즘 기초 Chapter04