Upstage AI Lab 2기 [Day041] 자료구조 및 알고리즘 (2)

Upstage AI Lab 2기

2024년 2월 7일 (수) Day_041

 

Day_041 실시간 강의 : 자료구조 및 알고리즘 (2)

(노정호 강사님

https://www.nossi.dev/

https://www.youtube.com/@nossi-dev)

---

2일차 수업 요약 키워드

queue 

stack

graph - 인접 행렬 / 인접 리스트 / 암시적 그래프

BFS / DFS

---

 

재귀함수의 단점 - 디버깅이 어렵고, 호출시 cost가 커서 큰 데이터를 처리하기에 부적합함

-> 대안 : Dynamic Programming

 

자료구조

queue : 선입선출

enqueue(i) : rear에 데이터 추가

dequeue() : front에서 데이터 꺼내기

(front)

(rear)

 

queue를 

- python list(array)로 구현할 경우

enqueue O(1)

dequeue O(n)

pop(0) 하고 나면 리스트 내 나머지 원소를 한자리씩 옮겨줘야 함.

 

- deque(linked list)로 구현할 경우

enqueue O(1)

dequeue O(1)

deque = double ended queue

from collections import deque
q = deque()

 

 

stack : 후입선출

push, pop

list로 구현 가능

 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문자열 s의 길이 : 100,000 이하의 자연수 -> O(n^2)으로 풀지 말라는 의도

 

https://leetcode.com/problems/valid-parentheses/description/

 

---

Graph - vertex & edge의 집합

굉장히 유용

- 방향 / 무향

- 다중 / 단순

- 가중치(Dijkstra)

 

표현방법

1. 인접 행렬 (adjacency matrix)

2. 인접 리스트 (adjacency list) - 인지하기 쉽고 메모리상 이점이 있음

graph = {
    1: [3],
    2: [3, 4],
    3: [1, 2, 4, 5],
    4: [2, 3, 5],
    5: [3, 4],
}

3. 암시적 그래프 (implicit graph) - grid

---

BFS (Breadth First Search)

가까운 곳부터 -> queue로 구현

def bfs(graph, start_v):
    q = deque()
    q.append(start_v)
    visited = {start_v : True}
    
    while q:
        cur_v = q.popleft()
        
        for next_v in graph[cur_v]:
            if next_v not in visited:
                q.append(next_v)
                visited[next_v] = True

visited는 list, dict, HashSet

 

DFS (Depth First Search)

stack 또는 재귀로 구현

def dfs(cur_v):
    visited[cur_v] = True
    for next_v in graph[cur_v]:
        if next_v not in visited:
            dfs(next_v)

visited = {}
dfs(0)

 

note. 학습자료 - 변수의 유효 범위 복습하기

 

예제

https://leetcode.com/problems/keys-and-rooms/description/

(BFS/DFS로 구현가능)

 

---

암시적 그래프 (implicit graph) - grid

유형 1. 도착점까지 갈 수 있는지? (visited == True => return True, visited == False => return False)

유형 2. 최단경로 - BFS (count or visited list)

 

 

방향구현 (4개 방향, 8개 방향 etc.)

next_r = cur_r +dr

next_c = cur_c +dc

 

https://leetcode.com/problems/number-of-islands/description/

 

---

숙제

https://school.programmers.co.kr/learn/courses/30/lessons/42587