차곡차곡

완전 탐색 (Brute Force) 가능한 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과를 가져오는 알고리즘 이다. 해가 존재한다는 가정을 세우고 완전 탐색하기 때문에 무조건 정답을 찾을 수 있다. 복잡한 알고리즘을 생각하지 않고 모든 경우를 단순히 살펴본다고 볼 수 있다. 완전 탐색 알고리즘을 풀 때는 탐색해야할 전체 데이터 개수가 100만개 이하일 때 완전 탐색을 사용해야한다. 완전 탐색 종류 1. 선형 구조를 전체 탐색하는 순차 탐색 2. 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 사용 조건 1. 문제에 대한 해결책이 잘 정의 되어 있어야 한다. - 해결책이 정의되어 있어야 브루트 포스를 사용한 해결책이 올바른 방법인지 확인할 수 있다. 2. 문제를 해..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 정답 code # 이진 검색 트리 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) tree = [] while True: try: num = int(input()) tree.append(num) except: break def postorder(start,end): if start > end: return mid ..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 정답 code #트리의 순회 import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) n = int(input()) inorder = list(map(int,input().split())) postorder = list(map(int,input().split())) #후위순회에서 최상위노드를 찾은후 중위순회에서 찾기위해 인덱스번호 부여 nodenum = [0] ..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 정답 code #트리 순회 import sys input = sys.stdin.readline #전위 순회 def preorder(root): if root != '.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) #중위 순회 def inorder(root): if root != '.': inorder(tre..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 정답 code #색종이 만들기 import sys input = sys.stdin.readline n = int(input()) paper = [list(map(int,input().split())) for _ in range(n)] result = [] def solution (x,y,n): color = paper[x][y] for i in range(x,x+n): ..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 정답 code #쿼드 트리 n = int(input()) tree = [list(map(int,input())) for _ in range(n)] def quadtree(x,y,n): if n == 1: return str(tree[x][y]) #x: 세로 y: 가로 result = [] for i in range(x, x+n): for j in range(y, y+n): if (tr..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 정답 code #종이의 개수 n = int(input()) paper = [list(map(int,input().split())) for _ in range(n)] minues = 0 zero = 0 one = 0 def dfs(x,y,n): global minues, zero, one check = paper[x][y] for i in range(x,x+n): for j in rang..