일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 알고리즘
- 그리디
- 구현
- java
- CS
- 플로이드-와샬
- 백준
- 유니온 파인드
- 프로그래머스
- JUnit 5
- Kotlin
- 문자열
- BFS
- mst
- 백트래킹
- 투 포인터
- 에라토스테네스의 체
- dfs
- 위상정렬
- 이분탐색
- 완전탐색
- 세그먼트 트리
- 스택
- Network
- 후니의 쉽게 쓴 시스코 네트워킹
- 시뮬레이션
- swea
- 동적계획법
- 수학
- Effective Java
반갑습니다!
[백준] 1915 가장 큰 정사각형 본문
풀이
이 문제는 동적 계획법을 사용해야한다. 이 문제의 핵심 아이디어는 위에서부터 탐색하면서 최대 크기의 정사각형을 갱신하는 것이다. 즉 dp[i][j] = (j, i)에서의 최대 정사각형의 길이
가 된다. (수학에서 사용하는 좌표계를 기준으로 x, y 순으로 좌표를 표현했음을 참고할 것)
배열을 board[][]
라고 하겠다.
그러면 board[i][j]
가 1인 곳은 변의 길이가 1인 정사각형이다.
변의 길이가 2인 정사각형은 board[i][j]
, board[i-1][j]
, board[i][j-1]
, board[i-1][j-1]
이 모두 1이어야 한다. 이 문제의 풀이는 여기서 힌트를 얻을 수 있다. 아래의 예시를 보면서 좀 더 알아보자.
(0, 0 ~ 3, 0), (0, 0) ~ (0, 3)은 아무리 큰 정사각형이 나와도 길이가 1이므로 (1, 1)부터 살펴보도록 하자.
(0, 0), (0, 1)이 0이므로 (1, 1) 위치에서 최대로 만들 수 있는 정사각형은 1이 된다.
마찬가지로 (2, 1) 지점도 최대로 만들 수 있는 정사각형이 1이 된다. 나머지 1행은 마찬가지로 최대 크기가 1이다.
이번엔 (2, 2) 지점을 한번 살펴보자.
(1, 1), (1, 2), (2, 1)이 모두 최대 크기가 1인 정사각형이므로 (2, 2) 위치에서는 최대 크기가 2인 정사각형을 만들 수 있다. 따라서 board[2][2] = 2
로 갱신해주면 된다.
이런식으로 모든 곳들을 탐색하다보면 규칙이 나온다. 규칙은 board[i][j] == 1
일 때 board[i][j] = board[i-1][j], board[i][j-1], board[i-1][j-1]의 최솟값 + 1
이 된다는 것을 알 수 있다. 아래의 코드는 (1, 1)부터 탐색을 시작하기 때문에 n
과 m
이 1인 경우에 답을 찾을 수 없어서 별도의 예외처리를 통해 해결해주었다.
코드
C++
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 최고의 집합 (0) | 2020.10.22 |
---|---|
[프로그래머스] 섬 연결하기 (0) | 2020.10.21 |
[백준] 17472 다리 만들기 2 (0) | 2020.10.19 |
[백준] 6497 전력난 (0) | 2020.10.19 |
[백준] 4386 별자리 만들기 (0) | 2020.10.19 |