www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net deque temp; 에 구간의 (값, 인덱스)를 저장한다 그리고 구간을 돌면서 구간 밖의 인덱스 인것들은 temp에서 제거하고, 또한 이제 들어오는 수 보다 크거나 같은 수들은 temp에서 제거한다 즉 이제 들어오는 수로 인해 앞으로 최솟값이 될 수 없는 수들을 제거하는 것이다. 그리고 이제 들어오는 수를 넣는다. 그러면 temp의 가장 앞에 있는 수는 구간의 최솟값이 된다는 ..

www.acmicpc.net/problem/2733 2733번: Brainf*ck 첫째 줄에 프로그램의 개수 T(1 ≤ T ≤ 100)가 주어진다. 각 프로그램은 한줄 또는 그 이상으로 구성되어 있으며, end만 적혀있는 줄로 끝난다. 프로그램에 올바르지 않은 문자 (+-.[])가 있다면, 이 www.acmicpc.net 주어진 문자에 따라 값을 수행한다. 주의해야 될 점은 [ , ]를 만났을 때인데, 이를 위해 미리 서로 짝의 정보를 left_right와 right_left에 저장해 놓아서 문제를 해결했다. 코드 #include #include #include #include #include #include #include using namespace std; int t; string info; vec..

www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 시작점이 더 작은 숫자인 버스는 bus1에 저장하고, 시작점이 더 큰 숫자인 버스는 bus2에 저장하였다. 그리고 bus1, bus2를 시작점이 작은 게 앞에 오고, 시작점이 같다면 도착점이 큰 게 앞에 오도록 정렬을 했다. 주의해야 될 점은 bus2는 도착지점에 n을 더한 것을 만든 뒤 그것을 앞에서 말한 형식에 맞춰 정렬했다. 그리고, bus1에 의해 사라지는 bu..

www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net map을 이용한 슬라이딩 윈도우를 이용해 문제를 해결했다. #include #include #include #include #include using namespace std; int n, m; vector ad(1000001); map see; //(빛의 세기, 개수) map::iterator it; vector result; int main() { cin.tie(NULL); ios_b..

www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net c에 더해지는 값은 해당 수가 들어가는 트리의 깊이이다. map tree에 (번호와, 트리에서 깊이)를 저장하여 upper_bound를 통해 현재 트리의 정보 중 입력받은 수 보다 큰 것 중 가장 작은 것을 찾고, 이를 통해 해당 수가 들어갈 트리의 깊이를 구한다. 코드 #include #include #include #include #include using namespace std; int n; lon..

www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 각각의 위치에서 물을 넣었을 때 그때의 결과를 확인한다, Solve(pair start) 함수를 통해 start위치에 물을 넣을 때 상황을 확인했는데, 이때 물이 바깥으로 넘치면 안 되며, 물을 넣는 곳의 높이 이하의 위치로만 물이 흐를 수 있다. 그리고 그렇게 흐른 위치들을 checked에 저장하고, checked의 테두리의 가장 낮은 높이를 구해서 각 칸에 채워지는 물을 구한다. 주의..