기록

문제 보기 로봇 청소기문제는 시뮬레이션 문제이다. 기존의 bfs 구현에서 아래 2가지를 추가해주면 된다. 1. 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행하기 때문에 현재 방향을 왼쪽방향으로 바꿔주는 함수 2. 현재 방향을 기준으로 후진을 하기 위해서 역방향으로 바꿔주는 함수 위 2가지를 추가해주고 기존의 bfs와 유사하게 코드를 구현하니 통과하였다. 코드 # boj 14503 # blog : jjangsungwon.tistory.com import sys from collections import deque # 북 동 남 서 dy = [-1, 0, 1, 0] dx = [0, 1, 0, -1] # 방향 전환 def change(d): if d == 0: # 북 -> 서 return 3 elif..

문제 보기 이 문제는 bfs 문제이다. 수빈이가 3가지 연산을 통해서 동생에게 최대한 빠르게 갈 수 있는 시간을 출력하는 문제이다. 최단 시간과 관련된 문제는 대부분 bfs와 관련이 있는 것 같다. 알고리즘 순서는 다음과 같다. 1. 수빈이의 현재 위치를 큐에 담는다. 2. 현재 위치에서 갈 수 있는 위치를 큐에 담는다(현재 위치 + 1, -1, * 2) 3. 2번 과정을 동생의 위치가 나올 때까지 반복적으로 한다. 위 알고리즘으로 구현을 하여도 시간 초과 혹은 메모리 초과가 발생할 수도 있다. 방문 여부를 확인하는 visited를 list형으로 했을 때 시간 초과가 발생했으며, 큐에 담는 위치를 제한하지 않으면 메모리 초과가 발생하였다. 따라서 방문 여부는 set으로, 큐에 담는 위치는 0 이상 10만..

문제 보기 이 문제는 TSP(Traveling Salesman problem) 문제이다. 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 한 붓 그리기로 유명한 해밀턴 경로와 유사하며, 다시 출발점으로 돌아오는 코드만 추가하면 된다. 풀이 과정은 아래 순서를 따르며 dfs를 통해서 구현하였다. 1. 각 번호에서 출발하여 제자리로 돌아오는 값을 구한다. 2. 1번 과정을 반복하면서 최솟값을 업데이트한다. 코드 import sys def dfs(start, next, value, visited): global min_value if len(visited) == N: if tr..

문제 보기 이 문제는 시간 초과를 해결하는 것이 핵심이다. 시간 초과를 해결하기 위해서 아래 2가지를 고려하였다. 1. 어떠한 자료구조를 사용할 것인지? - AC 문제에서는 양쪽에서 출력이 가능해야 하기 때문에 덱을 사용하였다. 덱은 양쪽에서 모두 입력과 출력이 가능한 자료구조이며 파이썬에는 이미 deque로 정의되어 있기 때문에 그대로 사용하면 된다. 2. 주어진 연산을 어떤 과정으로 수행할 것인지? - 주어진 연산이 RR이라고 가정해보자. RR의 수행 결과는 결국 원래 값이 된다. 이 경우에는 연산을 하지 않는 것이 좋다. 따라서 주어진 연산을 순차적으로 실행하는 것이 아니라, 뒤의 상황을 고려하면서 구현하였다. - 뒤집기(R)의 개수를 파악하고 D 연산을 수행한 후 마지막에 추가적으로 R 연산을 수..