기록

문제 보기 이 문제는 분할 정복, 재귀 호출 문제이다. Z 형태로 배열을 탐색하기 위해서는 크기가 2 * 2가 될 때까지 4등분을 반복해야 하며 알고리즘 순서는 아래와 같다. 1. 주어진 배열을 4등분 한다. (분할 정복) 2. 1의 과정을 반복적으로 진행하면서 단위가 2*2일 때 탐색을 시작한다. (재귀 호출) 3. r, c를 탐색하면 출력하고 종료한다. 코드 (시간 초과) def divide(size, start_row, start_col): global cnt if size == 2: if start_row == r and start_col == c: # 왼쪽 위 print(cnt) return cnt += 1 if start_row == r and start_col + 1 == c: # 오른쪽 위..

문제 보기 이 문제는 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 연산을 수..