부트캠프 20일차 후기

오늘 CodeKata는 간만에 5문제를 풀었다. 5문제 다 어렵지 않았고 문제를 해석하고 해결하는데 별다른 시간이 걸리지 않아서 걸린 성과이다. 하지만 그것과 별개로 이제 슬슬 브루트포스나 그리디 외의 알고리즘이 나오기 시작하는 모양이다. 이 5문제 내에 간단한 dp 문제가 있었으니 점점 더 어려워진다는 징조임이 분명하다. 그래도 5문제 안에 예전에 다른 언어로 풀었던 문제를 더욱 간단한 알고리즘을 활용해서 푼 것을 보면 내 PS 실력이 는 것에 대해 체감이 좀 들었다. 여담으로 이번 CodeKata에서 배운 것은 Char의 isLetter이다. 해당 Char가 알파벳인지 확인해준다. 그것 외에 없다는 것은 안타까운 일이다.

 

간만에 알고리즘을 새로 하나 알게 되었다. Mo's 란 알고리즘으로 오프라인 쿼리와 관련된 알고리즘이다. 이 알고리즘은 업데이트가 없는 구간 쿼리를 처리하는 알고리즘으로 쿼리의 순서를 조정해서 더 효율적으로 쿼리를 처리한다.방식은 어떤 쿼리의 답을 구한 후에 다음 쿼리의 구간을 이번 쿼리의 구간으로 조정하며 일치시켜서 답을 구하는 순서를 거친다. 예를 들어서 [1, 2, 3, 4, 5, 6, 7, 8, 9] 란 배열이 있다고 하자. 그리고 쿼리는 구간 합을 구하며, 인덱스로, (1, 5), (4, 7), (0, 6) 이라 하자.

 

그럼 일단 1에서 5까지의 인덱스의 구간을 구한다. 그럼 2 + 3 + 4 + 5 + 6 의 값인 20이 된다. 이제 (4, 7) 을 구하자 여기서 시작 인덱스인 1이 4로 움직이면 2, 3, 4를 뺀다. 끝 인덱스인 5를 7로 움직이면서 7, 8을 더한다. 그렇게 답이 26이 된다.

이제 (0, 6) 이라 하자 그럼 시작 인덱스인 4를 0으로 움직이며 4, 3, 2, 1을 더하고, 끝 인덱스인 7이 6으로 움직이며 8을 뺀다. 그렇게 28이란 값을 구하게 된다.

 

그럼 이제 쿼리의 정렬 순서가 중요하게 되는데, 보통은 배열의 길이에 루트를 씌운 값을 기준으로 그룹을 나눠서 정렬한다고 한다. 이렇게 하면 시간 복잡도가 N * 루트 N을 가지게 된다. 증명은 "제곱근 분할법"을 참조하도록하자. 여기서 그것까지 적기엔 좀 복잡해질거 같아서 여기서 줄인다.

 

C++ 기준 정렬 함수는 다음과 같다.

// sq는 배열의 길이의 루트 값
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
	int a = p1.first.first / sq, b = p2.first.first / sq;
	if (a == b) return p1.first.second < p2.first.second;
	return a < b;
}

 

그리고 Step3를 구현하는데에 성공했다. QueryDSL은 사용하진 않고, 단순 JPQL을 사용을 해서 구현을 하였다. 구현을 하며 가장 기억에 남는 오류는 "Required request body is missing"이다. 이 오류는 RequestBody에 JSON을 넘기지 않았을 때 발생되는 오류라 하는데, 분명 나는 Swagger로 JSON을 넘겼을 터인데, 전달이 되지 않았다는 수수께끼는 납득이 되지 않았다. 그런데, 문득, 이 오류의 다른 발생조건이 눈에 걸렸다. 그것은 Method를 제대로 사용하지 않았을 경우이다. 그래서 가설을 하나 세웠는데, "Get 메소드에서 RequestBody를 사용하면 안되는 건가?" 란 가설을 세우고 검색을 한 결과, GET 메소드는 RequestBody를 쓰면 안된다는 정보를 얻었다. 결국 @RequestBody를 지우고, 단순 파라미터로 전달하고 나서야 통과가 되었다.

 

이제 크리스마스를 껴서 3일 연휴이다. 푹 쉬고, 다음 주 화요일 부터 Step4를 구현해보도록 하자. 근데 몇몇 요구사항이 애매한 것 같아서 튜터님께 추가적으로 질문을 해봐야겠다.