해킹왕 양선규

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으로 나눠진다고 해서 무조건..

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

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다. 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 # 거리(가중치)를 계산할 변..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) board = [] for _ in range(N): # 미로 입력받기 board.append(list(map(int, input().strip()))) distroy = [[INF for _ in range(N)] for _ in range(N)] # 부순갯수 visited = [[False for _ in range(N)] for _ in range(N)] # 방문목록 def goingNogoing(x, y): # 갈지말지 정하는함수 if 0

from collections import deque import sys input = sys.stdin.readline M, N, H = map(int, input().split()) # 가로, 세로, 높이 5, 3, 2 box = [] for i in range(N * H): # 토마토 입력받기 box.append(list(map(int, input().split()))) visited = [[False] * M for _ in range(N * H)] # 방문목록 box와 똑같이 만들기 def goingNogoing(box, x, y, visited): # 익힐수있는지 고민하는함수 if 0