전체 글

1. 도입 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있습니다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냅니다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다. 이 차이점은 아래 그림에서 알 수 있습니다. 첫 번째 그림은 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고 두 번째 그림은 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여줍니다. 분할 정..

https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNCSynchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록www.algospot.com  처음에 문제를 읽고나서 풀기가 굉장히 어렵다고 생각되었던 부분이 현재 '12시' 로 맞춰져있는 시계를 다시 변경해서 답을 찾아가야하는지에 대한 부분이었다. 이렇게 이미 '12시'로 맞춰져 있는 시계를 건드리게 되면 답을 얻기 위해 따져봐야하는 경우의 수가 기하급수적으로 증가해버리기 때문이다. 그래서 일단은 ..

https://www.algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이www.algospot.com  문제를 풀려고 고민을 꽤 오래했지만 결국 풀지못하고 답안 코드를 봤다. 알고 스팟에 답안 제출한 코드는 아래와 같다. import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main { public static int[][][] cov..