문제 링크 http://icpc.me/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 스택과 분할 정복을 이용하여 풀 수 있다. 스택을 이용한 풀이는 O(N)에 풀 수 있지만 아이디어를 떠올리기 힘들고, 분할 정복은 O(NlogN)에 풀 수 있지만 세그먼트 트리를 알아야 한다. 분할 정복 구간 [l, r]에서 가장 큰 직사각형의 넓이는 (가장 작은 기둥 높이) * (r - l + 1) 그렇기 때문에 가장 작은 기둥 왼쪽, 가장 작은 기둥 ..

문제 링크 http://icpc.me/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 스택을 이용하여 풀 수 있다. 이 문제는 i번째 사람이 1 ~ i -1번째 사람 중에서 몇 명을 볼 수 있는지 확인하면 된다. 여기서 잘 관찰을 해보자면 i번째 사람이 볼 수 있는 사람은 자기보다 큰 사람에 막히지 않은 사람들이다. 그렇다면 사람들을 자기보다 큰 사람이 앞에 있어 볼 수 없는 사람과 볼 수 있는 가능성이 있는 사람들로 나눌 수 있다. 그럼 이제 가능성이 있는 사람들만 가지..

문제 링크 http://icpc.me/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이 백트래킹과 스택을 이용하여 풀 수 있다. 우선 여는 괄호와 닫는 괄호의 짝을 찾아 이것을 인덱스로 가지고 있어야 한다. 이 짝을 찾기 위해서 스택을 이용한다. )를 만날 때 까지 스택에 모두 push하다가 ) 를 만날때 ( 를 만날 때까지 pop을 하고 처음 만난 (가 )의 짝이다. 위에 구해둔 괄호 쌍을 이용하여 백트래킹을 한다. 백트래킹을 해도 괄호가 최대 10개이기 때문에 ..

문제 링크 http://icpc.me/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 풀이 스택을 이용하여 풀이할 수 있다. 문자열을 처음부터 읽으면서 아무것도 만나지 않았을 때는 stack에 담다가