나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/169199 🔑 BFS 범위가 끝 또는 'D'를 만날 때까지 이동하는 것만 끝 ✨ from collections import deque def solution(board): answer = 0 start, end = [], [] for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == 'R': # 시작점 찾기 start = [i, j] elif board[i][j] == 'G': # 도착점 찾기 end = [i, j] visit = [[0] * len(board[0]) for _ in range(len(board)..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/86971 🔑 완전 탐색, DFS 전선 연결 지점 한 곳을 끊고 탐색 (끊긴 곳이면 가지 않음) 이를 위해 양방향 그래프로 표현하고 해당하는 지점이면 continue | 방문 한 곳 - 안 한 곳 | 이 가장 적은 값으로 정답을 계속 업데이트해 주면 끝 ✨ from collections import defaultdict def solution(n, wires): answer = 1000 graph = defaultdict(list) for i in wires: # 양방향 그래프 graph[i[0]].append(i[1]) graph[i[1]].append(i[0]) def dfs(node, r..

문제 : https://www.acmicpc.net/problem/5557 🔑 DP dp 배열에 경우의 수를 저장 n = int(input()) num = list(map(int, input().split())) dp = [[0] * 21 for _ in range(n)] dp[0][num[0]] = 1 for i in range(1, n-1): for j in range(0, 21): if dp[i-1][j]: if j + num[i] = 0: dp[i][j-num[i]] += dp[i-1][j] print(dp[n-2][num[-1]])

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/68936 🔑 분할정복 알고리즘, divide and conquer algorithm 정사각형이 1칸짜리가 될 때까지 or 모두 같은 숫자의 정사각형이 나올 때까지 4등분 한다 위 조건을 만족하면 정답에 숫자를 올려준다. 모두 압축이 될 때까지 반복한다. def solution(arr): answer = [0, 0] length = len(arr) def div(x, y, length): if length == 1: # 1칸짜리 정사각형이 되면 answer[arr[x][y]] += 1 # 정답에 정사각형 숫자 갯수 올림 return t = arr[x][y] # 시작 위치의 값 저장 sw = 0..

문제 : https://www.acmicpc.net/problem/24479 🔑 visit 리스트에 방문했으면 1 대신 방문 순서를 저장 시작 노드가 가장 첫 방문 순서이기 때문에 1로 설정하고 cnt 변숫값을 2부터 시작 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n, m, r = map(int, input().split()) graph = {i : [] for i in range(1, n+1)} for i in range(m): p, c = map(int, input().split()) graph[p].append(c) graph[c].append(p) for i in graph: graph[i].sort() visit ..

문제 : https://www.acmicpc.net/problem/11725 🔑 DFS 양방향 그래프로 트리를 표현 1번 노드부터 출발 자식 노드에 도착하면 자식 노드 인덱스에 부모 노드 번호 저장 (answer 리스트) DFS 끝나면 answer [2]부터 출력 from collections import defaultdict import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n = int(input()) tree = defaultdict(list) for i in range(n-1): p, c = map(int, input().split()) tree[p].append(c) tree[c].append(p) answer = [0] ..

문제 : https://www.acmicpc.net/problem/16118 🔑 다익스트라 업그레이드 버전 (최소 거리 리스트가 2차원) 🌙 달빛 여우는 근본 다익스트라로 최소 거리를 구함 🌙 달빛 늑대 다익스트라 달릴 때, 걸을 때 두 상태를 저장하기 위해 [[INF, INF], [INF, INF], ...] 처럼 하나의 노드에 두 가지 거리 정보를 담는 리스트 생성 달릴 때는 0, 걸을 때는 1로 상태 표시를 함 처음 시작은 달리면서 시작이니까 0으로 설정 달릴 때는 달빛 여우의 2배 속도로 이동 (가중치 / 2로 계산) 걸을 때는 달빛 여우의 2배 느리게 이동 (가중치 * 2로 계산) 달빛 여우, 늑대 모두 구하고 달빛 여우의 거리가 더 짧은 노드가 있으면 카운트 증가 from collections..

문제 : https://www.acmicpc.net/problem/1753 🔑 기본 다익스트라 출발지에서 모든 노드까지의 거리를 출력 자신의 위치 0 출력 갈 수 없으면 INF 출력 출력 신경쓸 필요 없이 그냥 다익스트라 실행하고 1번 노드부터 순서대로 출력하면 그대로 나옴 INF 값만 따로 처리 from collections import defaultdict from heapq import heappush, heappop import sys input = sys.stdin.readline V, E = map(int, input().split()) # 노드의 개수, 간선의 개수 start = int(input()) # 시작 노드 graph = defaultdict(list) for i in range(E..