기록

문제 보기 bfs와 조합을 응용하여 구현하였다. 지도에서 3개의 벽을 세웠을 때 안전 영역의 최대 크기를 출력하는 문제이다. 조합을 통해서 벽을 세울 위치를 구하였으며, 벽을 세운 후 bfs를 통해서 바이러스를 퍼트렸다. 알고리즘 순서는 다음과 같다. 1. 벽을 세울 수 있는 후보를 찾는다. (배열에서 0 값을 찾는다) 2. 후보 중에서 3개를 고른다. (combinations 내장 함수 이용) 3. bfs 4. 안전 영역의 최대 크기를 업데이트하고 2번으로 돌아간다. (후보 중에서 3개를 고르는 모든 경우를 수행하고 알고리즘은 종료된다) 코드 # boj 14502 # blog : jjangsungwon.tistory.com import sys, copy import itertools from colle..

문제 보기 이 문제는 트리 문제이다. 트리를 구성하기 위해서 class를 사용하였다. 전위 순회, 중위 순회, 후위 순회 함수는 전체적인 구성은 똑같고 출력 위치만 바꿔주면 된다. 전위 순회의 알고리즘 순서는 아래와 같다. 1. 현재 노드 값을 출력한다. 2. 현재 노드의 왼쪽 자식의 값이 .이 아니라면 왼쪽 자식으로 이동하고 다시 1번을 진행한다. 3. 현재 노드의 오른쪽 자식의 값이 .이 아니라면 오른쪽 자식으로 이동하고 다시 1번을 진행한다. 코드 class Node: def __init__(self, item, left, right): self.item = item self.left = left self.right = right def preorder(node): # 전위 순회 print(node..

문제 보기 이 문제는 분할 정복 문제이다. A = 10, B = 11, C = 12라고 주어졌을 때 구해야 하는 정답은 10^11 % 12이다. 만약 10 * 10 * 10 * 10 ... * 10 % 12로 문제를 풀고자 했으면 시간 초과가 발생할 것이다. 시간 초과를 해결하기 위해서 곱셈의 개수를 줄이는 분할 정복이 필요하며 아래 과정을 중점적으로 구현하면 된다. 1. b의 값이 짝수인지 홀수인지 파악한다. 2. b의 값이 짝수라면 10 ^10 -> (10^5)^2 형태로 바꿔준다. 3. b의 값이 홀수라면 10 ^11 -> (10^5)^2 * 10 형태로 바꿔준다. 코드 def power(a, b): if b == 1: # b의 값이 1이면 a % C를 return한다. return a % C el..

문제 보기 이 문제는 분할 정복, 재귀 호출 문제이다. 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 연산을 수..