일단 씻고 나가자

`마나커 알고리즘` 이란문자열 내의 회문을 빠른 속도로 판별해주는 알고리즘이다. 문자열의 개별 문자에서 양쪽 방향으로 전체 탐색을 하는 방법이 아닌,기존에 탐색했던 값을 저장하여 활용하는 dp 성격을 띄는 알고리즘이다.    원리먼저 알고리즘을 설명하기 앞서 회문의 성격에 대해 생각해보자.  회문의 성질은 다음과 같다.중간 문자를 기준하여, 같은 거리만큼 떨어진 문자는 같다.회문 내부에 회문이 존재할 수 있다.하나의 글자도 회문이 된다. 회문 검사를 더 빠른 방식으로 하기 위해선아무래도 2번 조건인 회문 내부의 회문을 검사하여 응용하는 방식이 유용해 보인다.  이때 주의해야 할 것이,보통 회문 내부의 회문이라면, 아래 예시처럼 특정 포인트를 기점으로 두 개의 같은 회문이 반복되는 케이스만을 생각하게 된다..

`누적합/구간합 알고리즘` 이란 배열에서 특정 구간의 합을 한 번의 계산으로 처리할 수 있는 기법이다. 배열이 주어지고, n만큼 연속된 구간의 합을 m번 질문한다면,일반적으론 for(0 ~ n) * m 의 방식을 활용하여 n * m 의 속도가 나오지만,누적합을 활용하면 매 질문당 한 번의 연산으로 m의 속도만이 필요하다. 일반적인 일차원 배열에서의 활용법,이차원 배열에까지 확장한 활용법과,누적합 활용을 위한 배열 세팅 방법까지 알아보자.    원리 다음 도형에서 색칠된 칸의 개수는 몇 개인가?      V  V  V  V     손으로 세어서 4칸이다.   그런데 만약 이런 푯말이 있다고 가정하자.    처음부터여기까지4칸   처음부터여기까지8칸       V  V  V  V     이 상황에서도 손으로..