표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 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;
}
