2024 - 07 - 22 C++ 코딩테스트 10주완성 D+19
백준 1992 문제 - 쿼드 트리
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다.
흰 점을 나타내는 0 과 검은 점을 나타내는 1로만 이루어진 영상에서 같은 숫자의 점들이 한 곳에 많이 몰려 있으면,
쿼드트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 0, 모두 1로만 되어 있으면 1이 된다.
0과 1이 섞여 있는 배열이면 전체를 한번에 나타내지 못하고 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.
입력
첫째 줄에는 영상의 크기를 나타내는 숫자 N
(단 N은 언제나 2의 제곱수로 주어지며, 1 <= N <= 64의 범위를 가진다.)
두 번째 줄부터는 길이 N의 문자열 N개를 입력
(각 문자열은 0 또는 1의 숫자로 이루어져 있다.)
출력
영상을 압축한 결과 출력
#include <bits/stdc++.h>
using namespace std;
// 1. 변수 및 함수 목록
// 0,1로 입력받은 인덱스를 담을 2차원 배열 int a[][]
// 압축한 결과물 저장하고 출력할 문자 ret
// 방향을 담을 1차원 배열 int dy[],dx[]
// 배열의 크기를 입력받는 int n ( 1 <= n <= 64)
// dfs 탐색을 할때 검사하는 인덱스의 좌표를 넣을 int ux,uy
// dfs 탐색을 하고 매개인수를 y좌표 int y, x좌표 int x, 검사할 사이즈 int size를 받을
// 함수 dfs 선언
// 주어진 배열의 원소가 전부 0 또는 1임을 검사할 int cnt
const int max_n = 68;
char a[max_n][max_n];
int n, ux, uy, cnt;
string ret;
// ㄴ4.dfs 함수
// ㄴ4-1.visited 배열 - 받은 y,x 값에 해당하는 위치의 값을 1로 저장한다.
// ㄴ4-2 ret += (
// ㄴ4-3.조건이 받은 dy,dx 좌표로 부터 시작되고 size의 제곱근까지 반복하는
// 반복문을 만든다.
// ㄴ4-3-1.만약 반복문에서 a[dy][dx]가 1일 경우 cnt++ 를 해준다.
// ㄴ4-3-2.반복문이 끝난후 cnt가 0일경우 ret += "0)" 를
// ㄴ4-3-3.cnt가 size랑 같을 경우 ret +="1)"을 해준다.
// 둘다 아닐 경우에는 왼쪽 위,오른쪽 위, 왼쪽 아래, 오른쪽 아래인
// dfs(dy,dx,size/4),dfs(dy,dx+(sqrt(size)/2,size/4),
// dfs(dy+(sqrt(size)/2),dx,size/4),dfs(dy+(sqrt(size)/2),dx+(sqrt(size)/2,dx+,size/4)
// return ret;
string dfs(int y, int x, int size)
{
string str;
cnt = 0;
for (int dy = y; dy < y + sqrt(size); dy++)
{
for (int dx = x; dx < x + sqrt(size); dx++)
{
if (a[dy][dx] == '1')
cnt++;
}
}
if (size == 1)
{
str += a[y][x];
}
else if (cnt == 0)
{
str += "0";
}
else if (cnt == size)
{
str += "1";
}
else
{
str += "(";
str += dfs(y, x, size / 4);
str += dfs(y, x + (sqrt(size) / 2), size / 4);
str += dfs(y + (sqrt(size) / 2), x, size / 4);
str += dfs(y + (sqrt(size) / 2), x + (sqrt(size) / 2), size / 4);
str += ")";
}
return str;
}
int main()
{
// 2. 알고리즘
// ㄴ1. n의 값을 입력받는다.
// ㄴ2. n * n 의 크기만큼 a[][]의 원소안에 들어갈 값을 집어넣는다.
// ㄴ2-1 반복문안에 a[0][0] 과 a[i][j] 번째 인덱스를 비교하여
// 다를 경우 cnt++를 하여준다.
// ㄴ3. 반복문이 끝나고 cnt가 0 또는 (n * n)-1 이면 a[0][0] 안의 값을 출력시켜준다.
cin >> n;
if ((n & (n - 1)) != 0)
return 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
if (a[i][j] == '1')
cnt++;
}
}
if (cnt == 0)
cout << "0";
else if (cnt == (n * n))
cout << "1";
// ㄴ3-1 cnt가 0 또는 (n * n) -1 이 아닐 경우
// ㄴ cnt를 0으로 초기화해준후
// ㄴ 함수 dfs를 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로
// dfs(0,0,(n*n)/4), dfs(0,n/2,(n*n)/4),dfs(n/2,0,(n*n)/4),dfs(n/2,n/2,(n*n)/4)를 호출한다.
else
{
cnt = 0;
ret += "(";
ret += dfs(0, 0, (n * n) / 4);
ret += dfs(0, n / 2, (n * n) / 4);
ret += dfs(n / 2, 0, (n * n) / 4);
ret += dfs(n / 2, n / 2, (n * n) / 4);
ret += ")";
}
cout << ret;
return 0;
}
이 문제의 핵심은 DFS 알고리즘을 이용한 String 형 재귀함수를 이용하는 것이다.
String 형 재귀함수가 돌때마다, 탐색한 원소가 1이면 Cnt++ 를 해주어, 0 과 1로만 이루어져 있는지 확인하고, 아닐 시
다시 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀함수를 호출하여 주는 식으로 알고리즘을 구성하였습니다.
비록 강의를 조금 참조하긴 했지만,, 그래도 오늘은 2트만에 합격..★
기분이 좋다 헤헤 ㅋㅋ,
하지만 강의코드 비교시간은 무조건 가져봐야 하는 법! 비교해보자
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
string s;
char a[101][101];
string quard(int y, int x, int size){
if(size == 1) return string(1, a[y][x]);
char b = a[y][x];
string ret = "";
for(int i = y; i < y + size; i++){
for(int j = x; j < x + size; j++){
if(b != a[i][j]){
ret += '(';
ret += quard(y, x, size / 2);
ret += quard(y, x + size / 2, size / 2);
ret += quard(y + size / 2, x, size / 2);
ret += quard(y + size / 2, x + size / 2, size / 2);
ret += ')';
return ret;
}
}
}
return string(1, a[y][x]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++){
cin >> s;
for(int j = 0; j < n; j++){
a[i][j] = s[j];
}
}
cout << quard(0, 0, n) << '\n';
return 0;
}
차이점
메인함수안의 원소값을 입력받는 부분에서 String 형식으로 받은 다음 각각 문자열 배열안에 값을 집어넣었다.
Cnt 라는 변수를 쓰지않고 재귀함수안에 임시 문자열 변수인 b를 선언 및 받은 매개인수(y,x)의 위치의 값으로 초기화시켜
0 과 1로만 이루어져 있는 지 확인하였다..!!
그리고 quard 의 매개인수인 size 의 값을 넓이가 아닌, 행 또는 열의 길이를 넣음으로써, 다음 재귀함수를 호출할 때
계산식을 더욱 더 간단하게 호출할 수 있다.
같은 결과지만 코드가 이렇게 간결해질 수 있다니,, 더욱 더 분발해야겠다!
백준 2828 문제 - 사과 담기
스크린은 N칸으로 나누어져 있고, 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다.(M < N)
바구니는 왼쪽이나 오른쪽으로 이동할 수 있지만, 스크린의 경계를 넘어가면 안된다.
가장 처음에 바구니는 가장 왼쪽 M칸을 차지하고 있다.
스크린의 위에서 사과 여러개가 떨어진다. 각 사과는 N칸중 하나에 떨어지기 시작하며, 한 사과가 바닥에 닿는 즉시
다른 사과가 떨어지기 시작한다.
바구니는 사과가 떨어지는 칸을 차지하고 있으면 사과가 바닥에 닿을 때, 사과를 담을 수 있다.
사과를 모두 담으려고 할때, 바구니 이동 거리의 최솟값을 구하여라.
입력
첫째 줄.스크린의 크기 N 과 바구니의 크기 M을 입력받는다.
둘째 줄.떨어지는 사과의 개수 J 를 입력받는다.
그 다음 J 만큼 사과가 떨어지는 위치를 순서대로 입력받는다.
출력
모든 사과를 담기 위해 바구니가 이동해야 하는 거리의 최솟값
실습코드
#include <bits/stdc++.h>
using namespace std;
//1. 필요한 변수 목록
//스크린의 크기를 담을 int형 변수 N
//바구니의 크기를 담을 int형 변수 M
//사과의 개수를 담을 int형 변수 J
//바구니의 왼쪽끝,오른쪽끝을 담을 int형 변수 lm,rm
//사과가 떨어지는 위치를 순서대로 담을 int형 1차원 배열 dp[24]
//바구니가 이동한 총 거리를 담을 int형 변수 ret
int N, M,lm,rm,ret,J;
int dp[24];
int main()
{
//2. 알고리즘
//2-1.N과 M을 입력받는다. ( 1<= N,M <= 10, M<N)
//2-2.J를 입력받는다. ( 1 <= J <= 20 )
//2-3.J의 개수만큼 반복문을 돌려 dp[i]안에 값을 입력시킨다.
//2-4.rm 의 값을 rm + (m-1) 으로 초기화시킨다.
//2-5.반복문
//2-5-1 조건 : 사과의개수 J만큼 반복문을 돌린다.
//2-5-2 만약 n <= dp[i] <= m 이면 continue
//2-5-2 만약 dp[i] > m 면 m = m + (dp[i]-m)와 l = l + (dp[i] - m) 와 ret += dp[i] - m
//2-5-3 만약 dp[i] < n 면 m = m - (n-dp[i])와 l = l - (n-dp[i]) 와 ret += n - dp[i]
//2-6.ret 출력
cin >> N >> M;
if (N < 1 || M < 1 || N > 10 || M > 10 || M > N)
return 0;
rm += (M - 1);
cin >> J;
for (int i = 0; i < J; i++)
{
cin >> dp[i];
int dt = 0;
if (dp[i] <= 0 || dp[i] > 20)
return 0;
else if (dp[i] > rm)
{
dt = (dp[i] - rm);
rm += dt;
lm += dt;
}
else if (dp[i] < lm)
{
dt = (lm - dp[i]);
rm -= dt;
lm -= dt;
}
ret += dt;
}
cout << ret -1;
}
이 문제는 생각보다 난이도가 낮았다!!
핵심포인트는 바구니의 크기에 따른 양쪽 포인트 lm,rm 의 값을 조정해주면 된다!
1.스크린의 길이(n)과 바구니의 크기(m)을 입력받은 다음
2.사과의 개수를 입력받는다.
3.사과의 개수에 따라 반복문을 돌린다.
ㄴ3-1. 사과의 위치를 입력받는다.
ㄴ3-2. 거리를 담을 정수형 변수 dt를 선언한다.
ㄴ3-3. 사과의 위치가 바구니 오른쪽인 rm보다 크면 dp[i] - rm 을 해주어 dt 에 담는다.
ㄴ3-3-1. rm과 lm이 오른쪽으로 이동했으므로 dt를 더해준다.
ㄴ3-4. 사과의 위치가 바구니 왼쪽인 lm보다 작으면 lm이 더 크므로 lm - dp[i] 을 해주어 dt에 담는다.
ㄴ3-4-1. rm과 lm이 왼쪽으로 이동했으므로 dt를 빼준다.
ㄴ3-5. 이동한 거리만큼 ret에 더해준다.
4. 반복문이 끝나면 ret을 출력해준다.
쉽게 끝났어도 강의코드랑 비교해주는 건 필수!!
강의코드
#include <bits/stdc++.h>
using namespace std;
int n, m, j, l, r, temp, ret;
int main () {
cin >> n >> m >> j;
l = 1;
for(int i = 0; i < j; i++){
r = l + m - 1;
cin >> temp;
if(temp >= l && temp <= r) continue;
else{
if(temp < l){
ret += (l - temp);
l = temp;
}else{
l += (temp - r);
ret += (temp - r);
}
}
}
cout << ret << "\n";
return 0;
}
역시.. 배우신 분이라 코드가 간결 그자체다.
이 코드를 보니, 또 배워간다..
1.내가 코드를 짤때 썻던 정수형 배열을 쓸 필요가 없었다..!!
메모리 공간을 충분히 절약할 수 있었는데, 미처 거기까지 생각하지 못하였다.
2. 조건문을 훨씬 더 간단하게 표현할 수 있었다.
다음부터 계산식을 좀 더 단순하게 만들어 코드를 줄일 필요성이 있어보인다.
이렇게 간단한거 같았던 문제에서도 여러 고칠점이 보인다..
참고하여서 좀더 효율성이 좋은 코드를 작성해보아야겠다..!!