2/7 :: 실강

Queue 

시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 형식

FIFO  First In First Out

 

W-linked list가 queue 를 구현하기에 list보다 유리한듯함

 

enqueue

dequeue : double ended queue

 

Stack

시간순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출

LIFO Last In First Out

 

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

올바른 괄호 문제

 

# stack을 활용한 풀이

def solution(s):
    stack = []
    for c in s:
        if c == '(':
            stack.append('(')
        else:
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(')')

    return False if stack else True

# 수강생 A : stack을 쓰지 않는 방법
def solution(s):
    count = 0
    
    for c in s:
        count += 1 if c == '(' else - 1
        
        if count < 0:
            return False
        
    return count == 0

# 수강생 B : index를 활용한 방법

def solution(string):
    n = len(string)
    n_list = []
    for i in range(n):
        if string[i] == '(':
            n_list.append('(')
        else:
            if len(n_list) == 0:
                return False
            else:
                n_list.pop()
        
    if len(n_list) == 0:
        return True
    else:
        return False

 

 

정확성에 포커스를 맞추고 이후 효율적으로 개선하는 부분이 좋을듯함

 

 

 

Graph

현실세계의 사물이나 추상적인 개념 간 연결 관계를 표현

 

1. 방향 그래프 vs 무향 그래프(코테에 가장 많이 등장 

2. 다중 그래프 vs 단순 그래프

3. 가중치 그래프 → 다익스트라

 

Graph 표현방법

 

1. 인접 행렬 adjacency matrix

연결되면 1, 아니면 0 (5,5)는 오타임

 

0으로 표현되며 낭비되는 resource가 있을 수 있음

 

 

2. 인접 리스트 adjacency list 

인접행렬보다 데이터 리소스를 덜 잡아먹는다

 

 

BFS

그래프 순회, 그래프 탐색

 

from collections import deque

def bfs(graph, start_v):
    q = deque()
    q.append(start_v)
    visited = {start_v: True}

    while q:
        cur_v = q.popleft()
        print(cur_v)

        for next_v in graph[cur_v]:
            if next_v not in visited:
                q.append(next_v)
                visited[next_v] = True

graph = {
    0: [1, 3, 6],
    1: [0, 3],
    2: [3],
    3: [0, 1, 2, 7],
    4: [5],
    5: [4, 6, 7],
    6: [0, 5],
    7: [3, 5],
}
bfs(graph, 0)

 

 

DFS 깊이 우선 탐색 

 

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 = {}
graph = {...}
dfs(0)

 

Q. visited={}를 함수 밖에서 정의해주는건 함수 내부에 구현하면 매번 리셋되기 때문인가요?

A. 정답. BFS와 다르게 DFS는 외부에서 정의해준다.

 

 

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

 

 

# 1. dfs로 구현 코드

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = [False] * len(rooms)

        def dfs(rooms, cur_v):
            visited[cur_v] = True
            for next_v in rooms[cur_v]:
                if visited[next_v] == False: 
                    dfs(rooms, next_v)

        # bfs(rooms, 0)
        dfs(rooms, 0)

        return all(visited)

#2. bfs

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = [False] * len(rooms)

        def bfs(start_v):
            q = deque()
            q.append(start_v)
            visited[start_v] = True
        
            while q:
                cur_v = q.popleft()
                for next_v in rooms[cur_v]:
                    if visited[next_v] == False:
                        q.append(next_v)
                        visited[next_v] = True
        bfs(0)

        return all(visited)
    
    
print(Solution().canVisitAllRooms(rooms=[[1,3], [3,0,1], [2], [0]]))

 

 

3. 암시적 그래프

 

Grid DFS

 

grid = [
   [1, 1, 1, 1],
   [0, 1, 0, 1],
   [0, 1, 0, 1],
   [1, 0, 1, 1],
]
row_len = len(grid)
col_len = len(grid[0])

# visited = [[False for _ in range(col_len)] for _ in range(row_len)]
visited = [[False] * col_len for _ in range(row_len)]

dr = [1,-1,0,0]
dc = [0,0,1,-1]
def dfs(r, c):
    visited[r][c] = True
    print(f'(r:{r},c:{c})')
    for i in range(4):
        next_r = r + dr[i]
        next_c = c + dc[i]
        if 0<= next_r < row_len and 0 <= next_c < col_len:
            if grid[next_r][next_c] == 1 and not visited[next_r][next_c]:
                dfs(next_r, next_c)


dfs(0,0)

 

 

 

 

Grid BFS

from collections import deque

grid = [
   [1, 1, 1, 1],
   [0, 1, 0, 1],
   [0, 1, 0, 1],
   [1, 0, 1, 1],
]
row_len = len(grid)
col_len = len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]

dr = [1,0,-1,0,1,-1,1,-1]
dc = [0,1,0,-1,-1,1,1,-1]
def bfs(r, c):
    q = deque()
    distance = 0
    q.append((r,c, distance))
    visited[r][c] = True

    while q:
        cur_r, cur_c, cur_d = q.popleft()
        print(f'r:{cur_r}, c:{cur_c}, d:{cur_d}')

        for i in range(8):
            next_r = cur_r + dr[i]
            next_c = cur_c + dc[i]
            if 0<=next_r <row_len and 0 <= next_c < col_len:
                if grid[next_r][next_c] == 1 and not visited[next_r][next_c]:
                    q.append((next_r,next_c, cur_d+1))
                    visited[next_r][next_c] = True

bfs(0,0)

 

 

 

 

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

 

# BFS
from collections import deque
class Solution:
    def numIslands(self, grid):
        # bfs()
        # dfs()
        count = 0
        row_len = len(grid)
        col_len = len(grid[0])
        visited = [[False]*col_len for _ in range(row_len)]
        
        # def dfs(r,c):
        # def bfs(r,c):
        dr = [1,0,-1,0]
        dc = [0,1,0,-1]
        def bfs(r, c):
            q = deque()
            q.append((r,c))
            visited[r][c] = True

            while q:
                cur_r, cur_c= q.popleft()
                for i in range(4):
                    next_r = cur_r + dr[i]
                    next_c = cur_c + dc[i]
                    if 0<=next_r <row_len and 0 <= next_c < col_len:
                        if grid[next_r][next_c] == '1' and not visited[next_r][next_c]:
                            q.append((next_r,next_c))
                            visited[next_r][next_c] = True


        for i in range(row_len):
            for j in range(col_len):
                if grid[i][j] == '1' and visited[i][j] == False:
                    bfs(i, j)
                    # dfs(i,j)
                    count += 1
        return count