6549번 문제: 히스토그램에서 가장 큰 직사각형

히스토그램에서 가장 큰 직사각형을 찾는 방법을 알아보겠습니다.

백준저지의 또다른 재미 중 하나가 숏코딩입니다. 숏코딩이란, 어떤 문제를 되도록 짧은 코드로 푸는 게임입니다. 여기서 '짧은 코드'의 기준은 코드의 글자수(바이트)로 판단하게 됩니다. 따라서 문제를 푸는 능력은 물론 프로그래밍 언어의 특징을 알고 이를 활용하는 능력까지 기를 수 있는 게임입니다. 숏코딩에 유리한 프로그래밍 언어가 따로 있는데, 대표적으로 펄이 가장 널리 쓰이고, 루비, 파이썬등의 스크립트 언어나 sed/awk도 자주 쓰입니다. 또한 숏코딩을 위하여 고안한 언어(Golfscript)도 있으며, (다만, 현재 백준저지에선 지원 안합니다...) 심지어 아희로도 가능합니다(!)

C++11은 C++의 최신버젼입니다.

gcc에서는 -std=c++0x 또는 -std=c++11을 붙여서 사용할 수 있습니다.

g++ -O2 -o Main -std=c++11 Main.cc

배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다.

1. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기
2. i번째 수를 v로 바꾸기. A[i] = v

링크

Rooted Tree에서는 노드의 번호를 다시 매겨서 모든 노드에 대해 노드의 자손을 하나의 구간으로 나타낼 수 있습니다. 이는 노드의 번호를 DFS 방문 순서로 나타내는 것으로 가능합니다. 이제 BIT를 이용한 구간 갱신을 통해 특정 사람의 월급을 바로 계산할 수 있습니다.

Codeforces(코드포스)는 Topcoder와 유사하게 정기적으로 프로그래밍 대회가 열리는 사이트입니다.

최근 들어 Topcoder SRM에 비해 자주 Contest들이 개최되다보니(한 달에 대략 6번 가량의 Contest를 개최한다고 합니다.) 사용자가 꾸준히 증가하여 Division 1의 경우 약 1000명, Division 2의 경우 약 5000명 가량이 매번 참가하고 있습니다. 출제는 Polygon(폴리곤) 이라는 툴을 통해 Codeforces 유저들이 문제를 내고, 충분한 검수 과정을 거치는 것으로 진행됩니다.

Codeforces 메인 페이지에서 최상단, 우측에 Register를 클릭하시면 몇 가지의 정보(E-mail, ID, PW 등등)를 입력하시고 회원가입을 하실 수 있습니다.

Mathjax를 사용하려면, $와 $ 또는 $$와 $$안에 수식을 넣어야 합니다.

$는 inline Math로 문장 사이에 넣을 때, $$는 Display Math로 한 줄을 모두 차지하게 됩니다.

1부터 N까지 합: $\sum_{i=1}^{n} {i^2} = \frac{(2n+1)(n+1)n}{6}$

Java에서 Scanner와 BigInteger를 사용하는 방법입니다.

C/C++은 scanf/print, cin/cout과 같이 특정 자료형으로 입력을 받는 함수가 존재하지만, Java는 문자열 또는 바이트 단위로만 입력받을 수 있습니다. 이 때 사용하는 것이 Scanner 입니다.

Topcoder의 주소는 http://community.topcoder.com/tc 입니다. 아직 가입하지 않은 분은 이 곳에 들어가서 회원 가입을 하고 오세요.

SRM은 Topcoder에서 개최하는 정기적인 프로그래밍 대회입니다. 보통 2주에 한 번씩 열립니다. SRM 일정은 온라인 저지 캘린더나 알고스팟 캘린더, 또는 탑코더 공식 캘린더에서 확인할 수 있습니다. 또한 회원 가입을 한 경우에는 이메일로 다가오는 SRM 알림이 오기도 합니다.