봄봄.devlog

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 1. 문제 설명 폴리오미노는 크기가 1 X 1인 정사각형을 여러 개 이어 붙여서 만든 도형이다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 총 5가지가 있다. N X M 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제 4 즉, 파란색 테트로미노는 N X ( M-3 ) 정도를 놓을 수 있다. * 5 X 6 종이 위에 주황색 테트로미노를..

01. 개념 브루트 포스는 모든 경우의 수를 다 해보는 것이다. 이 때, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다. 예를 들어, 비밀번호가 4자리이고, 숫자로만 이루어져 있다고 한다면 0000부터 9999까지 다 입력해보면 된다. 경우의 수가 10,000가지 이다. 사람이 직접 비밀번호를 입력하는데 1초가 걸린다면 10,000초 = 2.7시간 정도 걸린다. 02. 브루트 포스 3단계 풀이법 1. 문제의 가능한 경우의 수를 계산한다. - 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다. 2. 가능한 모든 방법을 다 만들어본다. - 하나도 빠짐 없이 만들어야 한다. - 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀호출 사용, 비트마스크 사..

01. 순열의 개념 1~N 까지로 이루어진 수열 1 2 3 4 1 3 2 5 4 2 3 1 6 5 1 2 3 4 크기는 항상 N이 되어야 하고, 겹치는 숫자가 존재하지 않음 * 순열을 이용해서 문제를 푼다 => 순서가 매우 중요한 경우 ex) N개 (사과, 바나나, 배, 딸기) 먹는 순서가 바뀌면 값이 달라짐. 따라서 순서가 매우 중요함. 1부터 N까지의 값이 한번씩 나오면서 순서가 다르게! 크기가 N인 순열은 총 N!개가 존재한다 => N / N-1 / N-2 / N-3... / 2 / 1가지 순열을 사전순으로 나열했을 때 (두 문자열을 비교 ex. abc < abd) N=3인 경우에 사전순은 다음과 같다 1 2 3 (첫 순열 : 오름차순) 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 (마지막..