Coding_Test_C++
BaekJoon 11048번: 이동하기(C++)
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이법 1) n과m의 크기가 1000이 될 수 있기에, dfs나 bfs를 이용하면 시간 초과가 발생할 수 있어 DP로 문제를 해결했다. 2) 기존에 입력받은 배열을 제외하고 ans 배열을 만들어서, 현재 index에서의 최대 값을 찾는 저장하는 배열을 만들었다. 시작 index가 1,1 이고, 0행과 1열은 선언시 부터 0으로 초기화 되어있기에, 점화식을 다음과 같이 세웠다. 3) ..
BaekJoon 5430번: AC(C++)
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이법 1) Deque를 이용하여 문제를 해결하였다. 2) 구현 또한 포함되어 있는 부분이기에, 문제의 예제에서 \n와 break가 어디에 들어갈 수 있는지가 중요할 것이다. #include #include #include #include #include #include #include #include #define INF 987654321 using namespace std; int t; int main() { cin.tie(0); ios::sync_..
BaekJoon 6118번: 숨바꼭질
https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 > n >> m; for (int p = 0; p > a >> b; arr[a].push_back(b); arr[b].push_back(a); } bfs(1); sort(vec.begin(), vec.end(), compare); cout
BaekJoon 1303번: 전쟁 - 전투(C++)
https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이법 1) BFS를 활용하여, 칸의 개수를 구하고 이를 합으로 만들어보았다. 2) 구현이 어려운 부분이 아니나, n과 m의 순서를 입력 받는 것에 있어 문제에서 명시한 세로와 가로가 헷갈려서 헤맨 문제이다. 3) 기초 bfs/dfs 개념을 익히기에 가장 좋은 문제라고 생각한다. #include #include #include #include #include #includ..
BaekJoon 2467번: 용액(C++)
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이법 1) 투포인터를 활용하여 문제를 해결하면 시간 내에 문제를 해결할 수 있다. 2) sort를 활용하여 입력받은 배열을 정렬하고, 처음 index와 마지막 index를 합하였을 때 값이 음수이면 left 값을 1 증가 시키고, 양수이면 right 값을 1 감소시켰다. #include #include #include #include #include #include #include #def..
BaekJoon 17070번: 파이프 옮기기 1(C++)
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) BFS를 활용하되 visited배열을 사용하지 않고 문제를 풀었다. 2) 벽지가 긁히면 안되는 것을 꼭 유의하여 특히 대각선으로 움직일때 이동 가능한 모든 경우의 수에서 1이 없는지를 check 후 queue에 넣는 방식을 사용하였다. 이동 가능한 모든 경우의 수는 다음과 같다. int ..
BaekJoon 15686번: 치킨 배달(C++)
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) dfs를 활용하면 풀 수 있는 문제이다. (일종의 백트래킹) 2) bfs를 활용하여 접근 시에 시간 초과가 발생할 수 있다. |x1-x2|+|y1-y2|가 거리가 되므로 거리를 계산 시에 위 식을 활용하였다. 3) 1이 들어가 있는 x의 좌표와 y의 좌표를 ones 배열에 담아 주었으며, 2..
BaekJoon 14502번: 연구소
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이법 1) 바이러스가 퍼지는 것을 방지하기 위해 벽을 정확히 3개 세울 수 있다는 것에 유의하며 문제를 풀어야 한다. 2) 8x8 배열이므로 완전 탐색을 진행하였으며 벽을 세우는 것은 dfs 알고리즘을 활용하였다. 3) 벽이 3개 세워진 이후에는 bfs 알고리즘을 활용하여 안전 지대의 크기를 확인하여 문제를 해결하였다. (기존의 입력 값의 배열을 그대로 사용 시에 문제를 해결할 수 없다. 꼭 같은 크기의 배..
BaekJoon 14938번: 서강그라운드(C++)
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이법 1) 다익스트라를 반복하여 문제를 해결하면 쉽게 풀 수 있는 문제이다. 2) ans라는 배열에 각 start Node로 부터의 거리를 담아 최대 값을 찾으면 해결이 가능하다. #include #include #include #include #include #define INF 987654321 using namespace std; int n, m, r; int arr[101][101]; int ..
BaekJoon 2638번: 치즈(C++)
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이법 1) while 반복을 통해, 빈 배열이 나올때 까지 반복하여 총 걸리는 시간을 확인한다. 2) 치즈의 상태가 담길 배열을 arr, arr2로 두개 선언하였다. 시간이 종료된 후에 한번에 바꾸는 것이 결과값에 영향을 끼치지 않기에 두 개를 선언하여 문제를 해결하였다. 3) visited는 현재 치즈가 있는 배열을 의미하며, visited2는 현재 외부공기를 의미한다. 4) (0..