1. 알고리즘 문제 해결
구간 나누기(백준 2228):
일정 난이도를 넘어가기 시작하면 주어지는 n이 작을 때가 더 두렵다. 단순하게 로직하나 돌려서 끝나지 않고, 완전탐색이나 다른 탐색류 알고리즘이 더해지는 경우가 많아서다. 이번 문제는 큰 틀이 dp라는 것을 파악하는 데는 어려움이 없었지만, 그래서 결국 복수개의 구간합을 어떻게 dp로 풀어낼 것인지가 아리송했다.
주어진 배열 내에서 하나씩 순회해가며 탐색 중인 인덱스를 기점으로 구간이 0~M개까지 선택되는 경우을 찾아야 하는 것은 분명했다. 여기서 dp라는 틀에 얽매여서, Bottom-Up Approach만 떠올리느라 한참 시간을 보낸 것 같다. 긴 고민 끝에 풀어낸 방법은 오히려 Top-Down Approach를 이용하는 것이었다.
N*M 크기의 2차원 dp 배열을 생성한다. dp[i][j]는 i번째 인덱스까지 j개의 구간으로 만든 최대값을 저장할 것이다. 이 때 dp[i][j]를 구하는 방법은, 크게 두 가지 경우를 고려해서 구할 수 있다.
- dp[i-1][j]를 그대로 사용하는 경우. 이 경우에는 현재 탐색 중인 인덱스를 선택하지 않는 경우이다.
- 기준점을 1~i까지 하나하나 옮겨보면서, 기준점-2까지의 j-1개의 구간 최대값에 [기준점, i]을 더한 것을 사용하는 경우. 당연하게도 매번 max처리를 통해서 dp[i][j]값을 갱신해야한다.
왜 굳이 dp[기준점-2][j-1]를 이용하느냐고 하면, 현재 탐색 중인 인덱스를 포함해서 구간합을 더해줄 것이므로 j-1개의 구간을 이용한 경우를 찾아야하며, 이전 구간을 기준점-2까지로 한정해야 새로 생성되는 구간과 겹치거나 인접하지 않기 때문이다.
이걸 이용하면 재귀를 이용해 Top-Down Approach로 접근할 수 있는데, 재귀를 이용할 것이기 때문에 탈출 조건도 설정해줘야 한다. j가 0인 경우, 즉 구간이 0개라면 당연히 값은 0이므로 0을 리턴하고, i가 0보다 작거나 같은 경우(계산을 편하게 하기위해 입력 배열의 시작 인덱스가 1임) 올바르지 않은 접근이므로, 충분히 큰 음의 값을 리턴해 max처리에서 걸러질 수 있도록 한다.
위의 과정을 통해 dp[N][M]을 찾아내면 답을 얻을 수 있다. 과정 속에서 구간합을 빈번하게 구하고 있는데, 이는 누적합 배열을 통해서 바로바로 구해질 수 있도록 했다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> arr;
vector<int> accSum;
vector<vector<int> > dp;
int sectionSum(int i, int j) {
return accSum[j] - accSum[i-1];
}
int calc(int n, int m) {
if(m == 0) return 0;
if(n <= 0) return -1000000000;
if(dp[n][m] != -1) return dp[n][m];
dp[n][m] = calc(n-1, m);
for(int i=1; i<=n; i++) {
dp[n][m] = max(dp[n][m], calc(i-2, m-1)+sectionSum(i, n));
}
return dp[n][m];
}
int main() {
int n, m;
cin >> n >> m;
arr = vector<int>(n+1, 0);
accSum = vector<int>(n+1, 0);
dp = vector<vector<int> >(n+1, vector<int>(m+1, -1));
for(int i=1; i<=n; i++) {
cin >> arr[i];
accSum[i] = accSum[i-1] + arr[i];
}
cout << calc(n, m);
}
2. 앱개발 숙련 주차 개인과제
RecyclerView의 OnScrollListener에 관해
RecyclerView의 스크롤에 따라 View에 동적인 조작이 필요해서 OnScrollListener를 구현했다. 이를 이용해본 사람이라면 알겠지만 해당 리스너는 onScrolled()와 onScrollStateChanged() 두 메소드를 구현할 수 있게 해두었다.
onScrolled()는 매 스크롤마다 호출되기 때문에 반응성 좋은 동작 구현에는 유리하지만, 무거운 동작이 들어가면 그만큼 앱의 퍼포먼스에 악영향을 줄 수 있다. onScrollStateChanged()는 스크롤의 상태를 끝 부분 도달, 스크롤 중, 스크롤 종료로 나누어서 상태가 변경되면 호출되고, 그래서 이를 이용하면 불필요한 작업을 줄일 수 있다.
내가 구현해야 하는 동작 중 하나는, 하방 스크롤이 발생하면 플로팅 버튼을 노출 시켜야하는 것이었는데, onScrolled()를 이용해 구현하려다가 문득 onScrollStateChanged()를 이용하는게 낫지 않나 하는 생각을 했다.
불확실하지만, 뷰의 노출 상태와 관계된 동작이니 무겁지 않을까 싶었다. 그래서 onScrolled()에서는 스크롤의 방향만 확인하고 onScrollStateChanged()에서 스크롤의 시작 때 확인해 둔 방향을 검증해서 뷰를 노출하도록 했는데 예상대로 동작하지 않았다.
뷰가 아래로 스크롤 되는 시점에 플로팅 버튼이 노출되지 않았고, 스크롤을 멈췄다가 다시 아래로 스크롤하자 그제서야 노출되었다. 그래서 설마 onScrollStateChanged()가 onScrolled()보다 먼저 호출되는건가 싶어 로그를 찍어봤더니 역시나였다.
간단하게 설명하자면 ScrollState: 1이 스크롤 중, 그러니까 스크롤의 시작을 감지하고 onScrollStateChanged()를 호출하는 시점이고, 그 이후에 onScrolled()가 호출되면서 scroll: x 가 잔뜩 불려지는 것을 볼 수 있다.
그럼 어쩔 수 있나, 그냥 onScrolled()에서 처리해야지.. 근데 아마 스크롤로 인해서 뷰의 visibility가 수시로 변경되는 것도 아니고 하방 스크롤시에 계속해서 visibility에 VISIBLE 값이 들어가는건데 크게 문제가 있을까 싶다. 이미 노출해둔 뷰를 또 다시 그리진 않을 거라고 생각하기 때문에.
근데 요구사항이라서 이렇게 구현하긴 했지만, 조금 의아한 점도 있다. 보통 최상단으로 향하는 스크롤 버튼은 스크롤을 올릴 때와 최하단에 도달했을 때 노출되는 것이 합리적이지 않나? 스크롤을 내리는 중이라는 것은 아래 쪽의 아이템을 확인하려는 상태일텐데 그 때 노출하고, 오히려 어떤 유저가 아래에서부터 스크롤을 열심히 올릴 때는 노출하지 않는게 아이러니다(로직 상, 최상단부터 노출되며 어쨌든 하방 스크롤을 통해 플로팅 버튼이 보여지는 상태에서 상방 스크롤이 발생한다고 다시 플로팅 버튼을 숨기진 않으니까, 재현되지는 않을 상황이긴 하다).
마지막 선택 구현 사항만을 남겨두고 있는데, 어떤 식으로 처리할지 고민이 된다. 특정 뷰에서의 상호작용 결과가 다른 뷰의 RecyclerView에 영향을 줘야하는데 정상적인 클린 아키텍처의 앱이었다면 전혀 고민할 부분이 아닌지라.. 이번에도 되도록이면 아직 본 커리큘럼에서 배우지 않은 기술을 사용하는 것을 자제해야 하기 때문에, 몇 가지 방법이 떠오르는데 조금 더 생각해보고 적용해봐야겠다.