https://www.acmicpc.net/problem/1294 코드import sysfrom heapq import heappush, heappopinput = sys.stdin.readlinedef solution(): N = int(input()) heap = [] M = 0 for i in range(N): word = input().rstrip() heappush(heap, word+'_') M += len(word) res = '' for _ in range(M): word = heappop(heap) res += word[0] heappush(heap, word[1:]) pri..
자료구조&알고리즘/백준
문제 제목이 참 재밌다 벽 부수고 이동이라현실적으로는 쉽지만 코드로 구현하기 어려웠다ㅠ 문제 코드from collections import dequedx = [0, -1, 0, 1]dy = [1, 0, -1, 0]def bfs(): visit = [[[0]*2 for _ in range(M)] for _ in range(N)] visit[0][0][0] = 1 while q: x,y, wall = q.popleft() if x == N-1 and y == M-1: return visit[x][y][wall] for k in range(4): xx = x + dx[k] yy = y + dy[k..
문제 코드def min_cost_to_free_memory(N, M, memories, costs): max_cost = sum(costs) dp = [0] * (max_cost + 1) for i in range(N): memory = memories[i] cost = costs[i] for j in range(max_cost, cost -1, -1): dp[j] = max(dp[j], dp[j-cost] + memory) for k in range(max_cost + 1): if dp[k] >= M: return k return -1N,M = map..
문제 코드import sysinput = sys.stdin.readlinen = int(input().strip())matrices = []for _ in range(n): r, c = map(int, input().split()) matrices.append((r, c))dp = [[0] * n for _ in range(n)]for length in range(1, n): for i in range(n - length): j = i + length dp[i][j] = float('inf') for k in range(i, j): cost = dp[i][k] + dp[k + 1][j] + matrices[i][0] * matri..
진짜 어려웠다 이해하려고 3일동안 코드를 보았다 문제 코드def min_merge_cost(files): n = len(files) dp = [[0] * n for _ in range(n)] # dp[i][j]: i부터 j까지 파일을 합치는데 필요한 최소 비용 # 파일의 부분합 미리 계산 prefix_sum = [0] * (n + 1) for i in range(1, n + 1): prefix_sum[i] = prefix_sum[i - 1] + files[i - 1] # 대각선 길이 1부터 n-1까지 순회 for length in range(1, n): for i in range(n - length): j = i + l..
위 문제의 핵심을 절대값을 인덱스로 가지며 기존의 값을 가지고 있어야 한다는 점입니다. 문제 코드import sys, heapq as hqinput = sys.stdin.readlinen = int(input())ls = []for _ in range(n): num = int(input()) if num == 0: print(hq.heappop(ls)[1] if ls else 0) else: hq.heappush(ls, (abs(num), num)) 설명heapq 모듈을 import 합니다절대값을 구해야 하기 때문에 튜플의 형태로 넣습니다그렇게 되면 기존의 값 (절댓값, 실제값)의 형태로 힙에 저장되게 됩니다 그 뒤 절대 값을 기준으로 정렬된 힙에 실제 값을 ..
https://www.acmicpc.net/problem/12015예전에 가장 긴 증가하는 부분 수열 문제를 풀었었는데 이번에는 다른 점이 메모리 부분이 다문제 코드import sysinput = sys.stdin.readlinen = int(input())cases = list(map(int, input().split()))lis = [0]for case in cases: if lis[-1] 설명이진 탐색을 사용하여 효율적으로 위치를 찾는게 목표입니다수열의 각 원소 case에 대해 lis 리스트에서 적절한 위치를 찾아 삽입하거나 대체하는 코드 입니다 큰 값은 단순 추가: 현재 수열의 값이 lis의 마지막 값보다 크면 lis에 그대로 추가합니다.작거나 같은 값은 대체: 그렇지 않으면 이진 탐색을..
배경https://www.acmicpc.net/problem/10816 코드import sysinput = sys.stdin.readlineN = int(input())cards = sorted([*map(int, input().split())])M = int(input())candidate = [*map(int, input().split())]count = dict()for card in cards: if count.get(card, False): count[card] += 1 else: count[card] = 1def binarySearch(arr, target, start, end): if start > end: return 0 ..
