알고리즘/백준
-
[백준] 4354번 문자열 제곱 (파이썬)
4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 코드 while 1: s=input() if s==".": break else: s_len=len(s) p_table=[0 for _ in range(s_len)] j=0 for i in range(1,s_len): while j>0 and s[i]!=s[j]: j=p_table[j-1] if s[i]==s[j]: j+=1 p_table[i]=j p_len=s_len-p_table[s_len-1] if s_len % p_len..
-
[백준] 1786번 찾기 (파이썬)
1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m www.acmicpc.net 코드 def find(pattern): lps = [0 for _ in range(len(pattern))] leng = 0 i = 1 while i < len(pattern): if pattern[i] == pattern[leng]: leng += 1 lps[i] = leng i += 1 else: if leng != 0: leng = lps[leng - 1] else: lps[i] = 0 i += 1 return lps def kmp(search, so..
-
[백준] 11723번 집합 (파이썬)
11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 코드 import sys m = int(sys.stdin.readline()) S = set() for _ in range(m): temp = sys.stdin.readline().strip().split() if len(temp) == 1: if temp[0] == "all": S = set([i for i in range(1, 21)]) else: S = set() else: func, x = temp[0], temp[1] x = int(x) if func == "add": S.add(x) el..
-
[백준] 15681번 트리와 쿼리 (파이썬)
15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**9) n, r, q = map(int, sys.stdin.readline().split(" ")) li = [[] for _ in range(n+1)] for _ in range(n-1): u, v = map(int, sys.stdin.readline().split(" ")) li[u].append(v) li[v].append(u)..
-
[백준] 9372번 상근이의 여행 (파이썬)
9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 코드 if __name__ == '__main__': t = int(input()) for _ in range(t): n, m = map(int, input().split()) for _ in range(m): a, b = map(int, input().split()) print(n-1)
-
[백준] 1717번 집합의 표현 (파이썬)
1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 코드 import sys sys. setrecursionlimit(10**6) n, m = map(int, sys.stdin.readline().split(" ")) li = [0] * (n+1) answer_li = [] for i in range(n+1): li[i] = i def find(a): if a == li[a]: return a p = find(li[a]) li[a] = p return p def union..
-
[백준] 4803번 트리 (파이썬)
4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 코드 import sys input = sys.stdin.readline def check(num): visited[num] = True stack = [num] while stack: node = stack.pop(0) for next_node in tree[node]: if tree[node][next_node] == 1: if not visited[next_node]: visited[next_node] = True stack.append(..
-
[백준] 5639번 이진 검색 트리 (파이썬)
5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**8) pre_order = [] cnt = 0 while cnt end: return root = pre_order[start] idx = end + 1 for i in range(start+1, end+1): if pre_order[i] > root: idx = i break post_order(start+1, idx-1) post_order(idx, end) print(pre..