목록파이썬 (3)

step up

[프로그래머스] 정수삼각형 BFS 파이썬 풀이

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 검색해보니 대부분의 사람들이 이 문제 풀이를 DP로 푸는데, DP로 풀면 사실 엄청 간단하지만 BFS로도 풀어볼 수 있지 않을까해서 BFS로 풀어 봤다. 문제 풀이) 1. visited 초기값이 0인 삼각형을 만들고 triangle 위 상단 루트노드부터 BFS로 탐색. 2. 왼쪽 아래, 오른쪽 아래만 이동이 가능하기에, dx = [1,1], dy = [0,1] 로 정함. 이동할 다음 좌표는 nx,ny로 변수..
프로그래밍언어/코딩 문제 풀이 2022. 3. 21. 17:22
BFS와 DFS 어떻게 활용할까

그래프의 모든 노드를 순회하는 두 알고리즘의 가장 큰 차이는 1. 동일한 레벨(너비, breadth)의 형제 노드를 먼저 순회하는가 ?(BFS) 2. 깊은(depth) 노드 부터 순회를 하는가? (DFS) 로직 구성은 동일하지만 큐를 쓰는가, 스택을 쓰는가에 따라 순회 순서가 달라진다. BFS 코드 from collections import deque #graph = { 'A':['B'] , 'B':['A','C','D'], 'C':['A','B'], 'D':['A','C'] } def bfs(graph, start_node): visit = [] queue = deque() queue.append(start_node) while queue: node = queue.popleft() if node not..
프로그래밍언어/Python 2021. 7. 31. 15:05
파이썬 유용한 라이브러리 및 함수 정리

▶ itertools : 반복되는 형태의 데이터를 처리하기 위한 유용한 기능 제공 - 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 나열 from itertools import permutations data = ['A' , 'B', 'C'] result = list(permutations(data,2)) print(result) > [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')] - 조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택 from itertools import combinations data = ['A' , 'B', 'C'] result = list(combinations(data,2..
프로그래밍언어/Python 2021. 6. 6. 18:42
Prev 1 Next