알고리즘/algospot (8) 썸네일형 리스트형 [C++]algospot FENCE 문제 링크 : https://www.algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 www.algospot.com 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. .. [C++]algospot QUADTREE 문제 링크 : https://www.algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 www.algospot.com 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드.. 분할 정복 분할 정복이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 부분 문제에 대한 답을 재귀 호출을 이용(basecase : 상수 크기의 부문제들)해 계산하고, 그 답으로 부터 전체 문제의 답을 계산 일반적 재귀 호출과의 차이점 ? 문제를 나누는 크기 ! 재귀 호출은 문제를 한 조각과 나머지 전체로 나누지만, 분할 정복은 거의 같은 크기의 부분 문제로 나눔 예제 1) 분할 정복을 이용한 수열의 합 구하기 fastSum(n) = 1+2+3+...+n = (1+2+3+..+n/2) + ((n/2+1)+...+n) = (1+2+3+..+n/2) + (n/2+1) + (n/2+2) + ... + (n/2 + n/2) = (1+2+3+..+n/2) + n/2 * n/2 + (1+2+...+n/2) = fast.. 동적 계획법(Dynamic Programming) 동적 계획법은 중복되는 부분 문제의 값(계산 결과)을 메모리(cache)에 저장해 재활용하는 방법 메모리제이션 구현 패턴 int cache[2500][2500]; int someObscureFunction(int a, int b) { // basecase if (...) return ...; // cache에 저장된 값이 있으면 바로 리턴(cache는 -1로 초기화되어있음) int& ret = cache[a][b]; if (ret != -1) return ret; // 답 계산 ... return ret; } 기저사례 가장 먼저 처리 cache배열 초기화(memset 함수 사용 가능) cache배열에 대한 참조형 변수 ret 사용 - ret가 바뀌면 cache배열도 바뀜 → cache가 다차원 배열일 때.. [C++]algospot CLOCKSYNC 링크 : https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 .. [C++]algospot BOARDCOVER 링크 : https://www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 www.algospot.com 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방.. [C++]algospot PICNIC 링크 : https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 .. [C++]algospot BOGGLE 문제 링크 : https://www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 www.algospot.com 작년에 이 문제를 풀어봤었지만, 시간 초과로 해결하지 못했었다. 당시 완전 탐색으로만 문제를 해결하려 했었는데, 이번에는 여기에 메모리제이션을 적용해 시간을 줄여보았고 결과적으로 4ms의 시간으로 문제를 해결할 수 있었다. 문제를 풀면서 까다로웠던 점은, 다음 문자가 될 수 있는 칸은 상하좌우/대각선으로 8개의 칸이 있는데, 이중에서.. 이전 1 다음
