잡다한 소리 하는 블로그

엄청난 시리즈가 존재하는 수열과 쿼리입니다. 이 문제는 세그먼트 트리에 pair을 활용하여 문제를 풀 수 있었습니다. 여기서 세그먼트 트리에 대한 개념이 미리 있어야 합니다. 저는 세그먼트 트리에 관한 글을 쓰기가 두려우므로 백준님이 써두신 좋은 글을 참고해주시면 되겠습니다. https://www.acmicpc.net/blog/view/9 저도 다른 글을 찾다 이 글을 보고 확실히 이해할 수 있었습니다. 다른 글보다 이해하기 편하고, 코드가 명확해 참조하기 편하고 관련된 문제를 함께 풀 수 있습니다. pair에 관한 개념은 간단합니다. pair은 클래스로, 하나의 쌍입니다. 예를 들면 pair가 없는 환경에서 X와 Y 좌표를 저장하고 사용한다면 아래와 같이 사용할 수도 있습니다. int X; int Y;..

괄호 짝 맞추는 문제입니다. 여러 방법이 있지만, 이 풀이에서는 스택을 이용합니다. 괄호의 규칙은 아래와 같습니다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 따라서 괄호는 ( value ), [ value ] 와 같은 형태는 가능하지만, ( value ], [ value ) 와 같은 형태나 서로 매칭되지 괄호가 존재하지 않을 경우일 때 규칙에 위배됩..