안녕하세요 :) 소들입니당
알고리즘을 하다가... 이해가 잘 안 됐던 부분이 있었는데
잊지 않기 위해 기록할 겸 포스팅을 씁니다..!
풀려고 했던 문제는 어렵지 않은 문젠데,,,
2167번: 2차원 배열의 합
첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는
www.acmicpc.net
오히려 정답률이 59%....... OTL....
정답률 낮은 문제는 맞고, 높은 문제는 틀리는 이상한 현상이 요즘 발생 중..
그.. 2차원 배열의 합이.. 제가 생각 했던 합과 조금 다른 모양이더라구여??
2차원 배열의 합을 구하기 위해 DP를 이용해서 푸는 문제였어요!!!
따라서 제가 왜 헷갈렸었는지, 또 어떻게 다뤄야 하는지에 대해 알아보려고 해요!
이 포스팅에선 1차원 / 2차원 배열 모두 다뤄보려고 합니당 :)
모든 포스팅은 편의 말투로 합니다!
1. 1차원 배열의 합
1차원 배열의 합은 어렵지 않음
자 다음과 같은 1차원 배열이 있을 때
해당 index까지 배열의 합을 저장하는 dp는 먼저 다음과 같이 생김
0번 index엔 array[0~0] 까지의 합
1번 index엔 array[0~1] 까지의 합
2번 index엔 array[0~2] 까지의 합
.
.
이런 식으로, 1차원 배열일 땐 dp가 아주아주 간단함!!!
따라서 이 dp를 구하는 점화식 또한 매우매우 간단하게
dp[i] = dp[i-1] + array[i]
가 될 수 있음
만약 i가 2라고 해서 dp[2]를 구해야 한다면,
이렇게 dp[2] = dp[1] + array[2]를 한 값이 되는 것 :)
이를 Swift 코드로 짜면,
|
let array = [1, 2, 3, 4, 5]
var dp = array
for i in 1..<dp.count {
dp[i] = dp[i-1] + array[i]
}
|
이렇게 짤 수 있음 :)
굳이 dp 배열 안 만들고 array를 var로 선언해서 해도 됨!!!!
1-1. i ~ j 까지 배열의 합
자, 다음과 같은 배열에서
array[2] ~ array[4]까지 요소의 합을 dp를 이용해서 구하고 싶으면 어떻게 할까?!!
아까 만들어둔 dp 배열을 이용하는 것임 :)
dp[4]는 array[0~4] 까지의 합인데,
우리가 원하는 것은 array[2~4]의 합이기 때문에,
필요없는 array[0~1]의 합 즉, dp[1]의 값을 빼주면 되는 것임
이렇게!!!!
dp[4] - dp[1]을 해주면 우리가 원하는 array[2~4]까지의 합을 구할 수 있음!
따라서 i ~ j (i < j) 까지 배열의 합에 대한 점화식은
array[i~j]까지의 합 = dp[j] - dp[i-1]
이렇게 나타낼 수 있음 :D
1차원 배열은 정말 정말 간단하게 구할 수 있!!다!!
2. 2차원 배열의 합
내가.. 요거를 이해를 못 했어서... 시작된 포스팅이랄까..
처음에 내가 2차원 배열의 합의 점화식을 왜 이해를 못 했냐면
만약 다음과 같은 2차원 배열이 있음
이렇게!!! 그러면 이거에 대한 dp를 난 처음에 어떻게 생각 했냐면 ㅎㅎ;
1차원 배열처럼 모든 값을 더해서 dp를 구했었음
하핫;; 이렇게;; 근데 이렇게 구하는 게 아니래;; ㅎ;;;
2차원 배열에서의 합의 dp는
해당 index(dp[i][j])를 오른쪽 아래 끝점으로 하는 사각형 안에 있는 배열의 합
음 뭔 헛소린지 1도 이해 못했었고요
이게 무슨 말인지 예제로 보자 :)
① dp[1][1]
(1, 1)을 오른쪽 아래 끝점으로 하는 2차원 배열의 사각형은 위와같은 모습임!!!
따라서 dp[1][1]은 array[0~1][0~1]까지의 값을 모두 더한 값 14가 되는 것임!!!
② dp[2][3]
(2, 3)을 오른쪽 아래 끝점으로 하는 2차원 배열의 사각형은 위와같은 모습임!!!
따라서 dp[2][3]은 array[0~2][0~3]까지의 값을 모두 더한 값 78이 되는 것임!!!
.
.
아하! dp[i][j]란,
dp[i][j]를 오른쪽 아래 끝점으로 하는 사각형 안에 있는 배열의 합이란 말에 대해 이해를 했음!!!
그럼 도대체 저 사각형 안에 있는 배열의 합(dp[i][j])는 어떻게 구할까?
그림으로 이해하자 :)
먼저 dp[i][j]를 구하기 위해선이렇게,
dp[i][j-1]의 값과 dp[i-1][j]의 값을 더해주는 것임!!
만약 i,j가 (2,3)이라면, array로 봤을 때 1, 2, 3, 5, 6, 7이란 값이 중복으로 더해졌잖음!?!?
따라서 중복으로 더해진 dp[i-1][j-1]을 빼주는 것임!!!
그리고 마지막으로,
array[i][j] 값을 더해주면 !! dp[i][j] 값 완성 :)
따라서, 이를 점화식으로 나타내면,
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + array[i][j]
가 되는 것임!! 점화식만 보면 호에에에 이게 뭐야 싶지만,
위으ㅣ 그림을 차근차근 이해 했으면 어렵지 않았을 거라 믿음!!!
2차원 배열에서 dp 구하는 Swift 코드는
|
let array = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
var dp:[[Int]] = .init(repeating: .init(repeating: 0, count: array.first!.count + 1), count: array.count + 1)
for i in 1..<dp.count {
for j in 1..<dp[i].count {
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + array[i-1][j-1]
}
}
|
dp는 array보다 size를 각각 1씩 더 줘서 했음!!!
때문에 array에 접근할 때 array[i-1][j-1]이 된 것!!!
위는 코드를 첨부하기 위한 예제로 따로 배열의 Size를 받지 않아서
array를 내가 선언했기 때문에 옵셔널 강제 해제 연산을 쓴 것을 염두에 두길..!
2-1. (i,j) ~ (x,y) 까지 배열의 합
드디어 문제 내용 등장 XD
위 내용을 모두 이해 했다면, 정말 정말 쉬움!!!
이또한 예제로 보겠음!!
우리가 원하는 모양이 이렇게 생겼을 때 (i, j) ~ (x, y)의 합은 어떻게 구하냐면,
dp의 (x, y)는 이미 다음과 같은 사각형 영역이 모두 더해져 있는 거잖음???
이렇게!!! 이제 여기서 원하는 부분을 빼주는 것임
우리가 더하고 싶은 영역이 아닌 사각형 dp[x][j-1]와 dp[i-1][y]를 빼주는 것임!!
근데 이때 중복되어 빼지는 사각형 부분이 발생하기 때문에,
중복되어 빠져버린 부분인 dp[i-1][j-1]를 더해주면 끝임!!!!
따라서 점화식은
array[i][j] ~ array[x][y] 까지의 합 = dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1]
가 되는 것임 :)
.
.
.
지금껏 어려운 문제 풀면서도 한번도 블로그 포스팅한 적 없는데..
이건 진짜 쉬운 문젠데 왜 나만 이해 안가나 멘붕 왔어서..^^
틀린 내용이나 궁금증은 댓글 주세용!
'Algorithm > 문제 풀이' 카테고리의 다른 글
| Swift Algorithm) 기본 셋팅 - Command Line Tool, 예제 입력 받기 (4) | 2020.09.15 |
|---|
