[백준/약점체크] 2252번: 줄 세우기
2022. 10. 11. 18:43
컴퓨터/코딩테스트
[문제] [코드] 이 문제는 위상 정렬을 이용해서 풀면 된다. 위상 정렬에 대한 내용은 여기에 정리해 두었다. https://woo-niverse.tistory.com/237?category=1038170 정렬 알고리즘 : 위상 정렬 (Topological Sorting) 방향이 있는 그래프의 정점들을 방향대로 나열하는 것 위상 정렬의 예시 예시를 위해 자랑스러운 나의 전공, 국문학과의 국어학 커리큘럼을 가져와보았다. 보통 'OO론' 과목은 'OOO의이해' 수업을 woo-niverse.tistory.com 먼저, 큐를 이용한 방법 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split(..
[백준/약점체크] 16916번: 부분문자열
2022. 10. 7. 09:39
컴퓨터/코딩테스트
[문제] 링크: https://www.acmicpc.net/problem/16916 [내 코드] 문제를 해결하기 위해서 KMP 알고리즘을 공부하고 구현했다. 자세한 내용은 이 글을 참고. def LPS(pat, lps): leng = 0 i = 1 while i < len(pat): if pat[i] == pat[leng]: leng += 1 lps[i] = leng i += 1 else: if leng == 0: lps[i] = 0 i += 1 else: leng = lps[leng-1] def KMP(txt, pat): N = len(txt) M = len(pat) lps = [0] * M LPS(pat, lps) i = j = 0 while i < N: if pat[j] == txt[i]: j +=..
[백준/약점체크] 1197번: 최소 스패닝 트리
2022. 10. 5. 18:27
컴퓨터/코딩테스트
[문제] [정답] 최소 신장 트리는 크루스칼 알고리즘이나 프림 알고리즘으로 찾을 수 있다. 크루스칼 알고리즘과 이를 위한 합집합 찾기 알고리즘 그리고 프림 알고리즘에 대한 글을 별도로 작성했으니 참고하면 되겠다. 크루스칼 알고리즘 import sys input = sys.stdin.readline V, E = map(int, input().split()) Vroot = [i for i in range(V+1)] Elist = [] for _ in range(E): Elist.append(list(map(int, input().split()))) Elist.sort(key=lambda x: x[2]) def find(x): if x != Vroot[x]: Vroot[x] = find(Vroot[x]) r..
[백준/약점체크] 1916번: 최소비용 구하기
2022. 10. 3. 23:50
컴퓨터/코딩테스트
[문제] [내 코드] N = int(input()) # 도시의 개수 M = int(input()) # 버스의 개수 # 버스의 출발도시, 도착도시, 비용 graph = {} for n in range(N): graph[n+1] = {} for _ in range(M): a, d, c = map(int, input().split()) graph[a][d] = c start, end = map(int, input().split()) def bellman_ford(graph, start): dist = {} for node in range(1, N+1): dist[node] = float('inf') dist[start] = 0 # V-1 번 반복 for i in range(N-1): for node in gr..
[백준/약점체크] 1806번: 부분합
2022. 9. 25. 22:27
컴퓨터/코딩테스트
[문제] [내 코드] 먼저 시간 초과 오류가 떴던 코드다 N, S = map(int, input().split()) li = list(map(int, input().split())) def finder(answer): while True: for start in range(N): end = start+answer if sum(li[start:end]) >= S: return answer answer += 1 return 0 print(finder(0)) - answer를 두 인덱스의 간격으로 두고, 슬라이싱하여 합을 구했다 - 시간 초과 오류!! 그 다음, 통과한 코드다 N, S = map(int, input().split()) data = list(map(int, input().split())) sta..
[백준/약점체크] 1700번: 멀티탭 스케줄링
2022. 9. 24. 23:17
컴퓨터/코딩테스트
[문제] [내 코드] -> 틀렸습니다!! N, K = map(int, input().split()) usage = list(map(int, input().split())) plug = [] res = 0 for i in range(K): if usage[i] in plug: continue elif len(plug) < N: plug.append(usage[i]) else: wait = [] for j in usage[i:]: if j in plug: wait.append(j) if len(wait) == N: break if set(plug) - set(wait): obj = (set(plug) - set(wait)).pop() else: obj = wait[-1] plug[plug.index(obj)..
[백준/약점체크] 1062번: 가르침
2022. 9. 24. 21:55
컴퓨터/코딩테스트
[문제] [내 코드] N, K = map(int, input().split()) words = [input() for _ in range(N)] basics = ['t', 'i', 'c', 'a', 'n'] if K < len(basics): print(0) elif K == 26: print(len(words)) else: result = 0 unlearned = list(set([w for word in words for w in word if w not in basics])) # unlearned 중에서 r개를 새로 배운다 n = len(unlearned) r = K - len(basics) def dfs(idx, ls): global result if len(ls) == r: tmp = 0 lea..
[백준/약점체크] 14719번: 빗물
2022. 9. 18. 19:22
컴퓨터/코딩테스트
[문제] [내 코드] H, W = map(int, input().split()) blocks = list(map(int, input().split())) result = 0 for i in range(1, H+1): level = [] for j in range(len(blocks)): if i > blocks[j]: level.append(0) else: level.append(1) for l in range(len(level)): before = sum(level[:l]) after = sum(level[l:]) if (before>0) and (after>0) and (level[l] == 0) : result+=1 print(result) - 굉장히 어거지로 풀었다.. 층마다 0과 1로 블럭을 쌓..