Posted Updated a minute read (About 216 words)

B1992

개요

백준 문제 1992번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/1992

문제

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며,
이 영상을 쿼드 트리 구조를 이용하여 압축하면 “(0(0011)(0(0111)01)1)”로 표현된다.
N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string> 
using namespace std;
const int MAX = 64;
int input[MAX][MAX];
string tmp = "";
bool allPixelSame(int startRow,int startCal,int divUnit)
{
	int comparePixel = input[startRow][startCal];
	for(int i=0;i<divUnit;i++)
	{
		for(int j=0;j<divUnit;j++)
		{
			if(input[startRow+i][startCal+j] != comparePixel)
			{
				return false;
			}

		}
	}
	return true;


}

void quadTree(int startRow,int startCal,int divUnit)
{

	if(divUnit == 1 || allPixelSame(startRow,startCal,divUnit))
	{
		tmp.append(to_string(input[startRow][startCal]));
	}
	else
	{
		tmp.append("(");
		for(int i=0;i<divUnit;i+= divUnit/2)
		{
			for(int j=0;j<divUnit;j+=divUnit/2)
			{
				quadTree(startRow+i,startCal+j,divUnit/2);
			}
		}
		tmp.append(")");
	}

}

void solve()
{
	int N;
	char tmpInput;
	cin >> N;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			cin >> tmpInput;
			input[i][j] = tmpInput - '0';
		}
	}
	quadTree(0,0,N);
	cout << tmp;

}

int main()
{
	solve();
}

풀이

전형적인 분할정복 문제이며 이전에 풀었던 문제와 유사한 유형이어서 쉽게 풀 수 있었음.

배울 점, 메모

Posted Updated 4 minutes read (About 550 words)

B11729

개요

백준 문제 11729번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 120분
https://www.acmicpc.net/problem/11729

문제

하노이타워 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라.
단, 이동 횟수는 최소가 되어야 한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cmath>
using namespace std;


void hanoi(int n,int from,int by,int to) 
{
	if(n == 1)
	{
		cout << from << " " << to << "\n";
	}
	else
	{
		hanoi(n-1,from,to,by);
		cout << from << " " << to << "\n";
		hanoi(n-1,by,from,to);

	}
}

void solve()
{
	int N;
	int K;
	cin >> N;
	K = pow(2,N) -1;

	cout << K << "\n";
	hanoi(N,1,2,3);
}

int main()
{
	solve();

}

풀이

div and conquer방식은 어느정도 이해를 했다 생각하지만
실제 문제에 도입해서 풀려고하니 잘 풀리지 않았다.
(대부분 분할에 재귀형식으로 구현하는 것이 직관적임)
또한 하노이 타워 자체의 해결법을 알지 못해 혼자 스스로 생각하다
시간이 많이 걸렸다.

배울 점, 메모

  1. 하노이 타워같은 풀이방식은 내가 직접 찾기는 오래걸리고 힘들다.
    (어차피 규칙성에서 풀이를 찾는 것이라 크게 의미는 없다 봄)
  2. 1 따라서 이런 수학적이고 약간 노가다의 알고리즘은 찾아보는 것도 나쁘지 않다봄
  3. 한번 찾아본 것들은 잊어버리지 않는다는 생각으로 보고 반복하고 다시 생각해볼 것
  4. 하노이 타워 remind
    3.1 n-1의 원반을 중간 기둥에 옮김
    3.2 n번째 원반을 목적지에 옮김
    3.3 중간 기둥에서 목적지까지 옮김

    어려웠던 점

    여기서 중간 기둥으로 옮긴다는 것에는 다른 빈 기둥에 넣는다는 것을 내포한다.
    이것을 재귀나 코드로 구현하기가 어려웠다(다른 빈 기둥을 찾는것도 이상했고 복잡하다 생각해서)
  5. 문제의 케이스를 따라하며 풀이를 생각하고 찾는데,
    이 방법은 문제의 케이스에만 fit만 코드가 나올 때도 있어
    (사실 아직은 실력이 부족해 대부분) 이부분 주의해야함.
Posted Updated 2 minutes read (About 345 words)

B1780

개요

백준 문제 1780번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 120분
https://www.acmicpc.net/problem/1780

문제

N×N크기의 행렬로 표현되는 종이가 있다.
종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다.
우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cmath>
using namespace std;

const int MAX = 2200;
int arrNum[MAX][MAX];
int result[3];

bool isSameNumberPaper(int startRow,int startCal,int divUnit)
{

	int compareNum = arrNum[startRow][startCal];
	for(int i=0;i<divUnit;i++)
	{
		for(int j=0;j<divUnit;j++)
		{
			if(arrNum[startRow+i][startCal+j] != compareNum)
			{
				return false;
			}
		}
	}
	return true;
}

void divAndConquer(int startRow,int startCal, int divUnit)
{
	int val = arrNum[startRow][startCal];
	if(divUnit <= 1 || isSameNumberPaper(startRow,startCal,divUnit))
	{
		if(val == -1)
		{
			result[2] += 1;
		}
		else
		{
			result[val] += 1;
		}
	}
	else
	{
		for(int i=0;i< divUnit; i += divUnit/3)
		{
			for(int j=0;j< divUnit; j += divUnit/3)
			{
				divAndConquer(i+startRow,j+startCal,divUnit/3);
			}

		}
	}
}

void solve()
{
	int N;
	cin >> N;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			cin >> arrNum[i][j];
		}
	}
	divAndConquer(0,0,N);
	cout << result[2] << "\n";
	cout << result[0] << "\n";
	cout << result[1] << "\n";


}

int main()
{
	fill_n(result,3,0);
	solve();
}

풀이

divide and conquer

배울 점, 메모

문제를 잘못 이해해서 분할의 크기를 divide할 때 9로만 나눴는데
당연히 3으로 나눴어야 했다.(문제 조건을 보라)

Posted Updated 3 minutes read (About 512 words)

B11622

개요

백준 문제 11622번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 90분
https://www.acmicpc.net/problem/11622

문제

민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다. 또, 두 사람은 항상 일정한 속도로 걸어간다. 두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <iostream>
#include <cmath>

using namespace std;

typedef struct
{
	double x;
	double y;
}point;

double calDistance(point A,point B)
{
	return pow(A.x-B.x,2) + pow(A.y-B.y,2);
}
void setPoint(point * A,point * B,point * C,point * D)
{
	int Ax,Bx,Cx,Dx;
	int Ay,By,Cy,Dy;
	cin >> Ax >> Ay >> Bx >> By;
	cin >> Cx >> Cy >> Dx >> Dy;
	A->x = Ax;
	A->y = Ay;
	B->x = Bx;
	B->y = By;
	C->x = Cx;
	C->y = Cy;
	D->x = Dx;
	D->y = Dy;
}

point getPoint(double k,point A,point B)
{
	point resultPoint;
	resultPoint.x = A.x + (B.x - A.x) * (k/100);
	resultPoint.y = A.y + (B.y - A.y) * (k/100);
	return resultPoint; 
}


void solve()
{
	point A,B,C,D;
	setPoint(&A,&B,&C,&D);
	double minResult = 987654321;
	double fp = 0,lp=100,limit=2e9;
	double distA,distB;
	while(lp-fp>=1e-10)
	{
		double k1 = (fp*2 + lp) / 3;
		double k2 = (fp + lp * 2) / 3;
		point curPointAB_1 = getPoint(k1,A,B);
		point curPointCD_1 = getPoint(k1,C,D);
		point curPointAB_2 = getPoint(k2,A,B);
		point curPointCD_2 = getPoint(k2,C,D);
		distA = calDistance(curPointAB_1,curPointCD_1);
		distB = calDistance(curPointAB_2,curPointCD_2);
		minResult = min(minResult,min(distA,distB));
		if(distA >= distB)
		{
			fp = k1;
		}
		else
		{
			lp = k2;
		}


	}
	cout << sqrt(minResult);


}

int main()
{
	cout << fixed;
	cout.precision(6);	
	solve();

}


풀이

이분탐색으로 풀려고 했는데, 이분탐색의 경우 mid값을 정하는데 애매한 부분이 있고
실제로 이 문제에서는 오차문제로 인해 잘 풀리지 않는다.
삼분탐색이나 미적분을 이용한 방법이 있었는데 삼분탐색을 보고 카피해 풀었다.

배울 점, 메모

이분탐색 = 명확한 값 변화가 있을 때
범위,근사값 등이면서 볼록함수 형태 = 삼분탐색

Follow

Categories

Recents

Archives

Tags

CRF3
algorithm72
book_report2
database1
java26
jpa1
pet project12
pet_project1
retrospect1
springboot3
web3
web pet project2
write3

Subscribe for updates

×