알고리즘 공부 일기

2022.10.05 푸념

  백준 누적합 16139번을 푸는 중이다. 역시 약간의 응용을 하니 턱하니 막혔다. 일단 풀고 보니 누적합을 배우기 전에 각각의 케이스마다 연산하는 O(MN)알고리즘을 그대로 사용하고 있었다.

  근데 이건 매번 다른 알파벳이 나올 수가 있는데 어떻게 부분합으로 하지? 하는 생각이 들었다. 아 그럼 a~z까지 모든 알파벳에 대해서 부분합을 구하나? '설마 ㅋㅋ 이렇게 하겠어? 이게 훨씬 오래 걸릴거 같은데'라고 생각했다. 근데 이런 생각을 하지 말걸 그랬다. 그냥 해볼걸 그랬다.

  도무지 생각이 안나서 해답을 검색해 보았는데,각 알파벳마다 누적합을 구하는 식으로 구했다. 물론 이 사람은 단어에 있는 알파벳만 구한것이다. 만약에 내가 저 멍청하다고 생각한 아이디어를 구현해보고 개선했다면 저런식이 될 확률이 높지 않았을까? 앞으로는 좀 실행을 해보도록 해야겠다.