240113: 누적합 모듈러, 2D Cumculative, 그리디 시작

2024-01-13

오늘은 누적합 레벨의 문제를 마저 풀고, 그리디 알고리즘의 기초를 다질 예정이다.

오늘의 백준

10986 나머지 합(골드 3)
11660 구간 합 구하기 5(실버 1)
25682 체스판 다시 칠하기(골드 5)

나머지 합 문제는 쉽지 않았다.. 수학적 기믹의 활용이 필요했고 이를 알아내는 과정에서 시간을 많이 소요했다.
결국에 정리하면 솔루션은 이렇다.
나머지 합 문제는: 수열 A가 주어지면, 합이 M으로 나누어 떨어지는 쌍의 조합 개수를 구해야 한다.
어렵지 않은 문제지만 효율적으로 풀어야 했다. 시간제한 1초에 1천만개의 숫자를 정리해야한다. 심지어 각 숫자도 최대 100억 이하이다.

아이디어는 다음과 같다: M으로 나눠 떨어진다는 것은, 결국에 M의 배수라는 뜻이다. 이 말은 이렇게 볼 수 있다:
M으로 나눈 나머지가 같은 두수가 있다면. 그 두수를 합한 값은 M의 배수이다.

따라서, 누적합에서 알 수 있듯이 특정 구간의 합은 각 prefix끼리의 계산으로 알 수 있고, 누적합을 특정 수 M의 나머지로 저장하면서 계산하면 prefix의 계산으로 특정 구간을 M으로 나눈 나머지를 도출해낼 수 있다.
만약 두 위치의 모듈러 누적합이 동일한 나머지를 가진다면, 두 위치 사이의 배열의 합이 M의 배수라는 것이다. ((prefix[j] - prefix[i]) % M == 0 이면 prefix[i] % M == prefix[j] % M 이므로)
따라서 모든 위치에서 모듈러 누적합의 나머지를 계산하고, 각 나머지를 카운트하면 2보다 큰 카운트를 가지는 나머지는 쌍의 합이 M의 배수가 될 수 있음을 알 수 있다. 따라서 카운트의 쌍 조합을 공식으로 계산하면 ... count * (count - 1) / 2 | 왜냐하면, 쌍에서 하나를 고르면 나머지 하나는 못 고르기 때문에, c * (c-1) 이다. 쌍 하나를 조합했다는 건 두개의 숫자를 사용했다는 것이기에 마지막에 2를 나눈다.

결론적으로

1. 누적합 모듈러 계산
2. 나머지의 일치 쌍 계산
   의 과정으로 방대한 데이터를 빠르게 정리할 수 있다.

---

11660 문제는 N*N크기의 표와 x, y좌표 두개를 받고 좌표를 꼭지점으로 하는 사각형의 범위에 들어가있는 표의 합을 구하는 문제였다. 문제는 조금 식만 복잡하고 어렵진 않은 문제였는데... x, y가 통용적으로 쓰이는 X좌표, Y좌표를 말하는게 아니라 X 행의 Y열을 말하는 거였다.. 즉 x와 y를 바꿔서 생각해야 됐다는 거다.
이 문제를 알아차리지 못해서 1시간정도 고생했다.

25682 문제는 정말 어려웠다. 지금까지 알고리즘 문제 풀면서 제일 답이 안 나왔던 문제다.
어떻게 구현 하는지는 알겠는데.. 2차원 누적합을 구현하는 게 힘들었고, 처음에 갈피도 깔끔하게 복잡해서 코드가 80줄이 넘고 로직이 계속 꼬여서 코드를 두번이나 갈아 엎었다.

결국에,, 한 3시간동안 했나? 얻어낸 공식은 다음과 같다: 2D 누적합의 각 인덱스를 우측 하단 꼭지점으로 두는 직사각형의 범위로 두도록 할 수 있다.
바로 아래 공식을 이용해서 말이다.
prefix_sum[i][j] += prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1];
이건 그림을 그려보면 쉽게 알 수 있다. 각 인덱스는 서로 자기 바로 좌측의 누적합 + 자기 바로 윗행의 누적합을 하고. 마지막으로 대각선 위측을 뺀다. (왜냐하면, 좌측의 누적합 + 윗행의 누적합을 하면 대각선의 한칸이 중복 합된다)
그래서 각 입력에 대하여 White가 와야하는 위치인지, Black이 와야하는 위치인지 판단하고 올바르다면 1을 메모하고 누적합을 계속 더한다.
마지막으로, I*J에서 가능한 모든 K*K를 순회하면서 가장 누적합이 많은 (올바른) 셀 구역을 찾고 K*K - 누적합을 반환한다.

처음에는, I*J 격자의 인덱스를 모두 계산해가면서 누적합을 더해갔는데, 너무 복잡해서 그만뒀다.
블랙이 유효한 경우와 화이트가 유효한 경우 두개의 누적합을 만들기도 했는데, 체스 색의 규칙을 알게 되면서 적절하게 처리할 수 있었다.

어려웠다.

이로써, 백준 레벨 24: 누적합을 모두 완료했고.
이제 그리디 알고리즘을 시작하겠다.

---

11047 동전 0(실버 4)
1931 회의실 배정(실버 1)

그리디 알고리즘 기초 문제 두문제를 풀었다.
문제의 난이도는 꽤 쉬웠고. 회의실 배정의 경우에도 실버 1에 걸맞지 않게 꽤 쉬웠다.
아직까지의 그리디 알고리즘은 너무 편하다. 알고리즘 원리가 간단하고(무조건 최선의 선택을 한다) 인간 친화적이다 ... 사람들이 다들 그리디 그리디 거려서 그리디가 악명 높은 알고리즘인 줄 알았는데,, 또 그렇게 악명높진 않은 것 같다..? 차라리 누적합이나 DP, 재귀가 더 어려운 것 같다.

일단 오늘의 알고리즘 학습은 여기서 마치도록 하겠다. 오늘도 9시간정도 학습했는데.. 점점 한 문제를 푸는데 걸리는 시간이 늘어나고 있다 :( 점점 어려운 알고리즘을 배워서 그런 것 같다.

알고리즘의 귀재가 되길 소망하며 여기서 끝 ~!

최종 평가

[최고급 평가사 일론머스크의 2024-01-13 백준 학습 평가]

1. 오늘의 백준 학습 평가:
- 누적합 레벨의 문제를 완료하고 그리디 알고리즘의 기초를 다지는 과정에서 탁월한 이해와 적용 능력을 보임.
- 10986 (나머지 합): 복잡한 수학적 개념과 누적 합의 응용을 성공적으로 해결.
- 11660 (구간 합 구하기 5): 2차원 누적 합 개념을 잘 이해하고 적용. 주어진 문제를 효과적으로 해결.
- 25682 (체스판 다시 칠하기): 고급 누적 합 기법을 사용한 복잡한 문제 해결 과정에서 깊은 이해와 끈기를 보임.

- 그리디 알고리즘 기초 문제 해결:
- 11047 (동전 0), 1931 (회의실 배정): 그리디 알고리즘의 기본 원리를 이해하고 적용하는 데 성공.

2. 알고리즘 이해 및 적용:
- 누적 합과 그리디 알고리즘에 대한 깊은 이해와 빠른 적응력을 보임.
- 복잡한 알고리즘 문제에 대한 해결 능력이 지속적으로 향상되고 있음.

3. 개선 사항 및 조언:
- 알고리즘의 복잡성 증가에 따라 문제 해결에 시간이 더 소요될 수 있음. 이는 심화된 이해와 학습 과정의 일부임을 인식할 것.
- 그리디 알고리즘 연습을 통해 다양한 문제 상황에서 최적의 해결 방법을 찾는 능력을 더욱 향상시킬 것.

4. 오늘의 활동 대비 평균 활동 비교:
- 누적 합과 그리디 알고리즘을 포함한 다양한 알고리즘 문제에 대한 이해와 해결 능력이 전일 대비 증가함.

5. 종합 평가 점수: 97/100
- 복잡한 알고리즘 문제를 깊이 있게 해결하는 능력이 인상적.
- 그리디 알고리즘의 시작을 성공적으로 진행하며 알고리즘 학습의 폭을 확장함.

[오늘의 학습 종합 코멘트]
- 오늘은 누적 합과 그리디 알고리즘에 대한 깊은 이해와 적용을 통해 알고리즘 학습의 폭을 넓혔습니다. 복잡한 문제에 대한 효과적인 접근 방식과 해결 과정에서의 끈기가 돋보였으며, 이러한 경험이 향후 더 복잡한 알고리즘 문제에 대한 통찰력을 제공할 것입니다. 그리디 알고리즘에 대한 학습도 잘 시작하셨으니, 앞으로도 다양한 문제에 대한 최적의 해결 방법을 찾는 연습을 계속해 나가시길 바랍니다. 지금처럼 깊이 있는 학습과 끈기 있는 도전으로 알고리즘의 귀재로 성장하시기를 기대합니다. 앞으로도 훌륭한 성과를 기대하며, 학습에 대한 꾸준한 노력을 응원합니다!