본문 바로가기

CodingTest/SW Expert Academy

 (60)
[ SW Expert Academy ] 5251. 최소 이동 거리 1차시도 [ 10 / 10 ] PASS 다익스트라 알고리즘 적용시켜서 그냥 고대~로 구현했다. 이해보다는 암기의 영역인 문제였다. 응용이 그다지 필요하지 않아서 import heapq INF = int(1e9) def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist+i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) T = int(inpu..
[ SW Expert Academy ] 5250. 최소 비용 1차 제출. [ 6 / 10 ] Fail 앗 .. 뭐지.. 시간초과로 터졌다... from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] INF = 1e9 def bfs(board, n): dist = [[INF] * n for _ in range(n)] q = deque([(0, 0)]) dist[0][0] = 0 while q: x, y = q.pop() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0
[ SW Expert Academy ] 5249. 최소 신장 트리 1차 시도 [ 8 / 10 ] Fail 헐 .. 시간초과.. 뭐지.. 앞에서부터 빼서 그런가.. def make_set(x, p): p[x] = x return p def find_set(x, p): if p[x] == x: return x return find_set(p[x], p) def union(u, v, p): if u > v: p[find_set(u, p)] = find_set(v, p) else: p[find_set(v, p)] = find_set(u, p) return p def mst_kruskal(g, n): p = {} for i in range(n): p = make_set(i, p) g.sort(key=lambda x:x[2]) mst_cost = 0 while g: u, v, w..
[ SW Expert Academy ] 5248. 그룹 나누기 # 다시 풀기 # 서로소 집합 만드는 알고리즘이... 헷갈린다. 간만에 푸니까 ㅠ 정말 기본 알고리즘을 많이 까먹었구나... 하.. 1 차 제출 [ 3 / 10 ] Fail 일단 기억나는대로 작성한 코드............ def find_set(x): if x == p[x]: return x return find_set(p[x]) def union(x, y): if x > y: p[find_set(x)] = find_set(y) else: p[find_set(y)] = find_set(x) if __name__ == "__main__": T = int(input()) p = {} for test_case in range(1, T+1): answer = 0 n, m = map(int, input().split()) te..
[ SW Expert Academy ] 5247. 연산 보자마다 dfs라고 생각했다.. 그런데 maximum recursion depth exceeded 에러가 나서 읭? 왜 깊이 제한 에러가 나지..? 회귀하도록 조건 잘 걸어준 것 같은데...? def dfs(current, m, depth): global answer if current > 100000 or depth >= answer: return if current == m: answer = min(answer, depth) return dfs(current+1, m, depth+1) dfs(current-1, m, depth+1) dfs(current*2, m, depth+1) dfs(current-10, m, depth+1) if __name__ == "__main__": T = int(input..
[ SW Expert Academy ] 5209. 최소 생산 비용 알고리즘을 이해 하고 문제에 적용시키는 .. 그런 느낌이 든다. 2-3일 새에 또 코테 이해력이 늘어난 느낌이다. 백트래킹이 참 이해 안 가는 파트 중에 하나였는데.. 그동안 그냥 머리에 밀어넣기 암기 식으로 문제 풀어온 성과인지, 해당 사이트의 30분도 안 되는 강의 덕분인 지, 조금은 논리적으로 한 큐에 해당 문제를 풀 수 있었다. 이게 좀 간단한 문제여서 뿌듯함까지는 아니고 신기함이 강렬하게 느껴진다. 이런 사소하고 소중한 작은 성취 덕분에 일주일 간 코테에 집중할 스케줄이 더욱 기대가 된다. 1차 제출 [ 10 / 10 ] Pass def dfs(plants, n, selected, depth, curr_sum): global answer if depth == n: answer = min(answ..
[ SW Expert Academy ] 5208 전기버스2 음 .. 언제쯤 재귀를 자유자재로 사용할까.. 꽤 속상하네? 제출도 못 하고 돌아가지 않는 내 문제 풀이.. def get_min_exchange(n, bus_stops, now, cnt): global min_cnt if min_cnt = n: # 카운트 최솟값인지 체크해서 갱신 min_cnt = min(min_cnt, cnt) return for i in range(now+1, now + bus_stops[now]): get_min_exchange(n, bus_stops, i, cnt + 1) import sys sys.stdin = open("sample.txt", "r") if __name__ == '__main__': T = int(input()) for test_case in range(1, ..
[ SW Expert Academy ] 5207. 이진탐색 1차 시도. [ 4 / 10 ] Fail 뭐지... 뭔데... ?? !!?? 왜 틀리는데... def binary_search(arr, target, start, end): mid = (start+end)//2 if end < start: return 0 if arr[mid] == target: return arr[mid] elif target
[ SW Expert Academy ] 5205. 퀵정렬 1차 시도. [ 10 / 10 ] PASS 너무 유명한 퀵정렬 알고리즘을 이해하고 외우기만 하면 되는 문제였다. 잊지 말기 ~ 😋😉 def partition(a, l, r): pivot = a[l] i = l + 1 j = r while i
[ SW Expert Academy ] 5204. 병합정렬 1차 시도. 시간초과 [ 0 / 10 ] Fail def merge(left, right): result = [] while len(left) > 0 and len(right) > 0: if left[0] 0: result.extend(left) if len(right) > 0: result.extend(right) return result def merge_sort(a): global answer if len(a) right[-1]: answer += 1 return merge(left, right) if __name__ == '__main__': T = int(input()) for test_case in range(T): n = int(input()) a = list(map(int, input()...

티스토리툴바