난이도 : 골드 5 걸린 시간 : 1시간 20분 문제 가장 큰 정사각형 문제 바로가기 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 풀이 작은 문제 : 현재 위치에서 오른쪽과 아래 방향으로 가질 수 있는 정사각형의 최대 크기 재귀식 해당 위치에서 나타날 수 있는 최대 크기 정사각형의 한 변을 Area(row, col)이라고 한다면 Area(row, col) = min(Area(row+1,col)+1, Area(row,col+1)+1, Area(row+1,col+1)+1) 조건 벽에 붙어있으면 Area가 1 값이 ..

난이도 : 골드 3 걸린 시간 : 20분 문제 욕심쟁이 판다 문제 바로가기 문제 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 ..

문제 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 풀이 만약 완전탐색으로 하고자 했다면? 반복을 index 0부터 n-1까지 돌면서 해당 집에서 시작해서 나타나는 최대의 money를 구할 수 있음 하지만 index 2를 고른다면, 집의 개수..

🍑동적 프로그래밍 동적 프로그래밍은 Dynamic Programming 즉, DP라고 불리는 알고리즘 기법이다. 복잡한 문제를 점화식으로 만들어 분할 정복할 때, 반복문 또는 재귀를 사용할 수 있는데 이 과정에서 계산의 결과 값을 저장해두어 중복되는 계산을 하지 않도록 만들어준다. 이는 점화식 이렇게 결과 값을 저장해두는 것을 메모이제이션이라고 하는데, 보통 배열의 형태로 수행된다. DP 과정 전체 문제를 부분 문제로 단순화한다. 1번의 과정에서 점화식을 도출한다. 점화식을 이용하여 배열로 간단히 해결할 수 있는지 생각한다. bottom-up top-down 없다면 재귀함수를 만들고 메모이제이션한다. 메모이제이션 방식은 보통 배열이다. 전체 문제를 해결한다. 대표 문제 피보나치 수열 구하기 피보나치 수열..

Quantization https://www.algospot.com/judge/problem/read/QUANTIZE 나의 답 알고리즘 수열을 정렬한다. 부분 수열들의 경우의 수를 돌면서 부분 수열의 오차합이 가장 적은 수열을 구한다. 2번 과정에 대해서 최적부분구조임을 발견하고 각 부분 수열의 오차합을 메모이제이션하는 방식으로 진행하여야한다. 하지만 본인은 메모이제이션을 부분 수열을 모두 완성했을 때 진행하는 식으로 하여 어쨌든 부분 수열을 만드는 재귀함수의 끝에 도달해야 메모이제이션을 쓸 수 있게 구현하였다. 이 점이 시간초과의 원인이 되었다고 생각한다. 코드 코드1 #include #include using namespace std; int N, S; int arr[100]; int* num_idx..

PI https://www.algospot.com/judge/problem/read/PI 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다. 이 때, 각 조각들의 난이도는 다음과 같이 정해집니다: 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2 두 개의 숫..

https://www.algospot.com/judge/problem/read/LIS 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라. 어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다. 입력 입력의 첫 줄에는 테스트 케이스의 수 C..

https://www.algospot.com/judge/problem/read/TRIANGLEPATH 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테스트 케이스의 수 C(C > C; while (C--) { cin >> n; int index = 0; for (int i = 0; i ..