초이의 끄적끄적

유니온파인드( Union Find )

• 한 그래프와 다른 한 그래프의 노드를 비교하여 서로 다른 그래프에 속해있다면 합쳐준다. 같은 그래프에 속해있는지 판단하는 방법은 서로의 루트노드가 같은지 비교하면 된다.

문제 모음

• 프로그래머스 - 네트워크 (문제로 이동)
• 프로그래머스 - 섬 연결하기 -> Union-Find 응용한 크루스칼 알고리즘 (문제로 이동)
• 백준 - 1717번 집합의 표현 (골드4) (문제로 이동)
• 백준 - 1976번 여행 가자 (골드 4) (문제로 이동) (참고)
• 백준 - 4195번 친구 네트워크 (골드 2) (문제로 이동)

2021.06.18 - [알고리즘/baekjoon] - [백준/파이썬] 친구 네트워크, 수 찾기, SHA-356

프로그래머스 - 네트워크 (LEVEL 3)

def solution(n, computers):
    parents = [i for i in range(n)] # 초기값 각자 자기 자신을 부모로 가지고 있다

    def FindRoot(node): # 부모 노드를 찾는다
        parentNode = parents[node]
        # node의 parentnode가 자기 자신이 아닐경우 계속해서 상위노드를 탐색한다.
        if parentNode != node: 
            return FindRoot(parentNode)
        else:
            return parentNode

    def UnionSet(node1, node2): #두 노드의 부모를 병합(Union)한다
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            # print(parents)
            return
        else:
            parents[rootNode1] = rootNode2
            # print(parents)
            return

    def CountRoot(parents): # 루트 노드의 갯수를 센다(덩어리 갯수 세기)
        roots = set()
        for i in range(n):
            roots.add(FindRoot(i))
        # print(roots)
        return len(set(roots))

    for node1 in range(n): # 입력값 computers에서 연결된 그래프를 찾는다
        for node2 in range(node1,n):
            if computers[node1][node2]:
                UnionSet(node1, node2)

    return CountRoot(parents)

+ dfs/bfs풀이 

def solution(n, computers):
	answer = 0 # 네트워크의 개수 저장
    q = [] # 탐색을 위한 큐
    visited = [0]*n # 방문한 노드 체크

    while 0 in visited: #모든값이 방문표시가 될때까지 반봇
        x = visited.index(0)
        q.append(x) # 첫 노드 인덱스 추가
        visited[x] = 1 # 첫 노드 방문 표시
        
        while q: 
            node = q.pop(0) # 큐 앞에서부터 노드 꺼내기
            visited[node] = 1
            for i in range(n): #인접 노드 방문
                if visited[i] == 0 and computers[node][i] == 1:
                    # 인접노드이고 방문한적 없는 경우
                    q.append(i) # 큐에 추가
                    visited[i] = 1 #방문했음을 표시
        answer += 1 # 한 네트워크 탐색을 마치면 개수 증가
    return answer

프로그래머스 - 섬 연결하기 (LEVEL 3)

• 크루스칼 알고리즘(Kruskal Algorithm) : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리(MST)를 만들기 위한 대표적인 알고리즘
• 크루스칼 알고리즘(Kruskal Algorithm) = 유니온 파인드(Union Find) + 정렬
• 최소 가중치를 기준으로 정렬한 후 순차적으로 접근하며 두 개의 노드가 연결되어 있지 않다면 연결하고 그 간선의 가중치를 더해준다. 그리고 두 개의 노드를 병합해준다

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2]) # 비용기준 오름차순 정렬
    parents = [i for i in range(n)]  # union-find 리스트 선언.
    
    def FindRoot(node): # 부모 노드를 찾는다
        parentNode = parents[node]
        if parentNode != node: 
            return FindRoot(parentNode)
        else:
            return parentNode

    def UnionSet(node1, node2): #두 노드의 부모를 병합(Union)한다
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            return
        else:
            parents[rootNode1] = rootNode2
            return
    
    def findParent(node1, node2): # 두 노드가 연결되어 있는지 판별
        rootNode1 = FindRoot(node1)
        rootNode2 = FindRoot(node2)
        if rootNode1 == rootNode2:
            return 1
        else:
            return 0
    
    for s, d, cost in costs:
        # 두 노드가 연결되어 있지 않다면 연결시켜준다
        if findParent(s,d) != 1: 
            answer+= cost
            UnionSet(s,d)

    return answer

데이터 개수를 셀 때 유용한 파이썬의 collections 모듈의 Counter 클래스 사용법 ( 참고자료 ) 

* Counter() : 데이터 개수 세서 딕셔너리 형태로 반환

from collections import Counter

word_count = Counter('hello world') 
print(word_count)
>>> Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

for key,value in word_count.items():
    print(key,':',value)
>>> h : 1
>>> e : 1
>>> l : 3

* Counter의 내부 메소드

• most_common() : Counter()에서 가장 빈도수가 높은 순으로 정렬

from collections import Counter

# 데이터의 개수가 많은 순으로 정렬된 배열 리턴
Counter('hello world').most_common() 
>>>[('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

# 가장 개수가 많은 k개의 데이터 리턴
Counter('hello world').most_common(1)
>>> [('l', 3)]

순열(permutations) nPr

• 순서 고려해서 나열한 경우의 수
• itertools.permutations( items , r ) : 리스트에서 r개의 원소를 골라 순열 결과를 리턴

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, 리스트명)의 과정이 추가로 들어가야 함

• str.join -> iterable iterable에서 문자열을 연결 한 문자열을 반환합니다
• 때문에 숫자를 문자로 변경하지 않으면 'TypeError: sequence item 0: expected str instance, int found' 발생

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']

조합(combination) nCr

• 순서 고려하지 않고 나열한 경우의 수 -> 뽑는 순서는 중요하지 않다
• itertools.combinations( items , r ) : 리스트에서 r개의 원소를 골라 조합 결과를 리턴

import itertools

items = ['A', 'B', 'C']
nCr = itertools.combinations(items, 2)
print(list(nCr))
>>> [('A', 'B'), ('A', 'C'), ('B', 'C')]

코테 풀면서 자주 쓰이는 파이썬 내장함수 정리 ( 참고자료 )

• abs(x) : 절댓값
• divmod(a,b) : a를 b로 나눈 몫과 나머지를 튜플 형태로 반환
• pow(x,y) : x의 y 제곱한 결과값
• round(x) : 반올림
• ceil(x) : 올림
• floor(x) : 내림
• map(f, iterable) : 입력받은 자료형의 각 요소를 함수 f가 수행한 결과를 묶어서 반환

# 숫자 자리수대로 분리
num = 12345
list(map(int, str(num))
>>> [1,2,3,4,5]

• enumerate : 인덱스 번호와 컬렉션의 원소를 tuple 형태로 반환

for i, name in enumerate(['body', 'foo', 'bar']):
     print(i, name)
>>> 0 body
>>> 1 foo
>>> 2 bar

• zip : 동일한 개수로 이루어진 자료형을 묶어주는 역할을 하는 함수 ( ※ 리스트의 길이가 같아야 함)
  • 동시에 여러 리스트에 접근하여 처리할 때 사용

numbers = [1, 2, 3]
letters = ["A", "B", "C"]
for pair in zip(numbers, letters):
     print(pair)
>>> (1, 'A')
>>> (2, 'B')
>>> (3, 'C')

Number = [1,2,3,4]
Name = ['hong','gil','dong','nim']
dic = {}
for number, name in zip(Number,Name): 
    dic[number] = name
print(dic)
>>> {1 : 'hong' , 2 : 'gil' , 3 : 'dong' , 4 : 'nim'}

+ 재귀 함수 최대 깊이 설정하기

• 재귀 함수의 경우 문제에 따라 1,000,000보다 작거나 같은 자연수 같이 범위가 주어질 때가 있다.
  최상단에 아래와 같은 코드를 넣는다

import sys 
sys.setrecursionlimit(10**6) # 0의 갯수만큼 늘려주면 됌. 10^6 == 1,000,000

+ 함수 이름이 생각나지 않을 때

• dir() : 객체가 자체적으로 가지고 있는 변수나 함수를 보여준다

a = []  # 리스트
print(dir(a))
>>> [ ..., 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 
'pop', 'remove', 'reverse', 'sort']

b = {}  # 딕셔너리
print(dir(b))
>>>[ ..., 'clear', 'copy', 'fromkeys', 'get', 'items', 'keys', 'pop', 'popitem', 
'setdefault', 'update', 'values']

DFS나 BFS를 풀 때 그래프를 만들어 풀면 수월한 문제들이 있다

예를 들어 ( 프로그래머스 여행경로 문제  )

• 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미이다

[["ICN", "SFO"], 
["ICN", "ATL"], 
["SFO", "ATL"], 
["ATL", "ICN"], 
["ATL","SFO"]]

이를 딕셔너리를 사용하여 그래프를 만들면

• 첫 번째 방법

routes = {}
for key, value in tickets:
	if key in routes:
		routes[key].append(value)
	else:
		routes[key] = [value]

>>> {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']}

• defaultdict()를 활용한 이보다 간편한 두 번째 방법 -> 키가 있는지 확인할 필요가 없다

from collections import defaultdict

routes = defaultdict(list)
for key, value in tickets:
	routes[key].append(value)
   
>>> defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})

+ defaultdict() 활용법

• defaultdict()는 인자로 주어진 객체의 기본값을 딕셔너리 값의 초기값으로 지정할 수 있다.
• 숫자, 리스트, 셋 등으로 초기화 할 수 있다.
• 외부 함수이기 때문에 import 해야 됨 -> from collections import defaultdict

1. 숫자로 초기화 -> 값을 지정하지 않으면 0으로 초기화 ex) 알파벳 횟수 계산
2. 리스트로 초기화 -> 값을 지정하지 않으면 빈 리스트로 초기화 ex) 그래프 경로, 같은 성을 가진 이름끼리 취합하기 
3. 셋으로 초기화 -> 값을 지정하지 않으면 빈 리스트로 초기화

# 1번 숫자로 초기화

from collections import defaultdict
int_dict = defaultdict(int)
int_dict
>>> defaultdict(<class 'int'>, {}) # 디폴트값이 int인 딕셔너리

# 값 지정 안하면 0으로 초기화
int_dict['key1']
>>> 0
int_dict
>>> defaultdict(<class 'int'>, {'key1': 0}) 

# 값 지정하면 그 값으로 지정
int_dict['key2'] = 'test'
int_dict
>>> defaultdict(<class 'int'>, {'key1': 0, 'key2': 'test'}) 

# 리스트로 초기화

from collections import defaultdict
list_dict = defaultdict(list)
list_dict
>>> defaultdict(<class 'list'>, {}) # 디폴트값이 list인 딕셔너리

list_dict['key1'] # 값을 지정하지 않으면 빈 리스트로 초기화
>>> []

list_dict['key2'] = 'test' # 값을 지정하면 해당값으로 초기화
list_dict
>>> defaultdict(<class 'list'>, {'key1': [], 'key2': 'test'}) 

( 참고 : 유사 딕셔너리 defaultdict() 활용법 )

프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)

# 타겟 넘버 (Level2) : 2021.04.07 - [알고리즘] - 20210407_코테공부

# 네트워크 (Level 3) : 2021.02.17 - [알고리즘] - 20210217_코테공부

# 단어 변환 (Level 3) : 2021.04.08 - [알고리즘] - 20210408_코테공부

# 여행경로 (Level 3) : 2021.04.12 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 여행경로 - DFS/BFS

백준

# 17406 배열 돌리기 4 (골드4) : 2021.02.04 - [알고리즘] - 20210204_코테공부

# 12100 2048(Easy) (골드2) : 2021.01.29 - [알고리즘] - 20210129_코테공부

# 16768 Mooyo Mooyo (골드4) : 2021.01.28 - [알고리즘] - 20210128_코테공부

# 1021 유기농 배추 (실버2) : 2021.01.12 - [알고리즘] - 20210112_코테공부

#

+ DFS/BFS Tip.

• BFS는 최단거리에 유리함 -> DFS의 최악의 경우에는 오래걸릴 수 있으니까
• DFS는 종단노드까지 다 탐색해야만 답이 나오는 경우에 유리함
• 그래프 그릴 수 있는 애는 dic로 푸는게 유리
  • 2021.04.12 - [ 파이썬 ] 파이썬 Dictionary를 이용해 그래프 만들기 / defaultdict() 활용하기
• 이차원배열이 주어지고 대각선이나 위아래로 다 탐색해야되면 dic보다는 백트래킹 or BFS

문자열 빈출 함수

• 문자 개수 세기 : 문자열.count('s')
• 특정 문자 찾기 : 문자열.find('s')
  • 없으면 -1 리턴
• (접두어)특정 문자로 시작하는지 여부 : 문자열.startswith('ho') ( 참고자료 )
• (접미어)특정 문자로 끝나는지 여부 : 문자열.endswith('h')
  • 문자열 대신 문자열로 이루어진 tuple을 넣을 수도 있다. (※리스트 안됨)
• 위치 알려주기2 : 문자열.index('s')
  • 주의 : 없으면 오류 뜸
• 리스트를 문자열로 합치기 : '구분자'.join(리스트)
• 문자열 쪼개 리스트 만들기 : 문자열.split()
  • 파라미터를 안쓰면 띄어쓰기, 엔터를 구분하여 나눈다
• 문자열 치환 : 문자열.replace('a','b') # a를 b로 바꾼다

a = 'hobby'

# 문자열에서 특정 문자의 개수를 리턴
s1 = a.count('b')
print(s1)
>>> 2

# 위치 찾기1
s2 = a.find('b')
print(s2)
>>> 2
s3 = a.find('k')
print(s3)
>>> -1

# 특정 문자로 시작하는지 여부 
ss1 = a.startswith('ho')
print(ss1)
>>> True

# 특정 문자로 시작하는 여부 (여러개)
url = "https://www.naver.com"
url_check = ("http","https")
url.startswith(url)
>>> True

# 특정 문자로 끝나는지 여부
ss2 = a.endswith('h')
print(ss2)
>>> False

# 위치 찾기2
s4 = a.index('b')
print(s4)
>>> 2
a.index('k')
>>> 오류

# 리스트 문자로 합치기
b = ['a', 'b', 'c', 'd', '1', '2', '3']
s5 = "".join(b)
print(s5)
>>> abcd123
s6 = "-".join(b)
print(s6)
>>> a-b-c-d-1-2-3

# 문자열 쪼개기
c = "a b c d e f g"
s7 = s.split()
print(s7)
>>> ['a','b','c','d','e','f','g']
d = "aa.bb.cc.dd.ee.ff.gg"
s8 = s.split('.')
print(s8)
>>> ['aa','bb','cc','dd','ee','ff','gg']

+ 리스트 원소 추가, 삭제

• 원소 추가 : 리스트.append(값)
• 특정 위치에 원소 추가 : 리스트.insert(인덱스, 값)
• 여러 원소 추가하기 : 리스트.extend(추가할 리스트)
• 특정 위치의 원소 삭제 : del 리스트[인덱스]
• 원소 값 삭제 : 리스트.remove(값)

a = [1, 2, 3]

# 원소 추가
a.append(6)
>>> [1, 2, 3, 6]

# 특정 위치에 원소 추가
a.insert(1, 5)
>>> [1, 5, 2, 3, 6]

# 여러 원소 추가하기
a.extend([4,5,6])
>>> [1, 5, 2, 3, 6, 4, 5, 6]

# 특정 위치의 원소 삭제
del a[1]
>>> [1, 2, 3, 6, 4, 5, 6]

# 원소 값 삭제
a.remove(3)
>>> [1, 2, 6, 4, 5, 6]

문자열 정렬

• 리스트로 변환 후 sort, sorted를 사용하여 정렬한다.
  • list 본체 정렬 : 문자열.sort() # reverse = True 시 내림차순 정렬
  • list 정렬된 결과 반환 : sorted(문자열)
  • list 뒤집기 : 문자열.reverse()
  • 관련 문제 : 문자열 내림차순으로 배치하기  2021.04.07 - [알고리즘] - 20210407_코테공부

s = "Zbcdefg"
s = list(s)
print(s)
>>> ['Z', 'b', 'c', 'd', 'e', 'f', 'g']

s.sort(reverse = True)
print(s)
>>> ['g', 'f', 'e', 'd', 'c', 'b', 'Z']

a = [1, 10, 5, 7, 6]
a.sort()
a
>>> [1, 5, 6, 7, 10]

y = sorted(a)
y
>>> [1, 5, 6, 7, 10]

a.reverse()
a
>>> [6, 7, 5, 10, 1]

+ 문자열의 길이를 기준으로 정렬 : 문자열.sort(key=lamba x:len(x))

+ 문자열의 n번째 수 기준으로 정렬 : 문자열.sort(key=lambda x:x[n])

+ 다중 조건 정렬 : 문자열.sort(key=lambda x: (x[0],x[1])) // x[0] 기준으로 정렬하고 x[1] 기준으로 정렬

a = [(4,0), (4,3), (4,2), (3,2), (2,1), (1,0)]


# 인자 없이 sorted()를 사용하면 리스트 아이템의 각 요소 순서대로 정렬
# 첫 번째 요소가 같으면 두 번째 요소로 비교
b = sorted(a)
print(b)    
>>> [(1, 0), (2, 1), (3, 2), (4, 0), (4, 2), (4, 3)]


# key인자에 lambda 함수를 넘겨주면 반환값을 가지고 비교해 정렬
# 이 때, key로 전달되지 않은 요소에 대해선 정렬하지 않음
c = sorted(a, key=lambda x : x[0])
print(c)    
>>> [(1, 0), (2, 1), (3, 2), (4, 0), (4, 3), (4, 2)]
d = sorted(a, key=lambda x : x[1])
print(d)    
>>> [(4, 0), (1, 0), (2, 1), (4, 2), (3, 2), (4, 3)]


# 정렬 기준으로 다중 조건을 넘겨줄 수도 있다
# 첫 번째 인자를 기준으로 오름차순 정렬을 먼저 한다.
# 그 결과를 가지고 두 번째 인자를 기준으로 내림차순 정렬(-를 붙이면 내림차순 정렬)
e = sorted(a, key = lambda x : (x[0], -x[1]))
print(e)    
>>> [(1, 0), (2, 1), (3, 2), (4, 3), (4, 2), (4, 0)]

• 관련 문제 : 문자열 내 마음대로 정렬하기 2021.03.02 - [알고리즘] - 20210302_코테공부

대소문자 관리 함수 (upper, lower, isupper, islower)

• 주어진 문자열의 모든 알파벳을 소문자로 바꾸는 함수 : 문자열.lower()
• 주어진 문자열의 모든 알파벳을 대문자로 바꾸는 함수 : 문자열.upper()
• 주어진 문자열의 맨 첫 글자를 대문자로 바꾸는 함수 : 문자열.capitalize()
• 주어지 문자열에서 알파벳 외의 문자(숫자, 특수문자, 띄어쓰기 등)로 나누어져 있는 첫 글자를 모두 대문자로 바꾸는 함수 : 문자열.title()
• 소문자 확인 : 문자열.islower() -> True / False로 리턴
• 대문자 확인 : 문자열.isupper() -> True / False로 리턴

※ capitalize()와 title() 차이 주의!

+ 알파벳/숫자인지 확인하기  -> True / False로 리턴

• 알파벳인지 확인하기 : 문자열.isalpha()
• 숫자인지 확인하기 : 문자열.isdigit()
• 알파벳 또는 숫자인지 확인하기 : 문자열.isalnum() -> 특수문자 있는지 확인
• ※ 문자열에 공백이 포함되어 있으면 False를 리턴합니다

+ 소문자 / 대문자

• 'abcdefghijklmnopqrstuvwxyz'
• 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

a = 'hobby'

# 소문자로 바꾸기
s5 = a.lower()
print(s5)
>>> hobby

C = 'a2b3c4'
# 대문자로 바꾸기
C.upper()
>>> 'A2B3C4'

# 주어진 문자열의 맨 첫 글자를 대문자로 바꾸는 함수
C.capitalize()
>>> 'A2b3c4'

# 주어지 문자열에서 알파벳 외의 문자(숫자, 특수문자, 띄어쓰기 등)로 
# 나누어져 있는 첫 글자를 모두 대문자로 바꾸는 함수 : 문자열.title()
C.title()
>>> 'A2B3B4'

# 소문자 확인
a.islower()
>>> True

# 대문자 확인
a.isupper()
>>> False

# 알파벳인지 확인하기
Ex1 = 'ABC'
print(Ex1.isalpha())
>>> True
Ex2 = "100Appia"
print(Ex2.isalpha())
>>> False

# 숫자인지 확인하기
Ex1 = '123456'
print(Ex1.isdigit())
>>> True
Ex2 = "R4R3"
print(Ex2.isdigit())
>>> False
 

# 알파벳 혹은 숫자인지 확인하기
Ex1 = 'Hello3'
print(Ex1.isalnum())
>>> True
Ex2 = "1.Where" 
print(Ex2.isalnum())
>>> False

Deque란

• 주로 큐 구현에 사용
• Deque는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다. 스택과 큐의 기능을 모두 가졌다.

+ 스택(Stack)

• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조(LIFO) -> 오른쪽 끝에서 입출력
• 리스트 사용해 append(), pop() 사용

stack = [1,2,3]

# 원소 추가
stack.append(4) 
stack
>>> [1, 2, 3, 4]

# 가장 마지막 원소 삭제 후 그 값 리턴
top = stack.pop() 
print(top)
stack
>>> 4
>>> [1, 2, 3]

# 스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1] 사용
top = stack[-1] 
top
stack
>>> 3
>>> [1, 2, 3]

※ pop() : 맨 마지막 요소 삭제 / pop(x) : x번째 요소를 리턴 후 삭제 -> x는 인덱스임

 + list.remove('값') : 인덱스가 아니고 값임

+ 큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO) -> 오른쪽에 입력 왼쪽으로 출력
• deque를 사용해 append(), popleft() 사용
• 데이터를 입력된 순서대로 처리해야 할 때, BFS(너비 우선 탐색) 구현 할 때 사용

※ 스택과 달리 큐를 list로 이용하지 않는 이유

 스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 시간복잡도는 O(1)인 반면 pop(0)의 시간복잡도는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

디큐 함수 ( from collections import deque)

• 스택 구현(오른쪽 끝에서 입출력) : append(), pop()
• 큐 구현 : appendleft(), pop(), append(), popleft()
• depue 확장하기 : extend(), extendleft()
• 리스트 처럼 수정 삭제 : insert(), remove()
• deque 내용 좌우로 반전 : reverse()
• 회전 : rotate(n)
• 모든 원소 제거 : clear()

from collections import deque # 모듈 임포트
queue = deque([4, 5, 6]) # 디큐 생성

# append(x) : 오른쪽(마지막)에 원소 추가(삽입)
queue.append(7)
queue.append(8)
print(queue)
>>> [4, 5, 6, 7, 8]

# popleft() : 왼쪽(앞쪽)부터 차례대로 제거와 반환
queue.popleft()
>>> 4
queue.popleft()
>>> 5
print(queue)
>>> [6, 7, 8]

# rotate(n) : 요소들을 값 만큼 회전 해주는 메소드
# 음수면 왼쪽으로, 양수면 오른쪽으로 회전
deq = deque(['a', 'b', 'c', 'd', 'e'])
deq.rotate(1)
>>> e a b c d

deq2 = deque(['a', 'b', 'c', 'd', 'e'])
deq3.rotate(-1)
>>> b c d e a

+ 스택/큐 관련 문제 정리  ( 프로그래머스 )

# 다리를 지나는 트럭 (Level2) : 2021.04.17 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 다리를 지나는 트럭 - deque

# 주식가격 (Level2) : 2021.03.31 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 주식가격

# 기능개발 (Level2) : 

# 프린터 (Level2) : 2021.04.15 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 프린터 - deque