본문 바로가기

Algorithm13

[ Chapter.05 ] Part03 / 특정 거리의 도시 찾기 모든 간선의 비용이 동일할 때는 BFS를 이용해 최단 거리를 찾을 수 있습니다. from collections import deque n, m, k, x = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) # print(graph) # [[], [2, 3], [3, 4], [], []] check = [-1] * (n + 1) check[x] = 0 # 너비 우선 탐색(BFS) 수행 q = deque([x]) # print(q) # deque([1]) while q: now = q.popleft() # 현재 도시에서 이동할.. 2022. 7. 31.
[ Chapter.05 ] DFS / BFS 이론 그래프의 기본 구조 DFS / BFS 알고리즘에 대한 설명에 앞서, 그래프의 기본 구조 두 가지에 대해 살펴보겠습니다. 01) 인접 행렬 인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현하는 방식 입니다. 연결 되어 있지 않은 노드끼리는 무한이라고 작성합니다 (INF) 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 낭비됩니다. 02) 인접 리스트 인접 리스트는 각각의 노드에 연결된 노드의 정보를 차례대로 연결하여 저장합니다. 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용합니다. 연결된 데이터를 하나씩 확인해야 하기 때문에 정보를 얻는 속도가 느립니다. DFS Depth-First Search 깊이 우선 탐색이라고 부릅니다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다... 2022. 7. 27.
[ Chapter.05 ] 꼭 필요한 자료구조 기초 복습하는 느낌으로 간단하게 살펴보겠습니다. 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미합니다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 자주 다룹니다. 탐색 알고리즘으로 DFS, BFS를 뽑을 수 있습니다. 자료구조 데이터를 표현하고 관리하고 처리하기 위한 구조입니다. 대표적인 스택과 큐는 push(), pop() 함수로 구성됩니다. + 오버플로와 언더플로도 고민해야 합니다. 스택 쉽게 생각하면 박스 쌓기에 비유할 수 있습니다. 스택은 선입후출(First In Last Out) 구조입니다. python으로 stack을 구현할 때 별도의 라이브러리를 사용할 필요가 없으며, 기본 리스트에서 append()와 pop() 메서드를 이용하면 stack 자료구조와 동일.. 2022. 7. 27.
[ BOJ ] 14888 / 연산자 끼워넣기 문제 n개의 수로 이루어진 수열이 주어집니다. 수와 수 사이에 끼워 넣을 수 있는 n-1개의 연산자가 주어집니다. 연산자는 +, -, x, / 로만 구성됩니다. 주어진 수열의 순서를 바꾸는것은 안됩니다. Solve 연산자의 순열을 구합니다. operator = ['+', '+', '-', '*', '/'] arr = itertools.permutations(operator, len(operator)) print(len(list(arr))) # 120 ('+', '+', '-', '*', '/') 이런게 겹치는 것을 확인할 수 있습니다. 이때 전체 길이는 120입니다. arr = itertools.permutations(operator, len(operator)) arr_set = set(list(arr).. 2022. 7. 26.

티스토리툴바