본문 바로가기

알고리즘/알고스팟7

[알고스팟/C,C++] FENCE: 울타리 잘라내기 www.algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 www.algospot.com 도무지 풀이가 떠오르지 않아 알고리즘 문제 해결 전략의 코드를 참고하여 풀었습니다 ㅜㅜ 반으로 잘라도 옆의 사각형과 연결을 시켜야 하는데 이 부분에서 애를 많이 먹었는데요. 중간을 기점으로 분할한 왼쪽과 오른쪽 중 큰 사각형을 받아오고 그 사각형을 기준으로 현재 검색할 구간의 끝까지 사각형을 합쳐 더 큰 사각형을 계속 반환합니다. int dv(int left, int right.. 2021. 3. 27.
[알고스팟/C,C++] QUADTREE: 쿼드 트리 뒤집기 www.algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 www.algospot.com 처음에 입력값을 제대로 보지 않고 풀었는데, 들어올 수 있는 입력값이 $2^{20}\times 2^{20}$ 으로 매우 큰 수 입니다. 최초 시도는 입력값을 16 x 16 크기의 배열 형태로 변환하고, 그것을 뒤집은 뒤, 다시 압축하였습니다. 당연히 결과는 오답입니다. 쿼드 트리의 크기가 16 x 16으로 고정이 아닐뿐더러, 해당 방법으로는 시간이 초과.. 2021. 3. 27.
[알고스팟/C,C++] CLOCKSYNK: Synchronizing Clocks www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 재귀 호출을 통해 완전 탐색을 구현하는 것만으로 해결이 가능한 문제입니다. int clocks[CLOCK_CNT]; int* switches[SWITCH_CNT]{ new int[3]{0, 1, 2}, new int[4]{3, 7, 9, 11}, new int[4]{4, 10, 14, 15}, new int[5]{0, .. 2021. 3. 15.
[알고스팟/C,C++] BOARDCOVER: 게임판 덮기 www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 www.algospot.com 흔한 완전 탐색 문제기에, 코드를 짜는 것의 난이도 자체는 높지 않다고 생각합니다. 이 문제를 풀면서 오래 걸렸던 부분이 있는데 그림으로 보여드리겠습니다. 바로 가장 위쪽 그리고 왼쪽부터 탐색을 해도 모든 칸을 다 채울 수 있다는 점입니다. 가장 위 열부터 블록을 채워 나가기 때문에 좌표를 기준으로 위로 그려지는 블록은 배제할 수 있습니다. int s.. 2021. 3. 10.

티스토리툴바