본문 바로가기

전체글118

[Baekjoon-Python] 2493 : 탑 https://github.com/co-niverse/algorithm-study/pull/111 접근 스택 맨 위의 탑보다 현재 탑의 높이가 더 높으면 높이가 작거나 같을 때까지 스택을 삭제한다. 스택 맨 위의 탑보다 현재 탑의 높이가 작거나 같으면 스택 맨 위의 탑의 인덱스를 저장한다. 스택에 현재 탑을 삽입한다. 풀이 from sys import stdin n = int(stdin.readline()) res = [0] * n stack = [] for i, height in enumerate(map(int, stdin.readline().split())): if stack and stack[-1][0] < height: # (1) while stack and stack[-1][0] < height.. 2024. 1. 21.
[Baekjoon-Python] 17825 : 주사위 윷놀이 https://www.acmicpc.net/problem/17825 접근 게임판을 아래와 같이 설정한다. r = 0: 10, 20, 30에 말이 놓이지 않았을 때 이동하는 칸이다. r = 1: r = 0에서 10에 말이 놓였을 때 이동하는 칸이다. r = 2: r = 0에서 20에 말이 놓였을 때 이동하는 칸이다. r = 3: r = 0에서 30에 말이 놓였을 때 이동하는 칸이다. r = 4: r = 0, 1, 2, 3, 5에서 40에 말이 놓였을 때 이동하는 칸이다. r = 5: r = 1, 2, 3에서 25, 30, 35에 말이 놓였을 때 이동하는 칸이다. 말이 이동한 좌표에 따라 게임판의 인덱스를 조정하고 dfs 탐색한다. 풀이 from sys import stdin def dfs(i, record.. 2024. 1. 21.
[Baekjoon-Python] 1446 : 지름길 https://www.acmicpc.net/problem/1446 접근 도로 길이를 순회하면서 현재 운전거리의 최솟값을 메모이제이션한다. 지름길을 지나지 않는 것이 거리가 더 짧을 수 있다. 현재 위치가 지름길 도착 위치와 같다면 지름길을 지나서 온 거리와 현재 값 중 작은 것을 선택한다. 풀이 from sys import stdin n, d = map(int, stdin.readline().split()) short_road = [tuple(map(int, stdin.readline().split())) for _ in range(n)] dp = [1e9] * (d + 1) dp[0] = 0 for i in range(1, d + 1): dp[i] = dp[i - 1] + 1 for start, end.. 2024. 1. 21.
[Baekjoon-Python] 21608 : 상어 초등학교 https://www.acmicpc.net/problem/21608 접근 입력받은 학생 번호 순서로 자리를 지정한다. 교실을 순회하면서 상하좌우를 확인한다. 상하좌우에 좋아하는 학생이 가장 많은 자리를 찾는다. 좋아하는 학생이 가장 많은 자리가 여러 개이면 상하좌우에 빈 칸이 많은 자리를 찾는다. 행, 열을 오름차순으로 순회하기 때문에 빈 칸이 많은 자리가 여러 개여도 가장 먼저 찾은 자리가 행, 열 번호가 가장 작다. 풀이 from sys import stdin def sit(my_favorite): now_r = now_c = -1 max_my_favorite_cnt = max_blank_cnt = 0 for r in range(n): for c in range(n): if classroom[r][c.. 2024. 1. 21.
[Baekjoon-Python] 1918 : 후위 표기식 https://www.acmicpc.net/problem/1918 접근 여는 괄호와 연산자는 스택에 삽입한다. 여는 괄호는 닫는 괄호를 만났을 때 스택에서 삭제한다. 연산자는 다음 연산자보다 우선순위가 높을 때 스택에서 삭제한다. 풀이 from sys import stdin infix = stdin.readline().rstrip() priority = {"*": 2, "/": 2, "+": 1, "-": 1} stack = [] res = [] for token in infix: if 65 = priority[token]: res.append(stack.pop()) stack.append(token) while stack: res.append(stack.pop()) # (6) print("".join(.. 2024. 1. 21.
[Baekjoon-Python] 14719 : 빗물 https://www.acmicpc.net/problem/14719 접근 블록을 순회하면서 현재 블록 기준 왼쪽에서 가장 높은 높이, 오른쪽에서 가장 높은 높이를 구한다. 두 높이 중 최솟값까지 물이 고일 수 있다. 풀이 from sys import stdin h, w = map(int, stdin.readline().split()) blocks = list(map(int, stdin.readline().split())) res = 0 for i in range(1, w - 1): # (1) left = max(blocks[:i]) # (2) right = max(blocks[i + 1 :]) # (3) min_height = min(left, right) # (4) if min_height > bloc.. 2024. 1. 21.
[Baekjoon-Python] 1107 : 리모컨 https://www.acmicpc.net/problem/1107 접근 최대로 버튼을 누른 횟수는 + 또는 - 버튼만 사용한 횟수이다. 숫자 버튼을 눌러 어떤 채널로 이동한 후 + 또는 - 버튼으로 이동하려는 채널에 도달할 수 있다. 채널은 무한대이기 때문에 탈출 조건이 없으면 무한 루프에 빠진다. 풀이 from sys import stdin def check_button(limit, next): move_cnt = res channel = 100 while channel != limit: for num in str(channel): if num in broken: # (1) break else: move_cnt = min(move_cnt, len(str(channel)) + abs(channel - n.. 2024. 1. 21.
[Baekjoon-Python] 21610 : 마법사 상어와 비바라기 https://www.acmicpc.net/problem/21610 접근 격자의 끝이 연결되어 있기 때문에 구름이 이동할 때 n으로 나눈 나머지만큼 이동한다. 이동한 구름 좌표를 저장해서 물복사버그를 사용할 때 좌표의 대각선을 순회하고, 새로운 구름을 생성할 때 좌표가 포함되었는지 확인한다. 풀이 from sys import stdin from collections import deque def move_cloud(move_r, move_c) -> set: moved_cloud = set() while cloud: r, c = cloud.popleft() r, c = (r + move_r) % n, (c + move_c) % n # (1) board[r][c] += 1 moved_cloud.add((r,.. 2024. 1. 21.
[Baekjoon-Python] 1916 : 최소비용 구하기 https://www.acmicpc.net/problem/1916 접근 다익스트라 알고리즘을 사용하여 출발 도시에서 도착 도시까지 가는데 발생하는 최소 비용을 구한다. 풀이 from sys import stdin from heapq import heappop, heappush def dijkstra(start): q = [] heappush(q, (0, start)) while q: dist, now = heappop(q) if now == end: # (1) break for next, next_dist in city[now].items(): next_dist += dist if next_dist < distance[next]: distance[next] = next_dist heappush(q, (n.. 2024. 1. 21.
[Baekjoon-Python] 20055 : 컨베이어 벨트 위의 로봇 https://www.acmicpc.net/problem/20055 접근 벨트는 2N 길이의 큐, 로봇은 N길이의 큐로 사용한다. 풀이 from sys import stdin from collections import deque def put_robot(idx): global durability robot[idx] = True belt[idx] -= 1 if belt[idx] == 0: durability += 1 n, k = map(int, stdin.readline().split()) belt = deque(map(int, stdin.readline().split())) robot = deque([False] * n) step, durability = 0, 0 while durability < k: .. 2024. 1. 21.

티스토리툴바