본문 바로가기
반응형

전체 글288

[BOJ][Python]11444 풀이 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net def matrix_multiplication(matrix1, matrix2): result = [[0, 0], [0, 0]] for i in range(2): for j in range(2): for k in range(2): result[i][j] += matrix1[i][k]*matrix2[k][j] result[i][j] %= 1000000007 return result n = int(input()) ans = [[1, 0], [0, 1]] fib_mat = [[1,.. 2023. 8. 19.
[Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드 너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다. 이 그래프를 기본으로 해서 알아보겠습니다. 깊이 우선 탐색(Depth First Search) 먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊.. 2023. 8. 12.
[BOJ][Python]11404 풀이 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys ssr = sys.stdin.readline INF = 10000001 n = int(ssr()) m = int(ssr()) min_cost = [[INF for _ in range(n)] for _ in range(n)] for _ in range(m): a, b, c = map(int, ssr().split()) min_cost[a-1][b-1] = min(min_cost[.. 2023. 8. 11.
[BOJ][Python]9251 풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net s1, s2 = input(), input() lcs = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)] for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): if s1[i-1] == s2[j-1]: lcs[i][j] = lcs[i-1][j-1].. 2023. 8. 10.
[BOJ][Python]2206 풀이 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline INF = 1000001 def bfs(): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] visited = [[0 for _ in range(m)] for _ in range(n)] visited[0][0] = 1 q = de.. 2023. 8. 9.
[BOJ][Python]1918 풀이 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net def f(equation): priority = {'+':1, '-':1,'*':2,'/':2,'(':0} stack = [] for i in equation: if i.isalpha(): print(i, end='') else: if len(stack) == 0 or i == '(': stack.append(i) elif i == ')': while True: tmp = stack.pop(.. 2023. 8. 8.
[BOJ][Python]28432 풀이 https://www.acmicpc.net/problem/28432 28432번: 끝말잇기 첫 줄에 끝말잇기 기록의 길이 $N$ 이 주어집니다. $(1 \le N \le 100)$ 둘째 줄부터 다음 $N$개의 줄에는 끝말잇기의 기록 $S_1, \cdots, S_N$이 한 줄에 하나씩 주어집니다. 여기서, 하나의 $S_i$는 “?” 로 www.acmicpc.net import sys ssr = sys.stdin.readline n = int(ssr()) s = [] loc = 0 for i in range(n): word = ssr().rstrip() s.append(word) if word == '?': loc = i m = int(ssr()) first, last = '', '' a = '' if n .. 2023. 8. 7.
[BOJ][Python]1738 풀이 https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어 www.acmicpc.net import sys ssr = sys.stdin.readline INF = 987654321 def bellman_ford(): for i in range(1, n+1): for cur_node, next_node, next_cost in edges: cost = max_cost[cur_node] + next_cost if max_cost[cur_node] != -IN.. 2023. 8. 7.
[BOJ][Python]1865 풀이 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net import sys ssr = sys.stdin.readline INF = 10001 def bellman_ford(): min_time = [INF for _ in range(n+1)] min_time[1] = 0 for i in range(1, n+1): for j in range(1, n+1): for next_node, next_time in routes[j]: if min_t.. 2023. 8. 6.
[BOJ][Python]11657 풀이 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net import sys ssr = sys.stdin.readline INF = 5000001 def bellman_ford(): for i in range(n): for cur_node, next_node, next_time in routes: if min_time[cur_node] != INF and min_time[cur_node]+ne.. 2023. 8. 5.
반응형

티스토리툴바