https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net '('을 1, ')'을 -1이라 가정한다. 만약 어떤 구간 [l,r]이 올바른 괄호 문자열이 아니라면 ')'가 '('보다 많아지는 순간이 있을 것이다. 이를 누적합으로 표현해보면 l부터 누적으로 더하다가 0보다 작아지는 경우와 ')'가 '('보다 많아지는 경우은 동치이다. 따라서 구간의 누적합을 구하고, 누적합들의 최솟값이 0보다 작아지는 경우가 있는지 검사해보는 식으로 바꿀 수 있다..
https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 이 문제는 언뜻 보면 어려워 보이는데, 사실 \((2000/2)^{2} = 10^{6}\) 임을 알면 왼쪽에 1000개, 오른쪽에 1000개에 적당한 약의 개수를 넣으면 \(10^6\) 개를 만들 수 있을 것 같다. 어떤 약의 수 X만큼을 주기 위해 X를 1000으로 나눈 몫과 나머지에 대한 식을 세워보자. $$X = 1000*b + r$$ 왼쪽엔 1000짜리 1000개, 오른쪽에는 1짜리 1000개를 넣으면, 원하는 수 만큼의 약을 담을 수 있다. #include using nam..
https://www.acmicpc.net/problem/17958 17958번: Cycle String? In the first example, substrings of the restored string are: “abbab”, “bbabc”, “babcb”, “abcbc”, “bcbcc”, “cbccb”, “bccba”, “ccbab”, “cbabb”, “babba”. Note that the first example does not contain repetitions, however www.acmicpc.net 일단 \(NO\)가 되는 조건을 알아보자. 1. 등장하는 문자가 1개인 경우 ex)\(aa...a\) 2. 등장하는 문자가 2개고, 한 문자가 \(2N-2\)개 이상인 경우 ex) \(aa..
- Total
- Today
- Yesterday
- 하이퍼
- 정렬
- 김춘배
- hyper
- 스택
- 앳코더
- gunwookim
- 냄새 싫어
- 쿼리
- combination
- 누적 합
- 비요뜨 존맛
- ABC
- 오일러 경로
- 알고리즘 문제 풀이
- 1909
- 비요뜨
- 간단한 풀이
- Offline Dynamic Connectivity
- DP
- PS
- codeforces
- 수열과 쿼리
- BOJ
- 세그먼트 트리
- Rabin-Karp
- Constructive
- AtCoder
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |