스택 자료구조
먼저 들어온 데이터가 나중에 나가는 선입후출의 자료구조 --> 쌓는 개념
입구와 출구가 동일한 형태로 스택을 시각화
파이썬에서의 스택은 리스트이다.
- stack=[] # 스택선언
- 삽입 : .append(원소값) , 삭제 : .pop() - 맨 마지막 원소 리턴후 삭제 , pop(i) : 리스트의 i번째 원소를 리턴하고 삭제
- 최상단 원소부터 출력 : print(stack[::-1]) # 결과는 리스트 형태
- 최하단 원소부터 출력 : print(stack) # 결과는 리스트 형태
큐 자료구조
먼저 들어온 데이터가 먼저 나가는 선입선출의 자료구조 -->터널 개념
입구와 출구가 모두 뚫려 있는 형태로 시각화 --> 대기열
파이썬에서는 큐를 쓸려면 from collections import deque
- from collections import deque
queue = deque() # 큐 구현을 위해 deque 라이브러리를 사용 - 삽입 : .append(원소값) , 삭제 : .popleft()
- print(queue) # 먼저 들어온 순서대로 출력 # 실행결과 deque([!,!,!,!])
- queue.reverse() # 역순으로 바꾸기
재귀함수
무한루프를 이용하는 게 아니라면 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야함 종료시에는 스택과 같이 나중함수부터 종료됨
def refunc(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i ==100:
return
print(i,'번째 재귀함수에서',i+1,'번째 재귀함수를 호출합니다.')
refunc(i+1)
print(i,'번째 재귀함수를 종료합니다.')
refunc(1)dfs
깊이 우선탐색, 스택자료구조(혹은 재귀함수)를 사용
동작 과정:
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[], # 1번 노드부터 시작하기에 인덱스상 0 번위치는 비워둔다.
[2,3,8], # 1번노드와 인접한 노드번호
[1,7],...] # 2번 노드와 인접한 노드번호
visited=[False]*9
def dfs(map,i,visited):
visited[i]=True
print(i, end=" ")
for k in map[i]:
if not visited[k]:
dfs(map,k,visited)
dfs(map,1,visited)
...bfs
너비 우선 탐색, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조를 이용하며, 특정 조건에서의 최단경로 찾기 등에서 쓰인다. 구체적인 동작 과정은 다음과 같다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
from collections import deque
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
[], # 1번 노드부터 시작하기에 인덱스상 0 번위치는 비워둔다.
[2,3,8], # 1번노드와 인접한 노드번호
[1,7],...] # 2번 노드와 인접한 노드번호
visited=[False]*9
def bfs(map,i,visited):
#큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start]=True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력하기
v=queue.popleft()
print(v,end=" ")
# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in map[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
bfs(map,1,visited)
...-
2차원 배열 초기화 : n,m을 안다고 가정하면
arr=[[0]*m for _ in range(n)] -
from itertools import cycle 을 쓰면 반복가능한 객체를 순서대로 무한히 반복하는 이터레이터를 생성하는 함수이다.
import itertools
emp_pool = itertools.cycle(['김은경', '이명자', '이성진'])
next(emp_pool)
'김은경'
next(emp_pool)
'이명자'
next(emp_pool)
'이성진'
next(emp_pool)
'김은경'
next(emp_pool)
'이명자'
...
- 순열, 조합을 쓸때 여러개의 튜플형태로 반환이 되므로 튜플의 형태를 없애고 튜플안에 있는 값을 문자열로 이어서 붙이고 싶으면 다음과 같이 한다.
- 순회가능한 객체가 문자열로 이루어진 경우
import itertools
items = ['A', 'B', 'C']
nPr = itertools.permutations(items, 2) # 리스트에서 2개의 원소를 골라 순서정해 나열
print(list(nPr))
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
# items의 모든 원소를 가지고 순열을 만든다
print(list(map(''.join, itertools.permutations(items))))
>>> ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
# 2개의 원소를 가지고 순열을 만든다
print(list(map(''.join, itertools.permutations(items, 2))))
>>> ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']
❗ 주의할점 : 숫자 형태의 경우 map(str,리스트명)의 과정이 추가로 들어가야함
import itertools
# 숫자형태의 경우
nums=[3,1,2,4]
print(list(map(''.join, itertools.permutations(map(str,nums), 2))))
>>> ['31', '32', '34', '13', '12', '14', '23', '21', '24', '43', '41', '42']코드 출처 : https://jungeun960.tistory.com/173
