코딩 테스트/백준 강의 문제편

17069. 파이프 옮기기 2

17069번: 파이프 옮기기 2 (acmicpc.net) 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 유형 : 브루트 포스, DP # 가능한 방법의 수가 제한이 없다. # 따라서, 32x32 모양의 격자이므로 칸의 최대 개수는 1024에, # (0,0),(0,1)칸을 제외하고 각 칸에 (x,y)가 오는 경우/아닌 경우 2가지를 곱하여 구해지는 # 모든 경우의 수는 대략 2^1022 일 것 같다. # 따라서, 브루트 포스가 아닌 dp를 사용한 백트랙킹을 적용하여 탐색 경우의 수 ..

브루트포스) 16637.괄호 추가하기

16637번: 괄호 추가하기 (acmicpc.net) 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net # solution. # 비트마스크, 브루트포스 문제 # 연산자의 개수 m=(n-1)/2 이고, n은 19 이하이므로, m의 최댓값은 9다. # 시간복잡도 : 각 연산자가 괄호에 포함되는지 아닌지로 구분되기에, 모든 경우의 수는 최대 2^9=512 이다. # 각 자리의 연산자가 포함되면 1로, 포함되지 않으면 0으로 생각하여, 비트마스크로 구분한다. # 각 괄호는 연산자를 하나만 포함할 수 있으..

브루트포스) 17406.배열 돌리기 4

17406번: 배열 돌리기 4 (acmicpc.net) 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net from itertools import permutations from collections import deque from copy import deepcopy n,m,k= map(int,input().split()) a=list(list(map(int,input().split())) for _ in range(n)) ops=list(list(map(int,input().spl..

브루트 포스) 20058.마법사 상어와 파이어스톰

20058번: 마법사 상어와 파이어스톰 (acmicpc.net) 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net from collections import deque input_n,q = map(int,input().split()) n=2**input_n a=[list(map(int,input().split())) for _ in range(n)] ls=list(map(int,input().split())) dx=[-1,0,1,0] dy=[0,-1,0,1] # 매트릭스 시계방향 90도 회전 ..