인문학적 공학도

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 기준블럭 x,y 하나를 잡고 2차원 배열 모든 인덱스를 2중 loop로 순회하면 되는 문제이다. x,y를 기준으로, 상하좌우로 인접한 블럭들을 완전탐색하면 된다. 그런데 이렇게 할 경우 ㅗ 모양의 테..

불러오는 중입니다... 상당히 간단한 풀이의 문제였다. 일단 N과 K를 아무 숫자나 정하고 차근차근 세어보기로 한다. (10,K)로 대충 정해보자 N=10 K=1: 1개 N=10 K=2 : (0,10), (1,9), (2,8) ... (10,0) 11개 N=10 K=3 : (0,0,10), (0,1,9) ... (0,10,0) / (1,0,9), (1,1,8) ... (1,9,0) / ..... / (10,0,0) N=10 K=3에서 붉은 색 부분을 보자. N=10 K=2일 때의 경우의 수 그대로다. 주황 색 부분은? N=9 K=2일 때의 경우의 수이다. 쭉 진행해보면 마지막 파란색 부분은 N=0 K=2일 때의 경우의 수다. 간단하게 점화식을 얻을 수 있다. (N,K)=(N,K-1)+(N-1,K-1)+...

4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 오랜만에 BFS 문제를 풀어봤다. 요즘은 소마 코테를 준비하느라 브루트포스, DP, BFS 위주로 푸는 중이다. 각설하고, 입력된 그래프의 연결요소의 개수를 구하는 문제. 연결 요소란, '무향 그래프에서 ..

11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net DP문제를 연습하고 있다만 설명의 과정이 귀찮아 블로그에 기록하진 않았다. 이번 문제는 설명하기가 간단하고, DP의 핵심적인 부분을 다루고 있다. 블럭이 한 칸(2x1) 증가하는 경우와 두 칸(2x2)씩 증가하는 경우, 2가지를 상정한다. 이 때 두 칸씩 늘어나는 경우는 가로로 누운 블럭 두 개가 붙은 경우와 큰 하나의 블럭, 두 가지 블럭이다. 길이i 타일 = 길이가 i-1인 타일에 한 칸을 붙인 경우(경우의 수는 그대로) + 두 칸씩 늘어나는 경우*2(두 가지 블럭) 점화식으로 표현하면 DP[i] = DP[i-1] + DP[i-2]*2 #inclu..

13908번: 비밀번호 첫 번째 예제의 경우 가능한 비밀번호의 조합은 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97이다. 두 번째 예제의 경우 가능한 비밀번호의 조합은 34, 43이다. www.acmicpc.net 비밀번호의 일부분을 알고 있다는 전제 하에 모든 비밀번호 조합의 개수를 찾는 브루트포스 문제. 모든 비밀번호를 쭉 나열한 다음, 조건을 만족하는 비밀번호가 등장할 때마다 count해주면 된다. #include #include using namespace std; vector vec; int n, m, temp; bool visited[8]; int answer[8]; int result; void print..

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 비교적 풀이과정이 스무스했던 문제. 문제를 풀기 위해 특별히 알아야 할 알고리즘도 없다. 굳이 분류하자면 시뮬레이션..? 이 문제를 크게 두 부분으로 나누자면 1. 미세먼지 퍼뜨리기 2. 공기청..

14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net deque를 이용하면 쉽게 접근할 수 있는 문제 두 가지 사항을 고려했다. 1. 특정 톱니바퀴에 대한 시계방향 회전 function, 반시계방향 회전 function 2. 각 톱니바퀴와 맞물린 톱니바퀴..

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 또또 브루트포스 문제이다. 삼성역량테스트에는 브루트포스문제가 단골로 등장하나보다. 대부분의 브루트포스 문제는 N과M 시리즈를 참조할 수 있으니 브루트포스가 감이 잡히지 않는다면 꼭 다 풀어보자. 숫자와 그 사이에 끼워넣을 연산자가 입력으로 주어지면 연산자 순서를 이리저리 바꾸면서 계산할 수 있는 값의 최대 최소를 구하면 된다. 이번 문제는 크게 두 부분으로 나누자면..

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 전형적인 브루트포스 문제. 이전에 풀었던 N과 M문제를 참조하였다. 1. N명의 선수를 두 팀으로 나누기 : n C n/2 2. 각 팀을 2인1조로 구성하여 총 전력을 구하기 : n/2 C n 크게 두 분으로 나뉘어 있다. 막혔던 부분은 브루트포스 재귀문을 이용해 어떻게 두 팀을 동시에 구성할 것이냐에 관한 것이었다. 재귀를 돌릴 때마다 start팀과 link팀에 동시에 완전탐색을 통한 팀구성을 해야하나 싶었지만 두 팀은 배타적이기 때문에 한 팀의 정보만 저장해주면 다른 팀의 구성원도..

14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 처음봤을 때 조건이 너무 헷깔리는 문제였다. 관련 질문글을 봐도 문제 정정요청이 수두룩한 문제... 구조체에 로봇의 위치와 방향에 관한 정보를 저장하는 것은 필수이다. 본 코드의 핵심은 입력된 좌표..