겜돌이의 개발일지

문제 백준 14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 8x8의 작은 배열이기 때문에 가능한 모든 경우의 수에 대해 벽을 만들어 주는 브루트포스 방법을 사용합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..

문제 백준 2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 일반적인 dfs, bfs 문제입니다. 저는 bfs로 풀었습니다. 입력을 받고, 사각형이 있는 위치를 1, 없는 위치를 0으로 초기화해줍니다. bfs를 실행하면서 개수와 영역의 넓이를 구합니다. 영역은 vector에 push 해준 뒤, 오름차순으로 정렬하여 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

문제 백준 1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 입력이 빈칸으로 구분되지 않기 때문에 string 형식으로 받은 뒤 int 형식으로 map에 저장시켜 줍니다. 루프를 돌면서 색깔이 같지 않다면 4분할해주고, 같다면 그 색깔을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4..

문제 백준 1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 입력을 받은 후, 문자열을 알파벳 오름차순으로 정렬합니다. 그 이후에 루프를 돌면서 password의 크기가 length가 되면 검사를 합니다. 검사 후 조건(모음 1개 이상, 자음 2개 이상)을 만족하면 출력하고, 만족하지 못 하면 출력하지 않습니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37..

문제 백준 2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 dp 배열은 (인덱스, 몇번 연속으로 마셨는지) 중에서 최댓값을 나타냅니다. 예제로 보겠습니다. 6 10 13 9 8 1 0 0 6 16 23 28 33 1 6 10 19 25 31 29 2 0 16 23 28 33 32 먼저 1번째, 6일 때 안 마시는 경우(dp[0][0])를 0, 2번 연속 마시는 경우는 없으니 0으로 초기화 해줍니다. 1번 연속 마시는 경우에는 arr[0]값인 6을 넣어줍니다. 2번째에서 안 마시는 경우는 dp[i-..

문제 백준 9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 점화식만 알면 쉽게 풀 수 있는 문제입니다. 점화식은 직관...으로 찾았습니다. 인덱스가 커지면 배열의 값이 int 범위를 초과하므로 배열을 long long 형으로 선언합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; long long dp[101]; int main() { int t; int n..

문제 백준 2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 정해진 크기 만큼의 배열을 돈 뒤, 색깔이 모두 같으면 해당 색깔 개수를 늘려주고 색깔이 다르면 재귀를 통해 분할정복합니다. fun함수는 시작지점 sx, sy와 크기 size를 받습니다. map[sy][sx]에 따라 색깔을 나눈 뒤, 배열을 size만큼 점검합니다. 해당 배열의 색깔이 모두 같으면 해당색깔++을 해줍니다. 다르면 4개 영역으로 분할합니다. 각각 좌상 / 우상 / 좌하 / 우하 입니다. 소스 코드..

문제 백준 2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 일반적인 dfs 문제입니다. 1번 노드부터 dfs를 돌며 cnt를 증가시켜줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include using namespace std; bool graph[101][101]; bool visited[101]; int n, m; int cnt;..

문제 백준 9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 점화식을 이용합니다. i 번째에서 더해줄 수 있는 방법의 가지수는 3가지입니다. 1더하기, 2더하기, 3더하기 i 번째 오는 방법을 i+1, i+2, i+3에 각각 더해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int dp[14]; int main() { int t; cin >> t; dp[0] = 1; for (int i = 0; i n; cout

문제 백준 22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 풀이 전형적인 bfs, dfs 문제입니다. 투약 전과 투약 후의 상태를 입력받습니다. 루프를 돌면서, 전과 후의 상태가 다르면 그 지점부터 bfs를 해줍니다. bfs 이후에도 전과 후가 다르다면, 백신이 아니므로 NO를 출력합니다. 같다면 YES를 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..