Deff_Dev

문제 자연수 A를 B번 곱한 수를 C로 나눈 나머지 값을 구하는 문제이다.풀이최대 연산 횟수는 약 21억이기 때문에, B번을 다 곱하면 시간 초과가 나온다. 그렇기 때문에 분할 정복을 이용해서 풀이해야한다. 예를들어서 입력이 2 8 5 일 때, 2를 8번 곱해서 256이 나오고 5를 나눈 나머지인 1이 출력될 것 이다.2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 256 하지만 이 연산에도 규칙이 있다. (((2^2)^2)^2)처럼 제곱을 이용하면 8번해야하는 연산을 3번으로 줄일 수 있다. 왜 그럴까 ? 위 식을 계산해보면 아래와 같다.2^2 = 44^2 = 1616^2 = 256 이 규칙을 적용해서 문제를 풀어봤다.#include using namespace std;long long a, ..

문제이 문제는 (0,0) 에서 (n -1 , m - 1) 위치로 가야할 때, 단 한 번 벽을 뚫고 갈 수 있다.이때, 최단 거리를 출력하는 문제이다.풀이BFS를 이용하여 해당 문제를 풀이했다. 3차원 배열을 이용하여 [y 축][x 축][벽 파괴 유무]로 맵을 만들었다. 이를 BFS를 이용하여 (n - 1, m - 1)까지의 최단거리를 구했다.#include using namespace std;int arr[1000][1000][2];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int n, m;int BFS(){ queue, int>> q; q.push({{0, 0}, 0}); arr[0][0][0] = arr[0][0][1] = 1; while(!q.em..

문제 w * h 크기의 건물에 불이 났을 때, 상근이가 얼마나 빨리 탈출할 수 있는지 출력하는 문제이다. 입력'.': 빈 공간'#': 벽'@': 상근이의 시작 위치'*': 불풀이입력을 받을 때, 상근이의 시작위치, 불 위치는 각각의 큐에 저장하고, 탈출 지점 좌표를 벡터에 저장한다. 이후, 각각의 큐를 바탕으로 BFS를 진행하고, 각각의 map 정보를 저장한다. 탈출 지점 좌표를 탐색하여, 불 위치를 BFS한 맵, 상근이 위치를 BFS한 맵의 값을 비교하고 상근이 위치를 BFS한 맵의 탈출 지점 값이 더 작다면 최솟값을 비교한다. #include using namespace std;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int n, h, w;vecto..

문제M * N * H로 이루어진 박스에 토마토들이 담겨 있는데, 익은 토마토가 되기 위해서는 안 익은 토마토 근처에 익은 토마토가 있을 때, 하루가 지나면 익은 토마토가 된다. 박스에 모든 토마토가 익은 토마토가 될려면 며칠이 지나야하는지 출력하는 문제이다. 입력 조건은 -1(토마토가 없는 박스), 0(안익은 토마토), 1(익은 토마토)이다.풀이3차원 배열에 박스 정보를 입력받고, 익은 토마토 좌표를 큐에 저장한 뒤, BFS를 이용하여 날짜를 계산했다. 큐가 비었을 때 BFS가 끝나므로 출력할 땐, count - 1를 한다.#include using namespace std;int dx[6] = {0, 0, 1, -1,0,0 };int dz[6] = {1, -1, 0, 0,0,0};int dy[6] = ..

문제 n * n 크기의 R, G, B로이루어진 그림의 구역 수를 구하는 문제이다. 이때, 적록색약 유무에 따른 그림 영역의 갯수를 출력하면 된다. 적록 색약이 있는 사람은 R, G의 구분을 못한다.ex) 적록 색약 X ▶ R (1), G(1), B(1) = 3개,  적록 색약 O ▶ RG(1), B(1) = 2개풀이일반적인 그림이 담겨있는 2차원 벡터와 적록색약을 가진 사람이 보는 그림이 담긴 2차원 벡터 2개를 만들고,  이를 BFS를 이용하여 탐색했다. #include using namespace std;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int n ;void BFS(pair startPoint,vector> &arr,bool visited[1..

문제풀이간단한 BFS 문제로, BFS이용하여 그림 영역과 넓이를 구한 뒤, 출력했다.#include using namespace std;int n, m, pictureCount = 0 ,maxWidth = 0;int arr[500][500] = {0 ,};int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};bool visited[500][500] = {false, };void BFS(pair startPoint){ queue> q; q.push(startPoint); visited[startPoint.first][startPoint.second] = true; int count = 1; while (!q.empty()) { pair point = q.front(..

문제 이 문제는 아래의 규칙에 따라 ( , ) , [ , ] 로 이루어진 입력의 결과 값을 출력하는 문제이다. 규칙'()’ 인 괄호열의 값은 2이다.‘[]’ 인 괄호열의 값은 3이다.‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.이때, 올바르지 않은 괄호열일 경우 반드시 0을 출력한다.풀이이 문제를 실제 수식 연산처럼 풀이하기엔 괄호가 겹쳐있거나 했을 때, 변수가 많아 어려웠다.ex) "(()[[]])([])" ▶ 2 * (2 + 3 * 3) + 2 * 3 = 28 그래서 실제 연산이 아닌 분배 법칙을 이용하여 이 문제를 풀이했다. 위 식을 분배 법칙으로 바꿔본..

문제풀이이 문제는 쇠막대기를 레이저로 자를 떄, 몇 개의 막대기가 나오는지 출력하는 문제이다. 입력은   ' ( ' , ' ) ' 두 가지이다.' ( ' 뒤에 바로 ' ) '가 온다면 해당 자리에 레이저를 쏜다는 것이고, 이외의 입력은 막대기를 의미한다. ex) "(())" 입력은 ㅡ ㅡ 처럼 막대기 2개가 나온다.예제의 입력을 본다면 위 그림과 같이 17개의 막대기가 나온다.  해결 방법스택을 이용하여 풀이했고 입력을 받은 뒤, 입력된 문자열을 탐색하면서 레이저를 감별하고 막대기를 자른다.' ( ' 이라면 bar 갯수를 + 1 한 뒤, 스택에 푸시한다. (flag 변수 true)' ) '이라면 막대기 끝 or 레이저이기 때문에 bar 갯수를 - 1 한다.flag 변수가 true일 때는 레이저이기 때문에..