본문 바로가기

전체글118

[Baekjoon-Python] 1765 : 닭싸움 팀 정하기 https://www.acmicpc.net/problem/1765 접근 유니온-파인드를 사용하여 인간관계를 합친다. 풀이 from sys import stdin def find(x): if x != friend[x]: friend[x] = find(friend[x]) return friend[x] def union(a, b): a, b = find(a), find(b) if a == b: return friend[b] = a n, m = int(stdin.readline()), int(stdin.readline()) friend = [i for i in range(n + 1)] enemy = [[] for _ in range(n + 1)] for _ in range(m): letter, p, q = st.. 2024. 1. 23.
[Baekjoon-Python] 1106 : 호텔 https://www.acmicpc.net/problem/1106 접근 최소 비용을 메모이제이션한다. dp의 인덱스를 고객 수로 설정한다. 풀이 from sys import stdin c, n = map(int, stdin.readline().split()) city = [list(map(int, stdin.readline().split())) for _ in range(n)] dp = [1e9] * (c + 1) # (1) dp[0] = 0 for i in range(1, c + 1): for cost, customer in city: if i 2024. 1. 23.
[Baekjoon-Python] 4179 : 불! https://www.acmicpc.net/problem/4179 접근 불과 지훈 좌표를 따로 저장한다. 해당 분동안 불을 먼저 bfs로 확산한 후 지훈을 bfs 탐색한다. 풀이 from sys import stdin from collections import deque def escape(): maze[jihoon[0][0]][jihoon[0][1]] = -1 minutes = 0 while jihoon: minutes += 1 spread_fire() for _ in range(len(jihoon)): # (1) r, c = jihoon.popleft() for i in range(4): nr, nc = r + direction[i], c + direction[3 - i] if is_out_of_ra.. 2024. 1. 23.
[Baekjoon-Python] 1509 : 팰린드롬 분할 https://www.acmicpc.net/problem/1509 접근 팰린드롬은 거꾸로 읽어도 제대로 읽은 것과 같은 문장을 의미한다. 현재 문자열의 시작 문자와 끝 문자가 같고 내부 문자열이 팰린드롬이면 현재 문자열은 팰린드롬이다. 풀이 from sys import stdin letter = stdin.readline().rstrip() n = len(letter) palindrome = [[0] * n for _ in range(n)] dp = [2500] * (n + 1) dp[-1] = 0 for e in range(n): for s in range(e + 1): if letter[s] == letter[e] and (e - s < 2 or palindrome[s + 1][e - 1]): # (.. 2024. 1. 23.
[Baekjoon-Python] 1717 : 집합의 표현 https://www.acmicpc.net/problem/1717 접근 유니온-파인드를 사용하여 두 집합을 합친다. 풀이 from sys import stdin, setrecursionlimit def find(x): if x != parent[x]: parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a < b: parent[b] = a else: parent[a] = b setrecursionlimit(10**6) n, m = map(int, stdin.readline().split()) parent = [i for i in range(n + 1)] for _ in range(m): operat.. 2024. 1. 23.
[Baekjoon-Python] 2468 : 안전 영역 https://www.acmicpc.net/problem/2468 접근 비의 양을 0 ~ 지역의 최고 높이 - 1까지 순회하면서 안전한 영역의 개수를 구한다. 안전한 영역은 bfs 탐색한다. 풀이 from sys import stdin from collections import deque def bfs(r, c, rain, q: deque): q.append((r, c)) while q: r, c = q.popleft() for i in range(4): nr, nc = r + direction[i], c + direction[3 - i] if is_out_of_range(nr, nc) or visited[nr][nc] or city[nr][nc] = n or c = n n = int(.. 2024. 1. 23.
[Baekjoon-Python] 20437 : 문자열 게임 2 https://www.acmicpc.net/problem/20437 접근 알파벳의 ASCII - 97을 인덱스로 사용한다. 알파벳마다 문자열의 인덱스를 저장한다. 알파벳을 순회하면서 k개 포함하는 인덱스 2개를 찾고, 문자열의 길이를 구한다. 최소 길이, 최대 길이를 갱신한다. 풀이 from sys import stdin def play(): min_len, max_len = 1e9, 0 for alpha in alphabet: if len(alpha) < k: # (1) continue for i in range(len(alpha) - k + 1): length = alpha[i + k - 1] - alpha[i] + 1 # (2) if length < min_len: min_len = length i.. 2024. 1. 23.
[Baekjoon-Python] 20061 : 모노미노도미노 2 https://www.acmicpc.net/problem/20061 접근 새로운 행은 앞에서 추가되고 0, 1행에 블록이 존재할 때 뒤부터 삭제되기 때문에 데큐를 사용한다. blue는 x를 열로 두고 green과 같이 진행한다. 열이 가득 찬 행을 먼저 삭제하고 0, 1행을 확인한다. 풀이 from sys import stdin from collections import deque def find_top(board, c): # (1) for r in range(2, 6): # (2) if board[r][c] == 1: return r - 1 return 5 def remove_full_col(): global res for board in blue, green: for r in range(2, 6): .. 2024. 1. 23.
[Baekjoon-Python] 17143 : 낚시왕 https://www.acmicpc.net/problem/17143 접근 격자의 열 크기(C)가 5라면 상어가 이동할 때 인덱스(c)는 0, 1, 2, 3, 4, 3, 2, 1, ...이 된다. 상어가 움직일 때 인덱스에 사이클이 발생한다. 사이클 길이는 2 * (C - 1)이다. 상어의 이동 후 인덱스를 중복없이 한 번에 찾도록 최적화해야 시간 초과가 발생하지 않는다. 열, 오른쪽 방향 기준으로 상어의 이동 후 인덱스는 (현재 인덱스 + 속력) % 열 사이클 길이 즉, (c + s) % (2 * (C - 1))이다. 풀이 from sys import stdin def catch(j): for i in range(R): # (1) if (i, j) in sharks: return sharks.pop((i.. 2024. 1. 23.
[Baekjoon-Python] 9251 : LCS https://www.acmicpc.net/problem/9251 접근 첫 번째 문자열의 알파벳을 두 번째 문자열과 비교하면서 공통 부분 수열 길이를 메모이제이션한다. 풀이 from sys import stdin letter_1 = stdin.readline().rstrip() letter_2 = stdin.readline().rstrip() dp = [0] * len(letter_2) for let_1 in letter_1: cnt = 0 # (1) for i, let_2 in enumerate(letter_2): if dp[i] > cnt: # (2) cnt = dp[i] elif let_1 == let_2: # (3) dp[i] = cnt + 1 print(max(dp)) (1) cnt는 전 인덱스.. 2024. 1. 22.

티스토리툴바