🎆

시간을 줄일 수 있는 방법중 하나로 설명되는 전처리이다.전처리라는 단어의 의미와 같이 입력받은 데이터에 대해 선제적으로 처리하여 완전탐색을 피할 수 있도록 하는 방법이다. 문제 1) 괄호 쌍 만들어주기단순 모든 경우의 수를 탐색하면 모든 인덱스를 탐색하면서 여는 괄호가 두개인 시작점을 찾고, 닫는 괄호가 두개인 끝 점을 전부 찾아서 해야된다. 이는 (((()))), (())(())와 같은 경우가 최악의 경우로 생각할 수 있는데, ((을 잡고 ))을 찾기위해 모든 인덱스를 탐색하는 과정에서 시간복잡도는 O(N^2)가 나오게 된다. sol1) 누적합 응용 전처리누적합의 대상을 특정 인덱스 오른쪽의 ))의 개수로 한다. ( ( ) ) ( ( ) ) ( ( ) ) 와 같은 예시가 있다고 하자.인덱스의 역순으로 ..

기본 개념1차 수직선 상에 n개의 선분이 주어졌을 때, x = k 직선과 만나는 서로 다른 선분의 수는 몇 개인지를 판단하는 프로그램을 작성해보세요.단, 주어지는 x 좌표는 모두 다름을 가정해도 좋습니다. 문제를 가시적으로 나타내면 2개라는 것을 쉽게 알 수 있다. 이 가시성을 컴퓨터 알고리즘으로 쉽게 나타내기 위해서는 다음과 같이 시작점에 +1, 끝 점에 -1을 하는 방법이 있다.K를 기준으로 그보다 왼쪽에 있는 점들을 생각하여 만약 끝 점이 k보다 작다면 k와 겹치지 않으므로 시작점의 값 +1 + 끝점의 값 -1을 하므로 0이된다.K를 기준으로 그보다 시작점이 오른쪽에 있는 점 또한 마찬가지이며 만약 겹치는 점이 생길 경우 시작점이 +1이므로 겹치는 구간 +1를 할 수 있다.이렇게 된다면 특정한 구간..