회문(Palindrome)

• 앞뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열을 의미

• 회문 예시: "소주 만 병만 주소", "Madam, I'm Adam", "1234321"

• 회문을 판단하려면?

bool is_palindrome(string s) {
	for (int i = 0; i < s.length(); ++i) {
    	if (s[i] != s[s.length() - i - 1]) {
        		return false;
		}
	}
    return true;
}

def is_palindrome(s):
	for i in range(len(s)):
    	if s[i] != s[len(s) - i - 1];
        	return False
	return True

def is_palindrome(s):
	return s == s[::-1]

올바른 괄호 문자열(VPS = Valid Parenthesis String)

$S$가 입력될 때, $S$가 올바른 괄호 문자열인지 판단하여라.

1. 빈 문자열은 올바른 괄호 문자열이다.

2. $S$가 올바른 괄호 문자열이라면, ($S$)도 올바른 괄호 문자열이다.

3. $S$, $T$가 괄호 문자열이라면, $ST$도 올바른 괄호 문자열이다.

보통 stack을 사용해서 해결
')'가 입력될 때마다, 스택에 있는 '('를 하나씩 지우고 이때 스택이 비어있거나, '('이 없이면 올바른 괄호 문자열이 아님. 모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열이고, 비어있지 않으면 올바르지 않은 괄호 문자열임

정수형 변수 i를 0부터 s의 길이까지 반복:
	만약 s[i]가 '('이라면:
    	stack에 '('를 push
	그렇지 않다면, 만약 s[i]가 ')'이라면:
    	만약 stack이 비어있다면:
        	"NO"를 출력하고, 프로그램 종료
		그렇지 않다면: stack에서 요소를 pop

만약 stack이 비어있다면:
	"YES" 출력
그렇지 않으면:
	"NO" 출력

올바른 괄호 문자열 - 치환

• '('를 1, ')'를 -1로 치환

• 문자열 $S$를 전부 순회하며 합 계산

• 중간에 합이 음수가 되거나, 계산이 모두 끝나고 합이 0이 되지 않으면 올바른 괄호 문자열이 아님

• 마지막에 합이 0이 아닌 것은 스택이 비어있지 않은 것과 같은 의미