hhlab.tistory.com

의 해당 단원 밑줄입니다. "분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있습니다. 문제를 비슷한 크기의 더 작은 문제로 분할하는 과정(divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)" "같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예입니다. 여러번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문입니다." ​​ 병합 정렬 (Merge Sort) 수열을 가운데에서 쪼개 두 개의 부분수열로 만들고, 각 부분 수열에 대해서도 같은 절차를 재귀 호출한다. 기저 사례(base case)까지 쪼개 값이 반환되면, ..

algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 �� algospot.com #include #include #include using namespace std; queue answer; const int button[10][5] = { {0, 1, 2, -1, -1}, {3, 7, 9, 11, -1}, {4, 10, 14, 15, -1}, {0, 4, 5, 6, 7}, {6, 7, 8, 10, 12}, {0, 2, 14, 15, -1}, {3, 14, 15, -1, -1}, ..

algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 �� www.algospot.com #include #include #include using namespace std; queue answer; int row, col; int matrix[20][20]; int run() { /* 왼쪽 위 부터 탐색하여 비어있는 칸을 x,y에 저장 * flag 지정하여, 찾는 즉시 반복문 탈출 * x, y가 반복문을 그대로 통과하면 모두 채워졌다는 의미 >> 1을 반환(result에 더해짐) */ int x = -1; int ..

algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com #include #include using namespace std; queue answer; // matrix에 친구 관계, paired에 친구가 있는지 여부 저장 int matrix[10][10]; int paired[10]; int student_num, pair_num; int makePair() { // 짝이 없는 학생이 있다면 idx에 저장하고, 모두 짝이 있다면 1을 반환 int idx = -1; for (int i = 0; i < stu..

의 해당 단원 밑줄입니다. "공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽습니다." "컴퓨터의 최대 장점은 결국 속도가 빠르다는 것이니까요. 특히 현실 세계의 문제 중에는 입력의 크기가 작아 컴퓨터가 처리하기에는 별 것 아니지만, 손으로 직접 풀기에는 경우의 수가 너무 많은 경우가 종종 있는데, 이럴 때 완전탐색(가능한 방법을 전부 만들어 보는 알고리즘)은 충분히 빠르면서도 가장 구현하기 쉬운 대안이 됩니다." "우리가 들여다 보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있습니다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 호출입니다...