코드 트리 청약 챌린지 진행 중입니다!
관심 있으신 분들은 같이 참여해보세요
https://www.codetree.ai/ko/no-free-lunch-2026/?ref=T38PMZ
3년 만에 돌아온, 코드트리 청약 통장 챌린지 | 코드트리
매주 학습 납입하고 7주 만기 채우면 코드트리 8월까지 무료. 매주 추첨권을 모아 맥북·에어팟·애플워치 응모까지. 신청 인원에 따라 조기마감될 수 있어요.
www.codetree.ai
사각형 칠하기 1
좌표상 사각형 넓이 구하는 방법
좌표상의 좌표 2개를 주고 좌표 안의 사각형 넓이를 구할 때는 좌표를 2차원 격자(배열)로 바꾸고, 좌표 안의 격차일 때 1 값을 저장해 넓이를 구한다.
(x1, y1), (x2, y2) 좌표 영역의 사각형을 2차원 격자로 바꿀 때 오른쪽 상단의 좌표를 (x2 -1, y2-1)을 해야한다.
(2,5), (4, 8) 좌표 영역을 2차원 배열로 만들면, 오른쪽 그림처럼 [2행 5열], [2행 6열], [2행 7열], [3행 5열], [3행 6열], [3행 7열]의 넓이가 1인 정사각형을 카운팅하는 것이기 때문이다.
또한 좌표의 범위가 -100 <= x <= 100이라서 배열의 인덱스가 음수가 된다. 인덱스 에러 방지를 위해 범위의 최솟값을 오프셋을 더한다.
e.g. x = -100 -> x + 100 = -100 + 100 = 0 으로 평행이동하는 것과 같다.
기본 설명에서는 90도 회전한 2차원 배열을 만들었지만, 나의 경우 y(행) -> x(열) 좌표로 탐색하는 것이 익숙했기에 해설과 달리 코드를 작성했다.
문제
사각형의 총 넓이 2 설명 | 코드트리
사각형의 총 넓이 2을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내 코드
- 해설코드는 기본적으로 x1 < x2, y1 < y2를 가정하고 있어 대소 비교를 하는 코드가 없음
- C++에서 <bits/stdc++.h>를 사용하면 모든 라이브러리를 가져오기 때문에 전역변수 명인 y1 변수명이 존재합니다. 따라서 #define으로 임의의 문자열로 대체해야합니다.
#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa
int N, ret, mxx, mxy, mnx, mny;
int x1[10], y1[10];
int x2[10], y2[10];
int offset = 100;
int arr[204][204];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i] += offset;
x2[i] += offset;
y1[i] += offset;
y2[i] += offset;
if(x1[i] > x2[i]) {
mxx = x1[i]; mnx = x2[i];
}
else mxx = x2[i], mnx = x1[i];
if(y1[i] > y2[i]) mxy = y1[i], mny = y2[i];
else mxy = y2[i], mny = y1[i];
for(int j = mny; j <= mxy - 1; j++ ) {
for(int k = mnx; k <= mxx -1; k++) {
arr[j][k] = 1;
}
}
}
for(int i = 0; i < 204; i++ ) {
for(int j = 0; j < 204; j++) {
if(arr[i][j] == 1) ret++;
}
}
cout << ret << "\n";
return 0;
}
해설 코드
#include <iostream>
#define MAX_N 10
#define MAX_R 200
#define OFFSET 100
using namespace std;
int n;
int x1[MAX_N], y1[MAX_N];
int x2[MAX_N], y2[MAX_N];
int checked[MAX_R + 1][MAX_R + 1];
int main() {
// 입력
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
// OFFSET을 더해줍니다.
x1[i] += OFFSET;
y1[i] += OFFSET;
x2[i] += OFFSET;
y2[i] += OFFSET;
}
// 직사각형을 칠해줍니다.
// 격자 단위로 진행하는 문제이므로
// x2, y2에 등호가 들어가지 않음에 유의합니다.
for(int i = 0; i < n; i++)
for(int x = x1[i]; x < x2[i]; x++)
for(int y = y1[i]; y < y2[i]; y++)
checked[x][y] = 1;
// 직사각형 넓이의 총 합을 구합니다.
int area = 0;
for(int x = 0; x <= MAX_R; x++)
for(int y = 0; y <= MAX_R; y++)
if(checked[x][y])
area++;
cout << area;
return 0;
}
사각형 칠하기2 : 여러 직사각형의 넓이 구하기
이 문제의 경우 여러 사각형을 나타내는 좌표 중에서 가장 작은 x좌표, y좌표와 가장 큰 x좌표, y좌표 영역을 탐색하면서 M 사각형을 제외한 사각형의 넓이를 구하면 된다.
각 사각형 간의 영역을 구분하기 위해 이전과 다르게 1, 2 다르게 표기한다.
겹치지 않는 사각형의 넓이 설명 | 코드트리
겹치지 않는 사각형의 넓이을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내 코드
주어진 좌표마다 Offset을 더해야하고, 사각형마다 영역을 표기하는 반복문에서 중복되는 코드가 많이 발생했다.
이는 가독성에서는 함수로 인자만 전달해 처리하는 것이 좋아보인다. 하지만 함수 호출은 비용이 들기 때문에 여기서는 하지 않았다.
해설코드 피드백
- 사각형별로 좌표 변수를 다 선언할 필요 없음. 배열의 크기가 3인 배열 4개를 활용 x1[3], x2[3], y1[3], y2[3]
- 배열에 사각형 좌표를 저장하면 이중 for문과 offset 더하는 부분이 1개로 축약됨
#include<bits/stdc++.h>
#define offset 1000
using namespace std;
int ax1, ay1, ax2, ay2, bx1, bx2, by1, by2, mx1, mx2, my1, my2;
int ret, mnx, mxx, mny, mxy;
int checked[2004][2004];
int main() {
ios_base::sync_with_stdio(false);
cin >> ax1 >> ay1 >> ax2 >> ay2;
cin >> bx1 >> by1 >> bx2 >> by2;
cin >> mx1 >> my1 >> mx2 >> my2;
ax1 += offset; ax2 += offset; ay1 += offset; ay2 += offset;
bx1 += offset; bx2 += offset; by1 += offset; by2 += offset;
mx1 += offset; mx2 += offset; my1 += offset; my2 += offset;
mnx = min(ax1, bx1);
mxx = max(ax2, bx2);
mny = min(ay1, by1);
mxy = max(ay2, by2);
for(int y = ay1 ; y < ay2; y++) {
for(int x = ax1; x < ax2; x++) {
checked[y][x] = 1;
}
}
for(int y = by1 ; y < by2; y++) {
for(int x = bx1; x < bx2; x++) {
checked[y][x] = 2;
}
}
for(int y = my1 ; y < my2; y++) {
for(int x = mx1; x < mx2; x++) {
checked[y][x] = 0;
}
}
for(int y = mny; y < mxy; y++) {
for(int x = mnx; x < mxx; x++) {
if(checked[y][x]) ret++;
}
}
cout << ret << "\n";
return 0;
}
해설코드
#include <iostream>
#define N 3
#define MAX_R 2000
#define OFFSET 1000
using namespace std;
int x1[N], y1[N];
int x2[N], y2[N];
int checked[MAX_R + 1][MAX_R + 1];
int main() {
// 입력
for(int i = 0; i < N; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
// OFFSET을 더해줍니다.
x1[i] += OFFSET;
y1[i] += OFFSET;
x2[i] += OFFSET;
y2[i] += OFFSET;
}
// 직사각형에 주어진 순으로 1, 2, 3 번호를 붙여줍니다.
// 격자 단위로 진행하는 문제이므로
// x2, y2에 등호가 들어가지 않음에 유의합니다.
for(int i = 0; i < N; i++)
for(int x = x1[i]; x < x2[i]; x++)
for(int y = y1[i]; y < y2[i]; y++)
checked[x][y] = i + 1;
// 1, 2, 3 순으로 붙였는데도
// 아직 숫자 1, 2로 남아있는 영역의 넓이를 구합니다.
int area = 0;
for(int x = 0; x <= MAX_R; x++)
for(int y = 0; y <= MAX_R; y++)
if(checked[x][y] == 1 || checked[x][y] == 2)
area++;
cout << area;
return 0;
}
Challenge 1 : 색종이의 총 넓이
색종이의 총 넓이 설명 | 코드트리
색종이의 총 넓이을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
Challenge 2 : 잔해물을 덮기 위한 사각형의 최소 넓이
잔해물을 덮기 위한 사각형의 최소 넓이 설명 | 코드트리
잔해물을 덮기 위한 사각형의 최소 넓이을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
개인적인 평가
- 코드를 작성하는 것보다 풀이 방법을 떠올리는데 시간이 많이 소요됨
- 겹치는 영역이 첫번째 직사각형의 가로/세로 부분을 모두 겹치는 것도 아니어서 어떻게 덮는 게 최소 직사각형인지 방법을 떠올리는 것이 어려움.
내풀이
풀이시간 : 4시간
접근방법
- 각각 사각형의 양끝 좌표를 기준으로 2차원 배열에 첫번째 사각형은 1, 두번째 사각형은 2로 색칠(저장)한다.
- 첫번째 사각형 영역을 탐색하며 두번째 사각형과 겹치지 않는 "첫번째 사각형 영역" 1인 영역 중 좌표(인덱스) x의 최소/최댓값, y의 최소/최댓값을 구한다.
- 두번째 사각형이 첫번째 사각형의 모든 영역을 덮어쓴 경우와 아닌 경우를 나누어 첫번째 사각형의 넓이를 덮을 최소 넓이를 구한다.
실수한 부분
벡터에 첫번째 사각형의 영역 중 겹치지 않은 부분의 좌표만 저장하고, sort()로 정렬할 때 맨 마지막 원소의 (y, x)일 때 y는 가장 큰 값일지언정 x는 큰 값이 들어가는 것이 아님.
for(int i = 0; i < MAX; i++) {
for(int j = 0; j < MAX; j++) {
if(arr[i][j] == 1 || arr[i][j] == 3) v.push_back({j,i}); // x, y좌표
}
}
sort(v.begin(), v.end()); // v[(int)v.size() - 1]
맞춘 풀이
해설코드와 다른 점
- 해설코드는 두 사각형이 겹친 부분에 3이란 다른 값을 넣지 않음, 겹친 부분은 두번째 사각형이 마지막으로 칠하는 상태로 둠
- 이걸 적용하면 3중 for문에서 조건문이 제거됨. 실행시간이 4ms, 메모리 1ms 감소됨
#include<bits/stdc++.h>
using namespace std;
#define y1 aaaa
#define OFFSET 1000
#define MAX 2004
int mxx[2], mxy[2],mnx[2], mny[2];
int x1[2],x2[2], y1[2], y2[2];
int arr[MAX][MAX];
vector<pair<int,int>> v;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
for(int i = 0; i < 2; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
x1[i] += OFFSET; y1[i] += OFFSET; x2[i] += OFFSET; y2[i] += OFFSET;
}
// 2차원 좌표에 각 사각형의 영역을 색칠한다.
for(int i = 0; i < 2; i++) {
mxy[i] = max(y1[i], y2[i]); mny[i] = min(y1[i], y2[i]);
mxx[i] = max(x1[i], x2[i]); mnx[i] = min(x1[i], x2[i]);
for(int j = mny[i]; j < mxy[i]; j++) {
for(int k = mnx[i]; k < mxx[i]; k++) {
if(arr[j][k] != 0) arr[j][k] = 3; // 두 사각형이 겹치는 영역 : 3
else arr[j][k] = i + 1; // 1 : A, 2 : B
}
}
}
int mxx_ = -1e9, mxy_ = -1e9, mnx_ = 1e9, mny_ = 1e9;
for(int i = mny[0]; i < mxy[0]; i++) { // i = y
for(int j = mnx[0]; j < mxx[0]; j++) { // j = x
if(arr[i][j] == 1 ) {
if(j > mxx_ ) mxx_ = j;
if(j < mnx_) mnx_ = j;
if(i > mxy_) mxy_ = i;
if(i < mny_) mny_ = i;
}
}
}
if(mxx_ == -1e9 || mxy_ == -1e9 || mnx_ == 1e9 || mny_ == 1e9) cout << 0 << "\n";
else cout << (mxx_ - mnx_ + 1) * (mxy_ - mny_ + 1) << "\n" ;
return 0;
}
해설코드
#include <iostream>
#include <algorithm>
#define N 2
#define MAX_R 2000
#define OFFSET 1000
using namespace std;
int x1[N], y1[N];
int x2[N], y2[N];
int checked[MAX_R + 1][MAX_R + 1];
int main() {
// 입력
for(int i = 0; i < N; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
// OFFSET을 더해줍니다.
x1[i] += OFFSET;
y1[i] += OFFSET;
x2[i] += OFFSET;
y2[i] += OFFSET;
}
// 직사각형에 주어진 순으로 1, 2 번호를 붙여줍니다.
// 격자 단위로 진행하는 문제이므로
// x2, y2에 등호가 들어가지 않음에 유의합니다.
for(int i = 0; i < N; i++)
for(int x = x1[i]; x < x2[i]; x++)
for(int y = y1[i]; y < y2[i]; y++)
checked[x][y] = i + 1;
// 1, 2 순으로 붙였는데도
// 아직 숫자 1로 남아있는 곳들 중 최대 최소 x, y 값을 전부 계산합니다.
int min_x = MAX_R, max_x = 0, min_y = MAX_R, max_y = 0;
bool first_rect_exist = false;
for(int x = 0; x <= MAX_R; x++)
for(int y = 0; y <= MAX_R; y++)
if(checked[x][y] == 1) {
first_rect_exist = true;
min_x = min(min_x, x);
max_x = max(max_x, x);
min_y = min(min_y, y);
max_y = max(max_y, y);
}
// 넓이를 계산합니다.
int area;
// Case 1. 첫 번째 직사각형이 전혀 남아있지 않다면 넓이는 0입니다.
if(!first_rect_exist)
area = 0;
// Case 2. 첫 번째 직사각형이 남아있다면, 넓이를 계산합니다.
else
area = (max_x - min_x + 1) * (max_y - min_y + 1);
cout << area;
return 0;
}Test : 계속 중첩되는 사각형 설명
계속 중첩되는 사각형 설명 | 코드트리
계속 중첩되는 사각형을 통해 문제 요구사항과 입력·출력 예시를 꼼꼼히 확인해 정확한 풀이 전략을 세워보세요.
www.codetree.ai
내 코드
풀이 논리
- 사각형 칠하기 개념 두번째 문제처럼 사각형 별로 좌표에 해당하는 영역을 2차원 배열에 표기
- 사각형이 빨간색 -> 파란색 -> 빨간색 .. 반복되니까 모듈러 연산자로 영역을 구분
놓친 부분
- 빨간색, 파란색 번갈아가며 색칠하되, 마지막으로 색칠된 것은 파란색이 아닐 수도 있음
- 테스트 케이스가 번갈아가면서 색이 바뀌니까 모듈러 연산자(나머지 연산자)로 사각형 별로 영역을 표기해줘야함.
해설 코드 차이점
- 해설 좌표를 기반으로 사각형 영역 표기할 때 if문으로 쓰지 않고 삼항 연산자(? : )를 이용해 간단히 표현함
- i % 2 ? 2 : 1
- 해설은 OFFSET 적용을 입력받을 때 진행하여, 목적별로 분리가 잘 됨.
#include<bits/stdc++.h>
#define OFFSET 100
#define y1 aaaa
#define MAX 204
using namespace std;
int checked[MAX][MAX];
int x1[MAX], y1[MAX], ret;
int x2[MAX], y2[MAX];
int n;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
}
for(int i = 0; i < n; i++ ) {
x1[i] += OFFSET; y1[i] += OFFSET;
x2[i] += OFFSET; y2[i] += OFFSET;
for(int j = y1[i]; j < y2[i]; j++) {
for(int k = x1[i]; k < x2[i]; k++) {
// if(checked[j][k]) checked[j][k] = 3;
if(i % 2 == 0) checked[j][k] = 2;
else checked[j][k] = i % 2;
}
}
}
for(int i = 0; i < MAX; i++) {
for(int j = 0; j < MAX; j++) {
if(checked[i][j] % 2 == 1) {
// cout << i << " : " << j << "\n";
ret++;
}
}
}
cout << ret << "\n";
return 0;
}
해설 코드
#include <iostream>
#define MAX_N 10
#define MAX_R 200
#define OFFSET 100
using namespace std;
int x1[MAX_N], y1[MAX_N];
int x2[MAX_N], y2[MAX_N];
int checked[MAX_R + 1][MAX_R + 1];
int main() {
// 변수 선언 및 입력
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
// OFFSET을 더해줍니다.
x1[i] += OFFSET;
y1[i] += OFFSET;
x2[i] += OFFSET;
y2[i] += OFFSET;
}
// 직사각형에 주어진 순으로 1, 2 번호를 붙여줍니다.
// 격자 단위로 진행하는 문제이므로
// x2, y2에 등호가 들어가지 않음에 유의합니다.
for(int i = 0; i < n; i++)
for(int x = x1[i]; x < x2[i]; x++)
for(int y = y1[i]; y < y2[i]; y++)
checked[x][y] = i % 2 ? 2 : 1;
// 숫자 2로 남아있는 영역의 넓이를 구합니다.
int area = 0;
for(int x = 0; x <= MAX_R; x++)
for(int y = 0; y <= MAX_R; y++)
if(checked[x][y] == 2)
area++;
cout << area;
return 0;
}'Algorithm' 카테고리의 다른 글
| [CodeTree] Ch5.시뮬레이션 2 - 최장 연속 부분 수열 (0) | 2026.06.01 |
|---|---|
| [CodeTree] 4회차: 코테 꾸준히 하고자 하는 습관을 지켜주는 환경 (feat. 학습 리마인더 알림톡) (0) | 2026.06.01 |
| [CodeTree] 3회차: Trail2.시뮬레이션1 약점 학습 후기 (0) | 2026.05.22 |
| [CodeTree 후기] 코드트리 청약 챌린지 참여 - 2회차 : 갭체크 (0) | 2026.05.18 |
| [백준] 6234번 : 용돈 관리 (도식화 -> 로직 -> 코드) (0) | 2026.03.11 |