[수업기록] 알고리즘 : stack

240806~240807

 

1. stack의 특성

 

- 박스처럼 자료를 순서대로 쌓는 방식(박스, 접시를 생각하자!)

- 스택에 저장된 자료는 선형 구조를 갖는다

- 선형 구조 : 자료 간 관계가 1대 1의 관계

- 비선형구조 : 자료 간의 관곅 1대 N의 관계 ex. 트리

 

- 스택에 자료를 삽입하거나 자료를 꺼낼 수 있다

- 마지막에 삽입한 자료를 가장 먼저 꺼낸다(후입선출, LIFO)

- 마지막 삽입된 원소의 위치를 top이라 부름

- 연산 : 삽입(push), 삭제(pop)

stack = []

#append : 추천하지 않는 방식 -> 시간이 O(1)로 빠르지만 동적으로 메모리 할당하다보니 시간이 오래 걸림
#stack : 아예 사이즈를 잡아놓고 시작을 권유함
stack.append(1) #push(1)
stack.append(2) #push(2)
stack.append(3) #psuh(3)
print(stack.pop())
print(stack.pop())
print(stack.pop())
#3
#2
#1

#포인터 방식 : 시간이 훨씬 빠름

stack_size =10
stack = [0] * stack_size
top = -1

top += 1  # push(1)
stack[top] = 1
top += 1 # push(2)
stack[top] = 2
top += 1 # push(3)
stack[top] = 3

top -= 1
print(stack[top+1])
print(stack[top])
top -= 1
print(stack[top])
top -= 1 #이거 없어도 1 잘 나옴 내가 생각한게 맞음0
# 3 2 1

- overflow(스택길이가 부족하다), underflow(스택이 비어있다) 개념

def my_pop():
	if len(s) == 0:
    	#underflow
        return 
    else: return s.pop()

#스택 응용 : function call

def f2(c,d):
    return c-d
def f1(a,b):
    c = a+b
    d = 10
    return f2(c,d)

#a,b먼저 선언
a = 10
b = 20
print(f1(a,b))

 

2. 재귀호출 💖(A형 취득에 중요)

 

- 필요한 함수가 자신과 같은 경우 자신을 다시 호출하는 구조

- 종료조건/ 유도조건(문제를 더 작은 부분으로) 으로 나뉨

- 그럼 프로그램의 크기를 줄이고 간단하게 작성이 가능함

-ex. factorial : 1부터 n까지의 모든 자연수를 곱함

-ex. 피보나치 : 0과 1로 시작하고, 이전의 두 수합을 다음 항으로 하는 수열

def fact(n):
    if n == 1:
        return 1
    
    return n * fact(n-1)

print(fact(5))

#몇번 호출하는가
def f(n):
    global cnt
    cnt += 1
    if n == 0:
        return
    else:
        f(n-1)
cnt = 0
f(5)
print(cnt) #6

#크기 N인 배열 arr[i]에 접근
def f(i,N): # 현재 인덱스 i, N 크기
    if i == N:
        return
    else:
        print(arr[i])
        f(i+1,N)
        return #함수의 끝 구분위해 return #끝 retuen은 안써도 되긴함

arr = [1,2,3]
N = 3
print(f(0,N))

 

 

3.Memoization 메모이제이션 - top down

- 앞 예시에서 피보나치 수를 구하는 함수를 재귀함수로 구현시 엄청난 중복 호출이 존재한다

- 피보나치 수 : 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열

- 메모이제이션은 컴퓨터 프로그램 실행할 때 이전에 계산한 값을 메모리에 저장해서, 매번 다시 계산하지 않도록 하여 전체적 실행속도를 빠르게 하는 기술.

def fibo1(n): #훨씬 빠르게 수행
    if n >= 2 and memo[n] == 0: #fibo1(n)이 계산된 적 없으면
        memo[n] = fibo1(n-1) + fibo1(n-2) #아래 실행
    return memo[n]

def fibo(n):
    if n< 2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)
n = 7
memo = [0] * (n+1) #[0,1,1,2,3,5,8,13]
memo[0] = 0
memo[1] = 1
print(fibo1(n))
print(fibo(n))
print(memo)

 

4. 동적계획법(Dynamic Programming) - bottom up

- 그리디 알고리즘과 같이 최적화 문제 해결하는 알고리즘

- 큰 문제를 작은 문제로 나눌 수 있고,  작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 적용 가능

- ex. 피보나치(문제를 부분문제로 분할 가능)

- 메모이제이션을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현하는 것이 성능면에서 효율적

-> 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드 발생

---

5. DFS(깊이우선탐색)

1) 그래프란?

- 비선형적(아침드라마의 인간관계 같은..연결관계 ^0^), 정점과(Node,Vertex) 간선(Edge, Link)으로 이루어진 자료구조

- 그래프 -> 컴퓨터 폴더 구조 

- 그래프의 표현 :

-- 인접행렬(Adjacency Matrix) : 연결관계를 행렬로 나타냄, 연결되지 않은 노드들에 대한 정보 저장(메모리 과다)

-- 인접 리스트 : 각 노드별로 인접한 모든 노드를 리스트로 나타냄, 인접행렬에 비해 병렬처리가 어려움 O(N + E)

 

- 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함

-> 두가지 방법 : DFS(깊이 우선 탐색) / BFS(너비 우선 탐색)

 

2) DFS :

- 왜 쓰일까? : 경로 존재 확인(미로확인), 백트래킹(특정 조건 만족하는 모든 해 찾기) 

- 구현방법 : 후입선출 방식으로 처리하는 자료 구조인 재귀 함수, 스택 

-> 갈림길로 가다가, 더 이상 탐색할 길이 없을 때 가장 최근 갈림길로 돌아가, 다시 깊이 우선 탐색 반복해야하므로 후입선출 구조 스택 사용 ❤

 

 

V, E = 7, 8 #노드수, 간선 수
edges = list(map(int, "1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7".split())) #연결된 엣지정보
print(edges)
#[1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]


# 인접 리스트
# 세가지 방법으로 구현 가능
graph = [[] for _ in range(V+1)] #엣지에 0이 없어서 인덱스 0은 안씀
graph = {i+1:[] for i in range(V)}
from collections import defaultdict
graph = defaultdict(list)
for i in range(E):
    v1,v2 = edges[2*i], edges[2*i+1] #edge 2개가 한 묶음 #1 2 #1 3

    #무향 그래프(양방향으로 이동가능)
    graph[v1].append(v2)
    graph[v2].append(v1) #이 코드 없으면 유향그래프(단방향)
print(graph)
# for key,val in graph.items():
#     graph[key] = sorted(val) #재귀방식으로 작은 번호 순으로 방문
#     graph[key] = sorted(val, reverse=True) #스택 방식에서 작은 번호 순으로 방문
#[[], [2, 3], [1, 4, 5], [1, 7], [2, 6], [2, 6], [4, 5, 7], [6, 3]]


def dfs_recursive(cur_node):
    # 방문한 노드 처리 로직
    visited[cur_node] = 1
    print(cur_node, end=' ')

    # 현재 노드와 인접한 다음 노드 탐색
    for next_node in graph[cur_node]:
        #방문하지 않은 것만 탐색
        if not visited[next_node]:
            dfs_recursive(next_node)
visited = [0] * (V+1) ##??
dfs_recursive(1)


def dfs_stack(start_node):
    stack = [start_node]
    while stack : # 스택에 남은 것이 없을 때까지 반복
        cur_node = stack.pop() #현재 방문 노드

        #스택 중간 요소들을 빼주는 코드 #스택 : 마지막 요소를 고려
        #방문한 적이 있는 경우 continue -> 다음 while문으로 이어짐
        #최적화
        if visited[cur_node] :
            continue
        #방문처리
        visited[cur_node] = 1
        print(cur_node,end=' ')

        #현재 노드와 연결된 노드 중 방문하지 않은 노드만 스택에 추가
        for next_node in graph[cur_node]:
        # for next_node in sorted(graph[cur_node], reverse=True):
            if not visited[next_node]:
                stack.append(next_node)
print()
visited = [0] * (V+1) #노드 번호가 0부터 시작안하는 케이스라서
dfs_stack(1)