프로그래밍 공부131 BFS/DFS_특정 거리의 도시 찾기 풀이 암기 최단경로 문제 풀기 전 맛보기 그래프 확인! why 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) # 모든 도시에 대한 최단 거리 초기화 distance = [-1] * (n + 1) distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정 # 너비 우선 탐색(BFS) 수행 q = dequ.. 2022. 10. 5. DP_병사 배치하기 풀이 암기 * 하나의 수열이 주어졌을 때, 증가하는 형태의 가장 긴 부분의 수열만 남기기 * [10, 20, 10, 30, 20, 50] --> [10, 20, 30, 50]의 형태로 남기기 # 하나의 수열이 주어졌을 때, 증가하는 형태의 가장 긴 부분의 수열만 남기기 # [10, 20, 10, 30, 20, 50] --> [10, 20, 30, 50]의 형태로 남기기(가장 긴 증가하는 부분 수열) n = int(input()) array = list(map(int, input().split())) # 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환 array.reverse() # 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화 dp = [1] * n # 가장 긴 증가하.. 2022. 10. 3. BFS/DFS_경쟁적 전염 풀이 암기 * 완전탐색 -> BFS/DFS 활용 [모든 경우의 다 계산해야하므로] * BFS 이용 - > 초마다 이동하므로 (너비우선탐색) 1) 큐 라이브러리 활용 (from collections import deque) 2) q = deque(data) (1) 보드 정보를 한 줄 단위로 입력 (2) 해당 위치에 바이러스가 존재하는 경우 -> * (바이러스의 종류, 시간, 위치 X, 위치 Y) 삽입 = (graph[i][j], 0, i, j) 이해가 필요한 부분 # (바이러스 종류, 시간, 위치 X, 위치 Y) 삽입 data.append((graph[i][j], 0, i, j)) q.append((virus, s + 1, nx, ny)) print(graph[target_x - 1][target_y - 1]) # .. 2022. 10. 3. DP 문제 풀이정리 DP 풀이 핵심 : 점화식 도출! 정수 삼각형 n = int(input()) dp = [] # 다이나믹 프로그래밍을 위한 DP 테이블 초기화 for _ in range(n): dp.append(list(map(int, input().split()))) # 다이나믹 프로그래밍으로 2번째 줄부터 내려가면서 확인 for i in range(1, n): for j in range(i + 1): # 왼쪽 위에서 내려오는 경우 if j == 0: up_left = 0 else: up_left = dp[i - 1][j - 1] # 바로 위에서 내려오는 경우 if j == i: up = 0 else: up = dp[i - 1][j] # 최대 합을 저장 dp[i][j] = dp[i][j] + max(up_left, up.. 2022. 10. 1. 이전 1 2 3 4 5 6 7 8 ··· 33 다음
