본문 바로가기

BOJ 알고리즘 (T아카데미)

 (9)
2667번: 단지번호 붙이기 (그래프, BFS) www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net # 단지번호 붙이기 # https://www.acmicpc.net/problem/2667 (그래프, BFS) from collections import deque def bfs(x, y, area): dq = deque([(x, y)]) while dq: x, y = dq.popleft() if mp[x][y] == 0 or visited[x][y]: continue global count count += 1 ..
13116번: 30번 (그래프, 부모배열) www.acmicpc.net/problem/13116 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net # 30번 # https://www.acmicpc.net/problem/13116 (그래프, 부모배열) # PyPy3 def common_parent(a, b): parents_of_a = [] while a != 1: parents_of_a.append(a) a = a // 2 parents_of_b = [] while b != 1: parents_of_b.append(b) b ..
2644번: 촌수계산 (그래프, BFS) www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net # 촌수계산 # https://www.acmicpc.net/problem/2644 (그래프, BFS) from collections import deque def bfs(graph, st, ed): visited = [] queue = deque([(st, 0)]) while queue: v, cnt = queue.popleft() if v in visited: continue visited.a..
11866번: 요세푸스 문제 0 (구현, 큐) - Tacademy www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net # 요세푸스 문제 0 # https://www.acmicpc.net/problem/11866 (구현, 큐) from collections import deque def nums(n, k): ret, queue = [], deque(range(1, n + 1)) while queue: for _ in range(k - 1): queue.append(queue.popleft()) ret.append(queue.popleft()) return ret n, k = map(int, input().spli..
9012번: 괄호 (구현, 스택) - Tacademy www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net # 괄호 # https://www.acmicpc.net/problem/9012 (구현, 스택) def ckeck(s): stack = list() for x in list(s): if x == "(": stack.append(x) else: if len(stack) == 0 or stack[-1] == ")": return "NO" stack.pop() if len(stack) >..
11729번: 하노이탑 (구현, 재귀) - Tacademy www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net # 하노이탑 # https://www.acmicpc.net/problem/11729 (재귀) def hanoi(n, from_p, to_p): if n == 1: return print(f"{from_p} {to_p}") aux_p = 6 - from_p - to_p hanoi(n - 1, from_p, aux_p) print(f"{from_p} {to_p}") hanoi(n - 1, aux_p, ..
1629번: 곱셈 (구현, 수학) - Tacademy www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # 곱셈 # https://www.acmicpc.net/problem/1629 (구현) # 거듭제곱 def cpow(a, b, mod): # a의 11승 # 11 = 1011 (2진수) # a ** 11 = a ** (1+2+0+8) = (a) * (a**2) * (a**8) ret = 1 while b: b, r = divmod(b, 2) if r != 0: ret = ret * a % mod a = a * a % mod return ret a, b, mod = map(in..
2484번: 주사위 네개 (구현) - Tacademy www.acmicpc.net/problem/2484 2484번: 주사위 네개 첫째 줄에는 참여하는 사람 수 N이 주어지고 그 다음 줄부터 N개의 줄에 사람들이 주사위를 던진 4개의 눈이 빈칸을 사이에 두고 각각 주어진다. www.acmicpc.net # 주사위 네개 # https://www.acmicpc.net/problem/2484 (구현) def reward(): # 3 3 3 3 => [(3, 4)] # 3 3 6 3 => [(3, 3), (6, 1)] # 2 2 6 6 => [(2, 2), (6, 2)] # 2 2 6 4 => [(2, 2), (6, 1), (4, 1)] # 2 3 4 5 => [(5, 1), (4, 1), (3, 1), (2, 1)] a = sorted(list(map(int, ..

티스토리툴바