2022-07-20 TIL

 

☝ 스택

- 선입 후출

- append(), pop() 메서드 사용 가능

- 스택 최상단 원소부터 출력하는 방법

print(stack[::-1])

 

 

☝ 큐

- 선입선출

- from collections import deque

- 큐 규현을 위해 deque 라이브러리 사용

- queue = deque()

- append(), popleft() 메서드 사용 가능

- queue.reverse()로 역순 정렬 가능

 

 

☝ 재귀 함수

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

- 재귀 함수는 스택 자료 구조를 이용하기 좋다.
- 마지막에 호출된 함수가 수행을 끝내야 그전에 호출된 함수가 실행될 수 있기 때문

- 스택 자료구조로 재귀 함수를 이용하는 대표적 알고리즘은 DFS

 

 

☝ DFS

- 깊이 우선 탐색(Depth First Search)

- 인접 행렬을 사용하는 것이 좋다.

- 데이터 개수가 N개인 경우 O(N)의 시간이 소요

 

 

☝ BFS

- 너비 우선 탐색(Breadth First Search)

- 가까운 노드부터 탐색하는 알고리즘

- 선입선출 방식인 큐 자료구조를 이용하는 것이 좋다.

- 데이터 개수가 N개인 경우 O(N)의 시간이 소요

 

 

☝ 2차원 리스트 입력받기

n, m = map(int, input().split())

graph = []
for i in range(n):
	graph.append(list(map(int, input()))

 

☝ 2차원 배열 0으로 초기화하기

graph = [[0]*m for _ in range(n)]

 

 

☝ 깊은 복사

- 파이썬 리스트를 얕은 복사하는 경우 복사한 객체에 변경이 있으면 원본에도 변화가 생김

- 이 문제를 해결하려면 깊은 복사를 사용해야 한다.

- copy 라이브러리에서 제공하는 deepcopy() 함수를 사용하면 깊은 복사가 가능하다

import copy

n = int(input())
graph = []
for i in range(n) :
  graph.append(list((input())))
m = len(graph)

graph_rg = copy.deepcopy(graph)
for i in range(n) :
  for j in range(m) :
    if graph_rg[i][j] == 'G' :
      graph_rg[i][j] = 'R'