인문학적 공학도

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. 각 톱니바퀴와 맞물린 톱니바퀴..

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팀에 동시에 완전탐색을 통한 팀구성을 해야하나 싶었지만 두 팀은 배타적이기 때문에 한 팀의 정보만 저장해주면 다른 팀의 구성원도..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 구조는 간단하지만 상당히 까다로웠던 문제. 문제는 크게 두 부분으로 나뉜다. 1. 연구소의 벽 세우기 2. 바이러스 퍼뜨리기 처음에 문제를 접했을 때 완전탐색(브루트포스)를 숙지하지 않았기 때문에 벽을 어떻..

https://www.acmicpc.net/problem/14890 반복문의 iterator 조작이 까다로운 문제. 평지는 생략하고 높이가 바뀌는 블록을 기준으로 오르막길과 내리막길 각각의 조건이 맞는지 잘 따져야 한다. #include #include #include using namespace std; int map[101][101]; bool visited[101]; int N, L, path; void checkRow(int x) { int cur = map[x][0]; //visited[0] = true; int depth = -1; for (int i = 0; i < N; i++) { if (cur != map[x][i]) { //visited[i] = true; if (abs(cur - ma..