Technology/Problem Solving

[BOJ] 1992번: 쿼드트리

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 0ms - 사용 공간 : 1228KB 풀이 설명 - Top-down 흐름의 Divide-and-conquer 문제 #include #include #include using namespace std; vector matrix; string GetQaudTreeString(int offset_y, int offset_x, int si..

[BOJ] 2448번: 별 찍기 - 11

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 20ms - 사용 공간 : 2460KB 풀이 설명 - 프랙탈 형태의 패턴 출력 문제 - divide-and-conquer로 작은 문제로 쪼개 해결하였다. - 재귀형식으로 Top-down으로 문제를 접근하였다. #include #include #include using namespace std; int GetHeight(int generation) { return 3 * pow(2, generati..

[BOJ] 2250번: 트리의 높이와 너비

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 공간 제한 : 128MB 시간 제한 : 2s 사용 공간 : 2460KB 사용 시간 : 20ms 설명 - 입력받은 정보를 토대로 트리를 제작한다. - 맨 왼쪽의 노드의 x 위치를 0으로 두고 중위 순회를 통해 각 노드들의 x 위치를 구해준다. - 이후 그래프의 최대 너비와 해당 depth를 구해준다. #include #include #include using namespace std; class Node { private: public: int ..

[BOJ] 2904번: 수학은 너무 쉬워

2904번: 수학은 너무 쉬워 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다. www.acmicpc.net 공간 제한 : 128MB 시간 제한 : 1s 사용 공간 : 33,712KB 사용 시간 : 40ms 설명 - 결국에 인수들을 최대한 균등하게 이동시키는게 관건인거 같다. - 에라토스테네스의 체를 이용하여 입력받은 수들을 소인수분해했다. - 입력받은 모든 수들의 소인수분해값들을 모은 값을 수의 개수로 나눠주고, 그걸 만들기위한 이동 횟수를 센다. #include #include using namespace std; // 선택될수있는 수의 최대 크기 (편의상 +1 했음) const int M..