본문 바로가기
반응형

파이썬99

[BOJ][Python]1005 풀이 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net import sys; ssr = sys.stdin.readline sys.setrecursionlimit(10000) def f(node): if dp_delay[node] == -1: results = [] for child in build[node]: child_delay = f(child) results.append(child_delay) dp_delay[node] = delays[no.. 2023. 11. 24.
[BOJ][Python]17070 풀이 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net import sys; ssr = sys.stdin.readline def f(cur_r, cur_c, cur_dir): global ans if cur_r == n-1 and cur_c == n-1: ans += 1 return else: if cur_dir == 0 or cur_dir == 1: if cur_c+1 < n and board[cur_r][cur_c+1] !.. 2023. 10. 30.
[BOJ][Python]15686 풀이 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net import sys; ssr = sys.stdin.readline INF = 2501 def get_chicken_distance(chicken_locations, house_locations): result = [] for house_r, house_c in house_locations: chicken_distance = INF for chick_r, chick_c in c.. 2023. 10. 27.
[BOJ][Python]14938 풀이 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net import sys; ssr = sys.stdin.readline import heapq INF = 16 n, m, r = map(int, ssr().split()) items = list(map(int, ssr().split())) routes = [[] for _ in range(n+1)] ans = 0 for _ in range(r): a, b, l = map(int, ssr().split()) .. 2023. 10. 22.
[BOJ][Python]14502 풀이 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net from collections import deque import copy import sys ssr = sys.stdin.readline def bfs(n, m, board, twos): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] q = deque(twos) while q: v_r, v_c = q.popleft() for dr, dc in dpos: pos_r, pos_c =.. 2023. 10. 21.
[BOJ][Python]13172 풀이 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net import sys input = sys.stdin.readline X = 1_000_000_007 # 자릿수 구분할 때 언더스코어를 사용해도 됨 def get_ni(n, x): result = 1 while x > 0: if x % 2 == 1: result = result * n % X n = n * n % X x //= 2 return result m = int(input()) ans = 0 for _ in range(m): n, s = map.. 2023. 10. 16.
[BOJ][Python]12851 풀이 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net from collections import deque n, k = map(int, input().split()) visited = [0 for _ in range(200001)] visited[n] = 1 q = deque([(n, 0)]) ans = 100001 methods = [] while q: cur_pos, cur_time = q.popleft() .. 2023. 10. 14.
[BOJ][Python]11779 풀이 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 1000000001 def dijkstra(start, end): min_costs = [INF for _ in range(n+1)] min_costs[start] = 0 min_route = [0 for _ in range(n+1)] min_route[start] =.. 2023. 10. 10.
[Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드 이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다. 사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다. .. 2023. 10. 5.
[BOJ][Python]11054 풀이 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net def f(n, arr): dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면 if dp[i] < dp[j]+1: dp[i] = dp[j]+1 return dp n = int(input()) a = list(map(int, input().split())) dp = f(.. 2023. 10. 4.
반응형

티스토리툴바