귀염둥이의 메모

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 BFS를 이용해서 구현했다. 백트래킹을 이용해서 벽 3개를 세우는 모든 경우의 수를 구하였다. 벽 3개가 세워지면 1) BFS를 이용해서 바이러스를 전파시킨다. 2) 바이러스 전파가 끝난 후 안전영역을 구한다. 3) 안전영역의 최대 크기를 갱신한다. 소스코드 #include using namespace std; int n, m, result; int g[8][8]; int vis[8][8]; int bfs() {..

programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 1번, 2번, 3번 찍는 방식 a, b, c를 각각 선언했다. check 배열의 인덱스 0은 쓰지 않고, 1, 2, 3은 1번, 2번, 3번이 맞은 문제의 개수이다. answers의 길이만큼 반복문을 진행하며 a, b, c와 비교하며 맞으면 check를 1증가 시킨다. 마지막에 최댓값을 answer에 저장한다. 소스코드 #include #include using namespa..

www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 주사위를 배열 v와 h를 통해서 표현했다. 명령에 따라서 v와 h를 규칙에 맞게 적절히 업데이트하며 조건에 맞게 코드를 작성했다. 소스코드 #include using namespace std; int n, m, x, y, k; int g[20][20]; int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1,..

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net BFS로 간단하게 풀 수 있는 문제이다. 비가 내리지 않는 경우를 생각하지 않아서 계속 틀렸었다. 지역의 높이를 받을 때 가장 높은 지역의 높이를 high에 저장한다. 비가 내리지 않는 경우 k = 0 부터 k = high - 1 까지 오는 경우까지 BFS를 돌려서 최대 안전영역 수를 갱신시킨다. 소스코드 #include using namespace std; int n, mx, high, result; int m[10..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제를 읽었을 때 많이 복잡해 보였는데 생각보다 간단하게 풀렸다. 주어진 조건 그대로 작성하였다. 북 : 0, 동 : 1, 남 : 2, 서: 3 rot 배열의 index는 현재 바라 보는 방향이고, 배열 값을 현재 좌표에 각각 더하면 왼쪽 좌표이다. ex) 북쪽(index = 0) 일 때 (x+ rot[0][0], y + rot[0][1])은 지금 북쪽을 바라봤을 때 왼쪽 좌표 (r, c) back 배열의 i..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현이 조금 까다로워서 시간이 조금 걸렸다. 공기 순환 방향인 up, down 배열을 선언했다. up : {오른쪽, 위, 왼쪽, 아래} down : {오른쪽, 아래, 왼쪽, 위} 1. 미세먼지 확산 미세먼지가 있는 좌표와 확산되기 전 먼지 값(origin)을 큐에 넣는다. 확산 가능한 곳이면 origin/5을 더하고, 확산시킨 먼지 값을 origin/5 만큼 빼준다. 2. 공기청정기 작동 청정기 (위, 아래)..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS를 이용해서 해결할 수 있었다. +u와 -d씩 움직이며 탐색을 한다. 탈출 조건은 g(목표점)에 도달했을때 (vis배열 값 - 1) 을 return한다. vis배열은 버튼을 누른횟수가 들어가는데 처음에 0이 아닌 1이 들어가기때문에 (vis배열 값 - 1) 을 return 해준다. 탐색을 완전히 할때까지 g에 도달하지 못하면 "use the stairs"을 출력한다. 소스코드 #include using namespac..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 백트래킹을 활용하여 완전 탐색을 했다. 1. 현재 위치에서 4 방향(위, 아래, 왼, 오)으로 진행하며 사각형이 4개가 될 때마다 합의 최댓값을 갱신해 주었다. 2. 위 과정이 끝나고 k == 1일때 가능한 모든 ㅗ 모양에 대해서 최댓값을 갱신했다. 소스코드 #include using namespace std; int n, m, mx, s; int dx[4] = {0, 0, -1, 1}; int dy[4] = ..

www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net vis 배열에 스타트팀 인원들을 true로 표시하였고, 링크팀 인원들은 false이다. 각각의 모든 경우에 대해서 능력치 차이를 비교하여 차이의 최소를 구하였다. 소스코드 #include using namespace std; int n; int minimum = INT32_MAX; int vis[21]; int stat[21][21]; void dfs(int k, int start) { if (k == n / 2) { int st ..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 이차 원 배열 M에 사과는 1로 표시하고, 뱀의 몸은 -1로 표시를 하였다. int 변수 dx와 dy를 통해서 현재 진행방향을 나타 냈다. 벽 또는 자신의 몸에 부딪힐 때 종료 조건을 걸고 break 했다. 몸이 되는 부분의 차례로 큐에 넣어서 사과를 먹지 않았을 때 꼬리 부분(가장 나중에 큐에 들어간 부분)을 없앴다. 위, 아래, 오른쪽, 왼쪽 진행 방향 각각에 대해서 'L'과 'D'일 때를 처리해 주었다. -> 이..