본문 바로가기

프로그래밍 공부/코테 풀이 암기13

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.
DP_퇴사 풀이 암기 점화식 : dp[i] = max(p[i] + dp[time], max_value) n = int(input()) # 전체 상담 개수 t = [] # 각 상담을 완료하는데 걸리는 기간 p = [] # 각 상담을 완료했을 때 받을 수 있는 금액 dp = [0] * (n + 1) # 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화 max_value = 0 for _ in range(n): x, y = map(int, input().split()) t.append(x) p.append(y) # 리스트를 뒤에서부터 거꾸로 확인 for i in range(n - 1, -1, -1): time = t[i] + i # 상담이 기간 안에 끝나는 경우 if time 2022. 10. 1.
BFS/DFS_연구소 풀이 암기 * 완전탐색 -> BFS/DFS 활용 (반복문, 재귀함수) [모든 경우의 수 다 계산해야 하므로] 모든 조합을 계산할 때 : 1) 파이썬 조합 라이브러리 활용 (from itertools import combinations) 2) BFS/DFS 이용 (* DFS -> 벽을 세웠을 경우, 끝까지 탐색하여 전체 총량을 확인해야하므로 (깊이 우선 탐색) ) 힌트: 1) DFS 이용해 울타리 설치하면서, 매번 안전영역의 크기 계산 (1) 울타리가 3개 설치된 경우 (2) 각 바이러스의 위치에서 전파 진행(virus) (3) 안전영역의 최댓값 계산 (4) 빈 공간에 울타리 설치 **암기 "dfs(count)의 의미는 무엇인가?" 어려운 포인트) dfs(count)는 모든 영역을 다 점검하여, 어디에 울타리를 설치.. 2022. 9. 29.

티스토리툴바