Programming/Algorithm

분명... 알고리즘 수업 때 배웠던.. 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.11.07푼 문제 : 영어 끝말잇기사용한 언어 : python  접근 방식 :1) 이전 단어 끝 문자와 다음 단어 첫 문자가 일치하는지 비교2) 이전에 사용하지 않은 단어여야함 (딕셔너리로 체크)3) n보다 사람번호가 커지면 사람 번호를 다시 첫 번째 번호로 바꾸고 차례 수를 증가   코드 :def solution(n, words): answer = [] myDict = dict() for i in words: myDict[i] = 1 myDict[words[0]] = 0 now = words[0] idx = tern = 1 # idx는 사람번호, tern은 차례 check = False # 끝말잇기가 잘 이어지고 있는지 체..

푼 날짜 : 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(..