자료구조&알고리즘

배경  코드from collections import defaultdictdef solution(keymap, targets): answer = [] MAX_INT = 101 dic = defaultdict(lambda: MAX_INT) for kk in keymap: for i in range(len(kk)): dic[kk[i]] = min(dic[kk[i]], i + 1) for target in targets: cnt = 0 for t in target: if t in dic: cnt += dic[t] else: cnt = ..

def solution(diffs, times, limit): def calculate(level): time = 0 prev_time = 0 n = len(diffs) for i in range(n): if diffs[i]  정답 코드를 보게 되면 이진 탐색을 사용하였다 그 이유는 문제를 분석하면 숙련도의 최솟값을 찾는 문제이기 때문이다정렬 된 범위 내에서 효율적으로 값을 찾기 위해서는 이진 탐색을 생각해보자

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..

해시: 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 변경한 값Key - Value를 저장해둔 자료구조O(log2 n)으로 효율적인 자료구조 이다 해싱을 통해서 메모리에 적재값을 적재하기 위해 나머지를 사용하는데 적은 값으로 설정하면 중복, 높은 값으로 설정하면 과다한 메모리 사용이 된다. 체이닝 방식해시 충돌이 발생할 경우 동일한 해시값에서 해당하는 Key 끼리 연결LinkedList 자료구조를 이용해 해시값 연결 오픈 어드레스 방식해시 충돌 시 다른 버킷에 데이터를 삽입 비어있는 버켓을 찾을 때 까지 탐색

문제  코드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..