one Book a Day

0,1 knapsack 선택하느냐 마느냐의 문제는 greedy가 안되기 때문에 점화식을 세울 수 있다면 dp 아니면 완탐이다. K라는 무게값을 1~target값까지 증가시키며 최고 가치를 누적시키면 된다. import sys input = sys.stdin.readline N, K = map(int, input().split()) wei_cost = [[0,0]] dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N): wei_cost.append(list(map(int, input().split()))) for i in range(1, N + 1): for j in range(1, K + 1): weight = wei_cost[..

dp로 풀라고 대놓고 써있는 문제. 대충 계산해보면서 점화식 세우고 바로 풀었다. 사각형에서 사각형 빼고 겹치는 사각형은 더해주는 방식. import sys input = sys.stdin.readline N,M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] dp = [[0]*N for _ in range(N)] for i in range(N): for j in range(N): dp[0][0] = matrix[0][0] if i==0 and j>0: dp[i][j] = dp[i][j-1]+matrix[i][j] elif j==0 and i>0: dp[i][j] = dp[i-1][j]+matrix..

이해하는데 꽤 오래 걸렸다. dp를 대각선으로 그려야 답을 구할 수 있는 문제로 아주 신박하고 연습이 필요한 문제일 것 같다. dp[i][i+j]로 놓고 i를 증가시키면 양쪽이 1,1씩 증가해 대각선 배열을 먼저 연산 할 수 있으며 j가 늘어나면 가운데 대각선에서 한칸 더 멀어진 배열을 연산하게 되는 식이다. 즉 2개씩 묶은 행렬을 계산하고(AB,BC,CD,CE) 그 값을 가지고 3개씩 묶은 행렬을 계산. min(AB*C or A*BC) 그걸 가지고 4개씩 묶은 행렬을 계산min(A*BCD,AB*CD,ABC*D) N*N 인접 행렬에서 대각선으로 배열을 채우는법을 이해할 수 있었고 차후 다른 문제에서도 쓸만한아이디어인 것 같다. 행렬의 곱셈이 이루어지는 숫자는 [앞행렬의 행값 * 앞행렬의 열값(==뒷행렬의..

경우의 수를 만들어 연산자를 대입하는 문제였다. 보자마자 DFS가 생각나서 설계했는데 처음에는 +-보다 */연산을 먼저 처리하는 줄 알고 문자열로 calculate를 쌓고 eval answer에 삽입햇으나 테케 통과 못하고 문제 다시일어보니 앞에서부터 순차 연산... str에서 int로 바꾸고 진입시마다 계산해주면서 들어갔다. import sys input = sys.stdin.readline def DFS(idx,calculate): if idx==N: answer.append(calculate) return num = seqs[idx] for operator in '+-*/': if operator == '+'and opers[0]: opers[0] -=1 DFS(idx+1,calculate+num)..

너무나 명백하게 플로이드 워셜을 쓰라고 문제에 주어졌다. 플로이드 워셜을 통해 거리배열을 얻어내고 치킨집 2마리를 조합으로 묶어내면서 각 거리의 합을 미니멈으로 비교하는 문제이다. 인접리스트를 사랑하는 입장에서 인접행렬문제는 늘 까다롭다. 아직 코드가 손에 안익어서 그럴수도.. import sys input = sys.stdin.readline N,M = map(int,input().split()) graph = [[float('inf') for _ in range(N)] for _ in range(N)] for i in range(M): a,b = map(int,input().split()) graph[a-1][b-1] = 2 graph[b-1][a-1] = 2 for i in range(N): gra..

문제해결에 선행또는 후행 하는 순서가 있으면 위상정렬을 이용하면 쉽게 풀 수 있다. 위상정렬이란 위상이 0 즉 앞뒤에 뭐가 없는 node부터 위로 찬찬히 쌓아 나가는 것. 위상0인 문제를 해결했으면 그 바로 연결된 노드들의 위상을 1씩 낮추면서 계산해 나간다. 나는 배열에 쌓기 위해서 앞에 나와야 하는 노드를 위상0으로 두었지만 반대로 뒤가 없는 노드들을 먼저 쌓고 역순으로 출력할 수도 있을 것이다. import sys from collections import defaultdict,deque input = sys.stdin.readline def topological_sorting(): queue = deque() for i in range(1, N+1): if level[i] == 0: queue.a..

이진트리?? 최대 두개의 자식 노드를 가지는 트리형태의 자료구조. 단순 저장보다는 탐색혹은 정렬을 위함. 힙도 이진트리의 일종. 이진 탐색트리? 이진트리의 특수한 경우. 모든 노드에 대해 그 왼쪽 자식들의 값이 현재 노드보다 작거나 같으며 오른쪽 자식들의 값이 현재 노드의 값보다 크다는 조건을 만족하면 이진 탐색 트리가 된다(작은값은 왼쪽 큰값은 오른쪽에 저장.) 가장 처음 입력된 값이 root 클래스 정의, 초기화 노드 클래스 정의 class Node(object): def __init__(self, data): self.data = data self.left = self.right = None 이진 탐색 트리 클래스 정의 class BinarySearchTree(object): def __init__..

모든 노드에서 모든 노드까지의 정보를 구해야하는 플로이드 워셜 문제다. 요새 최단거리 문제해결 연습을 많이하고있는데 플로이드 워셜의 핵심은 이것. "내가 저기 갈껀데 다른곳의 정보를 이용해서 가는게 빠르냐 아니면 그냥 가는게 빠르냐?" 이거다. 여기선 전자를 이용할 수 있느냐를 물어보는 문제. (다른곳의 정보는 나뿐만아니라 도착지에서도 알고있어야한다.) 알고있다면 1 아니면 0 import sys input = sys.stdin.readline N, M = map(int, input().split()) knowing_tall = [[0 for _ in range(N)] for _ in range(N)] # 플로이드 워셜은 인접행렬을 쓴다. for i in range(M): high, low = map(i..

LIS 시리즈 문제중 하나이다. 역순으로도 구해서 각 지점 카운트합이 가장 높아지는 부분이 꺽이는 부분. N = int(input()) A = [0] + list(map(int, input().split())) LDS = [1]*(N+1) LIS = [1]*(N+1) Bi = [] # 바이토닉 수열의 핵심은 앞에서 LIS하고 역순 LIS dp를 각각 만들어 # 두 dp 인자의 합 = 올라갔다 내려오는 cnt를 만드는 것. # 싸피 CT문제 예제로 나오는 문제라 아이디어는 매우 쉬웠다. for i in range(1,N+1): for j in range(1,i): if A[i]>A[j] and LIS[i]A[-j] and LDS[-i]

그냥 문제 나온대로 읽고 BFS만들어서 풀었다. 더 좋은 방법이 있을지도.. import sys input = sys.stdin.readline from collections import deque def BFS(i,j): candy_max = 0 queue = deque() queue.append([i,j]) visited_candy = [[-1 for _ in range(M)] for _ in range(N)] visited_candy[i][j] = maze[i][j] while queue: x,y = queue.popleft() if x==N-1 and y==M-1: if visited_candy[x][y] > candy_max: candy_max = visited_candy[x][y] for nx..