[이코테] 기초 자료구조

자 우리는 자료구조를 공부하고 있는 것이 아니라 알고리즘을 공부하는 것이니 간단하게 설명만 하고 넘어가자.

 

 

스택

후입선출 (Last In First Out)

나중에 들어온 것이 먼저 나간다. 나 같은 경우 프링글스의 감자칩에 비유한다.

# 스택
# 후입선출(Last In First Out)
# 나중에 들어온 것이 먼저 나감(나는 프링글스의 감자칩에 비유함)

# 삽입(5), 삽입(2), 삽입(3), 삽입(7), 삭제(), 삽입(1), 삽입(4), 삭제()
stack=[]
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)

 

 

큐

선입선출(First In First Out)

먼저 들어온 것이 먼저 나간다. 나 같은 경우 사람들이 줄서는 것에 비유한다.

# 큐
# 선입선출(First In First Out)
# 나는 줄 서는 것에 비유한다.

# 삽입(5), 삽입(2), 삽입(3), 삽입(7), 삭제(), 삽입(1), 삽입(4), 삭제()

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)

 

재귀함수

자기 자신을 다시 호출하는 함수

재귀함수의 대표적인 예제인 팩토리얼을 구현해보았다.

# 재귀 함수
# 자기 자신을 다시 호출하는 함수

# 팩토리얼 예제
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n*factorial(n-1)

print(factorial(5))

 

DFS

깊이 우선 탐색으로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

def dfs(graph,v,visited):
    visited[v]=True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

 

BFS

너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이다.

from collections import deque

def bfs(graph,start,visited):
    queue=deque([start])
    visited[start] = True
    while queue:
        v=queue.popleft
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True