본문 바로가기

전체글118

[Baekjoon-Python] 17140 : 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 접근 Counter 클래스를 사용하여 등장 횟수를 구한다. C 연산은 열을 행으로 변환해서 정렬하고 다시 열로 변환한다. 풀이 from sys import stdin from collections import Counter def sort(array): res, max_len = [], 0 for arr in array: counter = Counter(arr) # (1) counter.pop(0, None) # (2) row = sorted(counter.items(), key=lambda x: (x[1], x[0])) # (3) row = list(sum(row, ())) # (4) if len(row) > 100: # (5) row.. 2024. 1. 21.
[Baekjoon-Python] 16236 : 아기 상어 https://www.acmicpc.net/problem/16236 접근 bfs 탐색하여 물고기를 찾는다. 상어보다 크기가 작은 물고기를 찾으면 거리와 물고기 좌표를 저장한다. 빈 칸이거나 상어와 크기가 같다면 이동한다. 먹을 수 있는 물고기가 여러 마리라면 거리가 가장 가까운 물고기를, 거리가 가장 가까운 물고기가 여러 마리라면 행이 가장 작은 물고기를, 행이 가장 작은 물고기가 여러 마리라면 열이 가장 작은 물고기를 먹는다. 풀이 from sys import stdin from collections import deque def bfs(r, c): q = deque([(0, r, c)]) visited = [[False] * n for _ in range(n)] visited[r][c] = True .. 2024. 1. 21.
[Baekjoon-Python] 14890 : 경사로 https://www.acmicpc.net/problem/14890 접근 행과 열을 구분하여 두 번 순회한다. 높이 차이가 2 이상이면 경사로를 놓을 수 없다. 경사로를 놓았을 때 방문 처리하여 경사로가 겹치는 경우를 확인한다. 풀이 from sys import stdin def can_move(road): slope = [False] * N i = 1 while i 1: # (1) return False if road[i - 1] > road[i]: # (2) for j in range(i, i + L): if j >= N or road[j] != road[i]: return False slope[j] = True i += L elif .. 2024. 1. 20.
[Baekjoon-Python] 16926 : 배열 돌리기 1 https://www.acmicpc.net/problem/16926 접근 함께 회전하는 배열을 계층이라고 할 때, 각 계층을 순회한다. 계층의 총 개수는 min(n, m) / 2이다. i번째 계층의 시작 좌표 (x, y)는 (i , i)이다. (i , i)부터 반시계 방향으로 i번째 계층의 값을 큐에 삽입한다. 큐를 r만큼 회전한 후 큐에서 값을 삭제하면서 (i , i)부터 반시계 방향으로 값을 저장한다. 풀이 from sys import stdin from collections import deque n, m, r = map(int, stdin.readline().split()) arr = [stdin.readline().split() for _ in range(n)] q = deque() for i .. 2024. 1. 20.
[Baekjoon-Python] 14501 : 퇴사 https://www.acmicpc.net/problem/14501 접근 날짜를 역순으로 순회하면서 해당 날짜 수익의 최댓값을 메모이제이션한다. 현재 날짜의 수익은 현재와 T일 뒤의 수익의 합, 다음날의 수익 중 최댓값이다. 즉, 오늘 상담해서 T일 뒤에 상담할 것인지, 오늘 상담을 포기하고 내일 상담할 것인지 선택하는 것이다. 풀이 from sys import stdin n = int(stdin.readline()) consulting = [tuple(map(int, stdin.readline().split())) for _ in range(n)] dp = [0] * (n + 1) for d in range(n - 1, -1, -1): # (1) t, p = consulting[d] if d + t >.. 2024. 1. 20.
[Baekjoon-Python] 15685 : 드래곤 커브 https://www.acmicpc.net/problem/15685 접근 0:우, 1:상, 2:좌, 3:하로 방향 인덱스를 정한다. k세대 드래곤 커브의 방향은 k - 1세대 드래곤 커브의 방향을 역순으로 순회하면서 1씩 증가한다. 풀이 from sys import stdin dragon = [[False] * 101 for _ in range(101)] direction = [(0, 1), (-1, 0), (0, -1), (1, 0)] for _ in range(int(stdin.readline())): x, y, d, g = map(int, stdin.readline().split()) dragon[y][x] = True # (1) y += direction[d][0] x += direction[d].. 2024. 1. 20.
[Baekjoon-Python] 15684 : 사다리 조작 https://www.acmicpc.net/problem/15684 접근 각각의 세로선마다 놓여진 가로선 개수가 홀수이면 원래 세로선으로 돌아올 수 없다. 즉, 세로선마다 놓여진 가로선 개수가 모두 짝수여야 한다. 세로선을 dfs 탐색해서 가로선이 놓여있지 않으면 가로선을 추가한다. 추가한 가로선 개수가 3개보다 많아질 경우 백트래킹한다. 풀이 from sys import stdin def is_same_vertical(): # (1) for j in range(1, n + 1): start = j for i in range(1, h + 1): if ladder[i][j]: j = ladder[i][j] if start != j: return False return True def dfs(cnt, dep.. 2024. 1. 18.
[Baekjoon-Python] 15683 : 감시 https://www.acmicpc.net/problem/15683 접근 각각의 cctv마다 감시할 수 있는 경우의 수 cctv 경우의 수 1번 4 2번 2 3번 4 4번 4 5번 1 cctv를 dfs 탐색해서 감시할 수 있는 모든 경우의 수를 구한다. 탐색이 끝나면 사각 지대의 크기를 구한다. 풀이 from sys import stdin def dfs(office, idx): global res if idx >= len(cctv): blind_spot = sum(o.count(0) for o in office) res = min(res, blind_spot) # (1) return r, c = cctv[idx] if office[r][c] == 1: # (2) for i in range(4): tmp_.. 2024. 1. 17.
[Baekjoon-Python] 14891 : 톱니바퀴 https://www.acmicpc.net/problem/14891 접근 톱니바퀴를 데큐로 사용하여 회전하는 방향에 따라 삽입, 삭제한다. 톱니바퀴의 인덱스를 0:12시, 2:3시, 4:6시, 6:9시 두고 회전시킨 톱니바퀴부터 dfs 탐색한다. 톱니바퀴를 바로 회전시키면 조건을 만족하지 않는 톱니바퀴에 영향을 미치기 때문에 조건을 만족하는 톱니바퀴를 전부 찾은 후 한 번에 회전시킨다. 현재 톱니바퀴의 6번 인덱스가 오른쪽 톱니바퀴의 2번 인덱스와 같지 않으면 오른쪽 톱니바퀴를 반대 방향으로 회전시킨다. 현재 톱니바퀴의 2번 인덱스가 왼쪽 톱니바퀴의 6번 인덱스와 같지 않으면 왼쪽 톱니바퀴를 반대 방향으로 회전시킨다. k번 회전시킨 후 0번 인덱스가 S극이면 톱니바퀴 번호만큼 1을 왼쪽으로 shift해서.. 2024. 1. 17.
[Baekjoon-Python] 14502 : 연구소 https://www.acmicpc.net/problem/14502 접근 빈 칸 중에서 3개를 조합으로 선택해서 벽을 세운다. 바이러스를 bfs 탐색하여 빈 칸이면 전염시킨다. 빈 칸의 개수를 구한다. 풀이 from sys import stdin from itertools import combinations from collections import deque def spread(new_wall): tmp_lab = [i[:] for i in lab] for r, c in new_wall: tmp_lab[r][c] = 1 # (1) q = deque(virus) infection = 0 while q: r, c = q.popleft() infection += 1 for i in range(4): nr, .. 2024. 1. 17.

티스토리툴바