백준 1915 - 가장 큰 정사각형
www.acmicpc.net/problem/1915 2차원 배열에서 가장 큰 정사각형을 찾는 문제이다. 이 문제는 현재 위치에 정사각형이 존재할 경우(값이 1일 경우) 왼쪽, 위쪽, 왼쪽 위에 있는 원소의 최솟값을 더해 현재 인덱스까지의 가장 큰 정사각형의 길이를 저장할 수 있다. 예제를 통해 알아보자. 인덱스 (0, 0)처럼 왼쪽, 위쪽, 왼쪽 위의 원소를 볼 수 없거나 그 값이 0인 경우는 넘어간다. 인덱스 (1, 1)에서 왼쪽, 위쪽, 왼쪽 위를 살펴보면 위쪽의 값은 1이지만 그 외 값들은 전부 0이다. 세 원소의 최솟값이 0이므로 해당 인덱스까지 계산했을 때 정사각형의 최대 길이는 역시 1 + 0 = 1이다. 마찬가지로 인덱스 (1, 2), (1, 3), (2, 1)까지 계산했을 때 최대 정사각형..
백준 1080 - 행렬
www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 한번 연산하면 3X3 부분행렬의 숫자가 0이면 1, 1이면 0으로 바뀐다고 할 때 필요한 연산의 최솟값을 구하는 문제이다. 3X3 부분행렬만 연산이 가능하므로 행렬의 전체 인덱스를 벗어나서 연산하는 일이 없도록 해야한다. 부분행렬 연산은 현재 인덱스 (i, j)에 대해 다음 범위로 계산한다고 하자. i, j i, j + 1 i, j + 2 i + 1, j i + 1, j + 1 i + 1, j + 2 i + 2, j i + ..
