본문 바로가기

👨‍💻📱✍️🎢314

BOJ 15723 - n단 논법 문제 백준 온라인 저지 - 15723번 풀이 과정 n단 논법 을 만족하는지 판단하는 문제입니다. 우선 주어진 논제를 바탕으로 방향 그래프를 생성합니다. 이후 특정 논법이 모순이 없는지 판단하기 위해서는 a is d 일 때 a 에서 d 에 도달 가능한지 판단하면 됩니다. 따라서 생성한 그래프에 플로이드 와샬 알고리즘을 이용해서 모든 정점에 대해 도달 가능성을 판단하면 됩니다. 코드 import sys N = int(input()) graph = [[0] * 26 for _ in range(26)] for _ in range(N): frm, to = list(sys.stdin.readline().strip().split(' is ')) graph[ord(frm) - ord('a'.. 2021. 3. 18.
BOJ 14496 - 그대, 그머가 되어 문제 백준 온라인 저지 - 14496번 풀이 과정 시작 지점에서 목표 지점에 도달하기 위한 최단 경로를 구하는 문제입니다. 다익스트라 알고리즘 을 활용해서 시작 지점에서 모든 지점까지의 거리를 구할 수 있습니다. 코드 import sys import heapq INF = 2e9 def make_graph(): graph = [[] for _ in range(n + 1)] for frm, to in edges: graph[frm].append(to) graph[to].append(frm) return graph def dijkstra(graph): dist = [INF] * (n + 1) pq = [] heapq.heappush(pq, [0, a]) dist[a] = 0 while pq: cost, her.. 2021. 3. 16.
BOJ 9311 - Robot in a Maze 문제 백준 온라인 저지 - 9311번 풀이 과정 시작 지점에서 목표 지점에 도달하기 위한 최단 이동 횟수를 구하는 전형적인 BFS 문제입니다. 보드를 입력받은 다음 시작 지점을 먼저 찾은 다음, BFS 를 통해서 목표 지점 G 를 찾을 때까지 순회합니다. 코드 import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def pre_processing(board, R, C): for x in range(R): for y in range(C): if board[x][y] == 'S': return [x, y] def bfs(start, board, R, C): q = deque() visit = [[0] * C.. 2021. 3. 14.
BOJ 20005 - 보스몬스터 전리품 문제 백준 온라인 저지 - 20005번 풀이 과정 해당 문제는 pypy3로 풀이했습니다. 몬스터와 플레이어의 위치가 주어질 때 몬스터를 처치해서 보상을 얻을 수 있는 플레이어의 수를 구하는 문제입니다. 플레이어는 몬스터에게 최단 거리로 이동하기 때문에 BFS 를 이용해서 몬스터 까지의 최단 경로룰 구하면 됩니다. 이때 상태공간 S 는 다음과 같이 정의할 수 있습니다. S[x][y][player] = (x, y) 지점에 player 가 이미 방문한 적이 있는지 유무 한 가지 실수를 했던 점은 `BFS` 가 종료되기 위한 조건으로 `queue` 가 비어있는지를 체크한 것인데, 사실 더 이상 이동할 곳이 없더라도 몬스터의 체력이 0 이하가 될 때까지 게임을 진행해야해서 계속 틀렸었습니다. 따라서 이 부분만 유.. 2021. 3. 14.
BOJ 17521 - Byte Coin 문제 백준 온라인 저지 - 17521번 풀이 과정 바이트 코인 의 시세가 주어질 때 매수 및 매도를 통해 얻을 수 있는 최대 이익을 계산하는 문제입니다. 매수 및 매도 횟수에 제한이 없기 때문에 그래프의 극대 및 극소 지점에서 매도 및 매수를 진행하는 그리디 해법이 적용됩니다. 각각의 순회에서 이전 가격과 비교하여 그래프의 상승 및 하강을 파악할 수 있으며 마지막에 매도하지 않고 남은 코인이 존재할 경우 이전에 극소 지점에서 코인을 구매하고 아직 판매하지 못한 것이기 때문에 극대 지점을 갱신 중인 상황이라는 것을 의미하고 따라서 마지막 날의 시세에 팔면 최대 이익을 취할 수 있습니다. 코드 import sys N, W = list(map(int, sys.stdin.readline().split())) c.. 2021. 3. 14.
BOJ 20363 - 당근 키우기 문제 백준 온라인 저지 - 20363번 풀이 과정 물과 햇빛을 주는 규칙이 주어질 때 목표 수치로 도달하기 위한 최소 횟수를 구하는 문제입니다. 예시로 햇빛과 물의 목표치가 123456, 12345 일 경우를 생각해보겠습니다. 10 으로 나눈 몫 만큼 반대편 수치가 줄어들기 때문에 첫번째 시도에는 두 수치중 큰 수치를 먼저 만족시키는게 유리합니다. 그런데 이때 123456 을 딱 맞춘 다음 12345 를 만족시키는 경우와 123456 보다 더 많은 수치를 부여한 뒤 12345 를 만족시키는 이 두 가지 경우에서 어떤 것이 더 적은 횟수의 양분 공급을 필요로 할까요? 10 으로 나눈 몫 만큼 반대편 수치가 줄어들기 때문에 첫번째 경우 1234, 123, 12, 1 순서대로 양분 공급이 필요합니다. 즉 첫번.. 2021. 3. 14.

티스토리툴바