백준

분명... 알고리즘 수업 때 배웠던.. MST오래되니 잊어버려서 다시 도전!한 문제~   푼 날짜 : 2024.11.08푼 문제 : [1197] / 최소 스패닝 트리사용한 언어 : python알고리즘 : MST(Prim)  접근 방식 :Kruskal 이랑 Prim 둘 중 Prim 방식으로 풀었다. 현재 기준으로 가장 비용이 낮은 것으로 이어나가는 방식이다.(이건 추후 다시 한 번 개념 정리해서 올려야겠다.) heapq를 사용하기 때문에 가장 작은 비용을 꺼내는 것은 쉽다!방문하지 않은 정점을 찾아나가며 비용이 가장 작은 길을 선택한다.   코드 :import sysimport heapqV, E = map(int, sys.stdin.readline().split())graph = [[] for _ in ..

푼 날짜 : 2024.10.30푼 문제 : [1189] / 컴백홈사용한 언어 : python알고리즘 : DFS/백트래킹  접근 방식 :DFS로 탐색하며 K만큼 이동한 위치가 목적지라면 카운트 해주는 방식으로 구현했다.  코드 : import sysR, C, K = map(int, sys.stdin.readline().split())graph_ = []for _ in range(R): row = list(sys.stdin.readline().rstrip()) graph_.append(row)dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]visited = [[0 for _ in range(C)] for _ in range(R)]ans = 0def DFS(v, now): gl..

푼 날짜 : 2024.10.30푼 문제 : [2210] / 숫자판 점프사용한 언어 : python알고리즘 : DFS  접근 방식 :깊이 우선 탐색으로 시작한다.문자열을 하나씩 추가해가며 여섯 자리가 만들어지면 set에 담겨 있는지 확인하고 없다면 추가한다. (여섯 자리가 만들어지면 무조건 리턴해준다.) DFS를 다 돌고 나면 맨 뒤에 문자열을 제거한다.이 과정을 반복하면 set에 중복없는 여섯 자리 수가 남게 된다!  코드 : NUM = 5 # 5x5 배열이므로 상수 고정graph_ = []for _ in range(NUM): nums = list(input().rstrip().split()) graph_.append(nums)dy = [-1, 1, 0, 0]dx = [0, 0, -1, 1]#..

푼 날짜 : 2024.10.27푼 문제 : [3184] / 양사용한 언어 : python알고리즘 : BFS  접근 방식 :BFS로 방문하지 않은 구간을 하나씩 탐색하며 양의 수와 늑대 수를 센다.비교해서 많은 값들을 누적해서 계산해주었다!  코드 :import sysfrom collections import dequeR, C = map(int, sys.stdin.readline().split())graph_ = []for _ in range(R): row = list(sys.stdin.readline().rstrip()) graph_.append(row)visited = [[0 for _ in range(C)] for _ in range(R)]dx = [-1, 1, 0, 0]dy = [0, 0..

푼 날짜 : 2024.10.25푼 문제 : [1890] / 점프사용한 언어 : python알고리즘 : DP  점화식 :dp[i+num][j] += dp[i][j] (if i + num dp[i][j+num] += dp[i][j] (if j + num  현재 위치에서 이동 가능 숫자(num)만큼 뛰었을 때 범위를 벗어나지 않는 경우 현재 값을 더해준다.   코드 :N = int(input())graph_ = []for _ in range(N): row = list(map(int, input().split())) graph_.append(row)dp = [[0 for _ in range(N)] for _ in range(N)]dp[0][0]=1 # 가장 왼쪽 위 칸에서 출발하므로 시작 1로 초기화..

푼 날짜 : 2024.10.18푼 문제 : [13913] / 숨바꼭질 4사용한 언어 : python알고리즘 : BFS  접근 방식 :가장 빠른 시간을 출력하는 것은 사실 이전과 비슷한 문제이기 때문에 어렵지 않았다.중요한 것은 이동 방법이 여러개인데 이를 어떻게 출력할 것인가 였다! 내가 결정한 방법은1) 이동 방법과 이동했을 때 위치를 저장2) 도착지점에서 세 가지 이동 방식을 활용해서 출발지점으로 이동하는 방법을 찾기 -> stack에 추가3) 출력을 pop을 사용해서 해준다였다. 사실 여러가지 이동 방법 중 하나의 이동 방법만 출력하면 되기에 가능한 시도였던 것 같다.  코드 :from collections import dequeN, K = map(int, input().split())# 방문 처리..

푼 날짜 : 2024.10.18푼 문제 : [9461] / 파도반 수열사용한 언어 : python알고리즘 : DP  점화식 :dp[i] = dp[i-3]+dp[i-2] 생각보다 쉬웠던 점화식 찾기! P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9  라고 문제에 주어졌기 때문에 확인해보면 3번째 전 숫자와 2번째 전 숫자를 더하면 현재 숫자가 나온다.  1, 1, 1, 2, 2, 3, 4, 5, 7, 91, 1, 1, 2, 2, 3, 4, 5, 7, 91, 1, 1, 2, 2, 3, 4, 5, 7, 91, 1, 1, 2, 2, 3, 4, 5, 7, 9...1, 1, 1, 2, 2, 3, 4, 5, 7, 9  이렇게 !!!   코드 :T = int(input(..

푼 날짜 : 2024.10.12푼 문제 : [2096] / 내려가기사용한 언어 : python알고리즘 : DP  접근 방식 :처음에 일반적인 DP로 풀다가 메모리 초과가 났다.생각해보면 DP는 현재값 계산을 위해 이전 값을 활용하기 때문에 다음 계산 전 현재 값을 이전 값으로 덮어씌웠다.# 덮어쓰기dp[0][0] = dp[1][0]dp[0][1] = dp[1][1]dp[0][2] = dp[1][2]dp2[0][0] = dp2[1][0]dp2[0][1] = dp2[1][1]dp2[0][2] = dp2[1][2] 이렇게 하면 모든 DP 배열을 채우지 않고 단순하게 계산할 수 있다.  코드 :import sysN = int(sys.stdin.readline())dp = [[0, 0, 0], [0, 0, 0]]..