표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
✅ 문제 풀이
n을 입력 받고 나서 크기가 n+1*n+1인 2차원 벡터를 생성해준다.
그리고 배열의 첫번째 행은 사용하지 않을 것이고, 첫번째 열은 모두 0으로 초기화 해준다.
이 배열은 각 행마다의 누적 합을 갖도록 한다.
배열 값을 입력 받을 때, 해당 행과 열에 해당하는 값은, 배열값+이전열 값을 더하여 누적하도록 한다.
이렇게 누적합을 가진 배열을 가지고, m번의 좌표 입력을 받을 것이다.
좌표의 x1부터 x2까지, y2까지의 누적합에서 y1-1까지의 누적합을 뺀 결과를 누적하여 각각의 answer를 구하고 출력한다.
만약 x1=2, y1=2, x2=3, y2=4이면 누적합 배열의 2행부터 3행까지, 각 항의 4열까지의 누적합-1열까지의 누적합을 하면 2,3,4열을 합한 값이 되는 것이므로 반복적인 덧셈을 피할 수 있다.
이렇게 누적합은 반복적인 연산을 줄여주어서 시간복잡도를 낮추어주는 장점이 있다.
✏ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> sum(n+1, vector<int>(n+1));
for (int i = 1; i < n+1; i++) {
sum[i][0] = 0;
for (int j = 1; j < n+1; j++) {
cin >> sum[i][j];
sum[i][j] += sum[i][j - 1];
}
}
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int answer = 0;
for (int j = x1; j <= x2; j++) {
answer += (sum[j][y2] - sum[j][y1 - 1]);
}
cout << answer<<"\n";
}
return 0;
}
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. [입력] 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
[출력] 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
✅ 문제 풀이
주어진 배열에서 연속적인 1을 하나의 영역으로 보고, 그 영역의 크기와, 총 영역의 개수를 구하는 문제이다.
2중 for문으로 순회하며 각 칸이 1인지 확인한다.
1인 경우에는 count를 0으로 초기화하고, dfs를 호출한다.
dfs에는 현재 칸의 좌표값과, count, 그리고 2차원 배열의 정보를 인자로 넘겨준다.
dfs의 동작은 다음과 같다.
dfs가 호출되면, 현재 칸을 방문했으므로 배열의 값을 0으로 갱신해준다.
그리고 해당 영역에 대한 크기를 구하기 위해서 count를 1 증가 시켜준다.
현재 칸을 기준으로 동서남북 방향에 대해서 총 4번 탐색할 건데, 동서남북이 배열의 인덱스에 유효한지 확인하고, 그 배열 값이 1이라면 dfs를 재귀 호출하여 이어 탐색하도록 한다.
이렇게 되면, 한 영역을 처음 방문하고 나서는 동일한 영역에 대해서는 재귀호출 시 다 처리 되기 때문에, main함수의 2중 for문 순회시에는 딱 각 영역의 시작만으로 구분할 수 있다. 따라서 main의 2중 for문 순회에서 배열 값이 1인 경우에는 dfs를 호출한 뒤, 영역의 개수를 하나 증가시키고, dfs 결과 계산된 해당 영역의 크기인 count를 영역의 크기만 저장하는 배열 cnt에 넣어둔다.
2중 for문을 모두 순회하고 나면 sum에는 영역의 개수가 저장되는 것이고, cnt에는 각 영역의 크기가 저장되어 있을 것이다.
문제에서 출력 시 영역의 크기는 오름차순으로 출력하도록 하라고 되어있으므로, sort함수를 사용하여 cnt 벡터를 오름차순 정렬 시켜주었다.
그리고 sum과 cnt를 모두 출력해준다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void dfs(int x, int y, int &count, vector<vector<int>> &arr) {
arr[x][y] = 0;
count++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n&&ny >= 0 && ny < n&&arr[nx][ny] == 1) {
dfs(nx, ny, count, arr);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
vector<vector<int>> arr(n, vector<int>(n));
for (int i = 0; i < n; i++) {
string str;
cin >> str;
for (int j = 0; j < n; j++) {
arr[i][j] = str[j]-'0';
}
}
vector<int> cnt;
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 1) {
int count = 0;
dfs(i, j, count, arr);
sum++;
cnt.push_back(count);
}
}
}
sort(cnt.begin(), cnt.end());
cout << sum<<"\n";
for (int i = 0; i < cnt.size(); i++) {
cout << cnt[i] << "\n";
}
return 0;
}
✅ 문제 풀이 문제를 풀기 전에 지문을 완벽하게 해석해야 한다. 질문게시판을 보면 알겠지만, 문제 해석에 어려움이 많아보인다.
로봇청소기는 입력으로 주어지는 (r,c)에서 출발하고 방향도 입력으로 주어지는 d를 향하여 시작한다.
이때 d는 북쪽일 경우 0, 동쪽일 경우 1, 남쪽일 경우 2, 서쪽일 경우 3이다. 나는 여기서 동쪽과 서쪽을 반대로 생각하는 실수로 인해 자꾸 틀렸습니다가 떠서 알고리즘의 문제인가 싶었다..
방의 상태는 2차원 arr벡터에, 청소를 한 칸의 횟수는 count에 저장한다.
그리고 다음 과정을 while문을 통해서 반복해주면 된다.
현재 칸이 청소가 안되어 있으면, 즉 0이면 count를 하나 증가시켜주고 현재 칸의 값을 2로 바꾸어준다. 2로 하는 이유는 청소가 안된 0과 벽인 1을 구분하기 위함이다.
그리고 현재 칸에서 동서남북에 있는 칸 중 청소가 안된 칸이 있는지 확인한다. 이때 어디가 청소가 안된 칸인지 정확히 알 필요는 없다. 그냥 청소가 안된 칸이 있다면 bool타입의 clean을 false로 바꾸어주면 된다.
만약(if) 현재 칸에서 동서남북에 있는 칸 중 청소가 안된 칸이 없다면 clean이 true일 것이다. 따라서 clean이 true이면 다음을 따른다. 3-A. 만약(if) 현재 방향에서 한칸 뒤가 벽이 아니라면, 즉 1이 아니라면 후진할 수 있는 것이기 때문에 r과 c를 한칸 후진한 좌표로 갱신해준다. 이 로직을 수행하고 나면 다시 while문의 1번으로 돌아가게 될 것이다. 3-B. 만약 현재 방향에서 한칸 뒤가 벽이라면(else), 즉 1이라면 현재 상태에서 청소를 멈춘다. 따라서 count를 출력하고 return 0;을 함으로써 while문을 끝내고 프로그램을 종료한다.
3과 같지 않다면(else), 즉 주변에 청소할 칸이 하나라도 있으면 clean이 false일 것이다. 따라서 clean이 false이면 다음을 따른다. 4-A. 무조건 현재 방향에서 왼쪽(반시계방향)으로 90도 돌린다. 즉 현재 방향이 북이라면 서로, 서라면 남으로, 남이라면 동으로, 동이라면 북으로 돌아간다. 따라서 숫자로 보면 0>>3>>2>>1>>0...방향이다. 이는 (d+3)을 4로 나눈 나머지와 같아진다. 따라서 d를 (d+3)%4로 갱신해 주면 된다. 4-B. 그리고 갱신된 방향으로 한칸 앞이 청소가 안되어 있으면r과 c를 한칸 앞인 좌표로 갱신해준다. 이 로직을 수행하고 나면 다시 while문의 1번으로 돌아가게 될 것이다.
while문을 끝내고 난 뒤에는 count를 출력하도록 한다.
✏ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
int r, c, d;
cin >> r >> c >> d;
vector<vector<int>> arr(n, vector<int> (m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
int count = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
while (1) {
if (arr[r][c] == 0) {//현재 위치가 벽이 아니고, 청소가 안된 곳이라면
count++;
arr[r][c] = 2;//청소를 완료하면 2로 채운다
}
bool clean = true;
for (int i = 0; i < 4; i++) {
int x = r + dx[i];
int y = c + dy[i];
if (arr[x][y] == 0) {
clean = false;//하나라도 청소안된 곳이있으면 바로 빠져나옴
break;
}
}
if (clean) {//주변에 청소할데가 없으면
int bx, by;
if (d == 0) {//북
bx = r + 1;
by = c;
}
else if (d == 1) {//동
bx = r;
by = c - 1;
}
else if (d == 2) {//남
bx = r - 1;
by = c;
}
else {//서
bx = r;
by = c + 1;
}
if (arr[bx][by] != 1) {//후진할 수 있으면
r = bx;
c = by;
}
else {
cout << count;
return 0;//중단
}
}
//0>>3>>2>>1>>0
else{//청소할데가 있으면
d = (d + 3) % 4;//회전=반시례로 90도는 시계로 270도니까
if (d == 0) {//북
if (arr[r - 1][c] == 0) {
r = r - 1;
}
}
else if (d == 1) {//동
if (arr[r][c + 1] == 0) {
c = c + 1;
}
}
else if (d == 2) {//남
if (arr[r + 1][c] == 0) {
r = r + 1;
}
}
else {//서
if (arr[r][c - 1] == 0) {
c = c - 1;
}
}
}
}
cout << count;
return 0;
}
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다.
[입력] 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
[출력] 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
✅ 문제 풀이
트리를 전위, 중위, 후위 순회하는 방법은 각각의 함수를 재귀호출하는 방법이다.
트리를 int타입의 2차원 배열에 넣을건데, 각 노드는 입력으로 받는 노드 즉 알파벳에서 'A'를 뺀 값을 인덱스로 받을 것이다. 따라서 A부터이므로, 0~25까지 인덱스를 사용하게 될 것이다. 그 인덱스의 첫번째 요소에는 left자식이, 두번째 요소에는 right자식이 들어가는 것이다.
따라서 left에는 두번째로 입력받은 문자가 .이 아닐 경우 문자-'A' 한 값을 넣어주고, right도 세번째로 입력받은 문자에 대해 동일하게 처리한다.
만약 문자가 .이라면 -1을 넣도록 한다.
preorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 node n을 알파벳으로 출력하기 위해 n+'A'를 하여 알파벳으로 출력한다. 그런후 preorder(arr[n][0])와 preorder(arr[n][1])을 차례로 호출하여 재귀 호출되도록 한다.
inorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 inorder(arr[n][0])를 호출한 후, n을 알파벳으로 출력하고, inorder(arr[n][1])을 호출한다.
postorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 postorder(arr[n][0])와 postorder(arr[n][1])을 호출한 후, n을 알파벳으로 출력한다.
각각의 함수들을 main함수에서 n=0으로 시작해 호출하고 결과를 확인한다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
void preorder(int n, vector<vector<int>> &arr) {
if (n == -1) return;
cout << (char)(n + 'A');
preorder(arr[n][0], arr);
preorder(arr[n][1], arr);
}
void inorder(int n, vector<vector<int>> &arr) {
if (n == -1) return;
inorder(arr[n][0], arr);
cout << (char)(n + 'A');
inorder(arr[n][1], arr);
}
void postorder(int n, vector<vector<int>> &arr) {
if (n == -1) return;
postorder(arr[n][0], arr);
postorder(arr[n][1], arr);
cout << (char)(n + 'A');
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<vector<int>> arr(n);
for (int i = 0; i < n; i++) {
char node, l, r;
cin >> node >> l >> r;
int x = node - 'A';
if (l == '.') {
arr[x].push_back(-1);
}
else arr[x].push_back(l-'A');
if (r == '.') {
arr[x].push_back(-1);
}
else arr[x].push_back(r - 'A');
}
preorder(0, arr);
cout << "\n";
inorder(0, arr);
cout << "\n";
postorder(0, arr);
cout << "\n";
return 0;
}
N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
[입력] 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
[출력] 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
✅ 문제 풀이
처음에 시간초과가 발생했던 접근법
miro라는 함수를 호출하여 (0,0)부터 출발하고, 동,서,남,북에 있는 값이 1이면 각각의 위치에서 miro함수를 재귀호출하는 방식을 통해 count해 나간다.
만약 miro함수에서 현재 위치가 (n-1,m-1)이면 현재까지의 count값과 answer값을 비교해서 작은 것을 answer로 갱신한다.
-> 이렇게 되면 n이 커질수록, 재귀호출 양이 많아져 시간 초과가 발생한다.
queue를 이용해 재귀호출을 하지않고 count하는 방식으로 문제를 해결!
miro함수에 queue를 하나 생성한다. 이 queue는 pair로 <<행,렬>, count>로 데이터를 갖고 있다.
queue에 {{0,0},1}을 추가해서 (0,0)위치에서 1카운트 된 것을 queue에 집어넣는다.
다음의 과정은 queue가 빌때까지 실행한다.
queue의 front에서 행의 값을 r에, 열의 값을 c에, count를 count에 넣는다.
이제 여기는 방문한 것이므로 arr값을 0으로 바꾸어준다.
현재 위치가 (n-1,m-1)인지 확인해서 맞다면, 현재의 count값과 기존의 최소 count가 저장된 answer를 비교해서 더 작은 값으로 갱신해준다.
그리고 for문을 통해 현재 위치에서 상,하,좌,우에 있는 값이 1이면 queue에 해당 좌표와 현재의 count에서 +1한 값을 카운트로 넣어주고, 방문했음을 표시하기 위해 해당 위치의 arr값도 0으로 갱신해준다.
miro함수가 끝나고 나면 answer에는 최소 이동 값만이 저장된다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int n, m;
int answer = 10000;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void miro(vector<vector<int>> &arr) {
queue<pair<pair<int, int>, int>> q;
q.push({ { 0, 0 }, 1 });
arr[0][0] = 0;
while (!q.empty()) {
int r = q.front().first.first;
int c = q.front().first.second;
int count = q.front().second;
q.pop();
if (r == n - 1 && c == m - 1) {
answer = min(answer, count);
return;
}
for (int i = 0; i < 4; i++) {
int x = r + dx[i];
int y = c + dy[i];
if (x >= 0 && x < n&&y >= 0 && y < m&&arr[x][y] == 1) {
q.push({ {x,y}, count + 1 });
arr[x][y] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
vector<vector<int>> arr(n);
for (int i = 0; i < n; i++) {
string str;
cin >> str;
for (int j = 0; j < str.length(); j++) {
arr[i].push_back(str[j] - '0');
}
}
miro(arr);
cout << answer;
}
어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다. 빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.
[입력] 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다.
[출력] 각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.
✅ 문제 풀이
행성계를 이탈해야하는 경우와 진입해야 하는 경우로 나누어서 생각할 수 있다.
행성계를 이탈해야 하는 경우 - 출발점이 행성계의 내부에 있고, 도착점이 행성계의 외부에 있는 경우
행성계에 진입해야 하는 경우 - 도착점이 행성계의 내부에 있고, 출발점이 행성계의 외부에 있는 경우
따라서 동일한 행성계 내에 출발점과 도착점이 존재한다면 이탈/진입하지 않는다.
최종 이탈 + 진입 횟수를 구하면 정답이 된다.
✏ 코드 전문
#include<iostream>
#include<math.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;//출발점, 도착점
int n;//행성계의 개수
cin >> n;
int en = 0;
int dep = 0;
for (int j = 0; j < n; j++) {
int cx, cy, r;
cin >> cx >> cy >> r;
//출발점을 포함하는 행성계는 이탈, 도착점을 포함하는 행성계는 진입
if (pow(cx - x1, 2) + pow(cy - y1, 2) <= r*r) {//출발점이 행성계안에있고
if (pow(cx - x2, 2) + pow(cy - y2, 2) > r*r) {//도착점이 행성계 밖에 있는경우
dep++;//이탈
}
}
if (pow(cx - x2, 2) + pow(cy - y2, 2) <= r*r) {//도착점이 행성계안에있고
if (pow(cx - x1, 2) + pow(cy - y1, 2) > r*r) {//출발점이 행성계 밖에 있는경우
en++;//진입
}
}
}
cout << en + dep<<"\n";
}
return 0;
}
