해킹왕 양선규

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 1 for i in range(3, x + 1): d[i] = d[i-1] + d[i-2] print(d[x]) 간단한 DP 문제이다. 재귀함수로 구현하면 입력값이 90까지이기 때문에 메모리가 터져버린다. x가 1, 2일 경우만 리스트에 등록해 둔 후 간단한 반복문을 돌리면 된다. 재귀 구현했을 경우 90이면 정말 컴퓨터가 터지기 직전까지 가는데 상향식 DP방식인 반복문으로 구현하면 대략 90번정도만 연산하면 되기 때문에 문제를 해결할 수 있다.

N, money = map(int, input().split()) # 동전 종류, 돈 coinBox = [] for _ in range(N): coinBox.append(int(input())) coinBox.reverse() cnt = 0 for coin in coinBox: # 큰 동전부터 차례로 대입된다 if money >= coin: cnt += money // coin money = money % coin print(cnt) 그리디 알고리즘으로 해결할 수 있는 문제이다. 매 순간 최적의 선택을 하면 되기 때문에, 구현이 그리 어렵진 않다. 동전을 입력받은 후, 반복문을 돌리면 큰 동전부터 나오도록 reverse()메소드로 뒤집는다. 이후 큰 동전부터 반복문을 돌며, 남은 돈이 동전 가치보다 같거..

import sys input = sys.stdin.readline x = int(input()) d = [0] * (x + 1) path = ['' for _ in range(x + 1)] path[1] = '1' for i in range(2, x + 1): d[i] = d[i - 1] + 1 prev = i - 1 if i % 3 == 0 and d[i // 3] + 1

x = int(input()) d = [0] * ((10 ** 6) + 1) for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) print(d[x]) 다이나믹 프로그래밍 문제이다. d는 메모이제이션(값을 저장해 놓을)할 리스트. i는 현재 계산중인 숫자 d[i] 는 i에 대한 최소연산횟수이다. 숫자 2부터 바텀 업 방식으로 d리스트를 채워나가 최종적으로 x의 최소연산횟수를 구하는 것이다. 이 문제는 3가지 연산을 할 수 있다. 1을 빼기, 2로 나누기, 3으로 나누기 하지만 2나 3으로 나눠진다고 해서 무조건..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..

매일매일 엄청난 양의 지식을 머리에 꾸역꾸역 넣고 있다. 공부가 잘 안 되는 것 같고, 집중도 안 되는 것 같고. 남들은 더 열심히 하는 것 같고, 나는 부족한 것 같고 하는 생각이 계속계속 들어도, 멈춰서 차근히 돌아보면 지금의 나는 입소날인 3월18일보다 몇 배로, 말도 안되게 빠른 속도로 성장했다. 실질적인 웹 개발이나 프로젝트 경험이 전무하던 내가 입소 4일만에 어엿한 웹사이트를 하나 만들어 냈고, 프로젝트 경험이 생겼다. 알고리즘의 ㅇ자도 모르던 내가 2주만에 DFS, BFS, 백트래킹, 최소스패닝트리, 위상정렬, 여러가지 그래프 이론, 스택, 큐, 힙, 정렬, 재귀함수, CS지식 등등 이것보다 훨씬 많은 말도 안되게 많은 지식을 습득했으며, 백준 티어도 어느새 골드5가 되었다. 하루하루가 정말..

신장 트리(Spanning Tree) - 그래프 내의 모든 정점을 포함하면서 사이클이 없는 부분 트리 최소 스패닝(신장) 트리(Minimum Spanning Tree, MST) - 가중치가 있는 양방향 그래프에서 싸이클 없이 모든 정점을 포함하며 가중치의 합이 최소인 트리 - 모든 정점을 연결하는 트리를 형성하면서, 가중치 합이 최소화되도록 하는 것 프림(Prim) 알고리즘 - 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘 - 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 우선순위 큐를 사용한다. - 이미 그래프에 속한 노드엔 적용시키지 않기 위해 visited를 사용한다. 프림 알고리즘 동작원리 1. 임의의 시작 노드를 설정하고 T(트리)..

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다. import sys from collections import deque input = sys.stdin.readline R, C = map(int, input().split()) # 행, 열 forest = [list(input().strip()) for _ in range(R)] visited = [[-1] * C for _ in range(R)] # -1로 설정해두고 도치의 이동 과정을 입력할것이다 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() for x in range(R): for y in range(C): if f..

import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline # 이분 그래프 판별 DFS 함수 def DFS(graph, start, visited, group): visited[start] = group for i in graph[start]: if visited[i] == 0: # 방문 안 한 곳이라면 result = DFS(graph, i, visited, -group) if not result: return False # 하위에서 이분 그래프 아니라고 판단했다면 함수 종료 elif visited[i] == group: # 인접노드인데 그룹이 같을경우 이분그래프 아님 return False return True # 입력받은 갯수만큼 그래..

import heapq import sys input = sys.stdin.readline N, E = map(int, input().split()) # 노드, 간선 graph = [[] for _ in range(N + 1)] # 그래프 입력받기 for _ in range(E): a, b, c = map(int, input().split()) graph[a].append((c, b)) graph[b].append((c, a)) visited = [False] * (N + 1) # 방문체크 리스트 def prim(graph, start): # 그래프, 시작노드 입력받는다, 프림 알고리즘 사용 visited[start] = True # 시작노드 방문체크 distance = 0 # 거리(가중치)를 계산할 변..