[백준 2042] 구간 합 구하기 : https://www.acmicpc.net/problem/2042 문제 조건 정리 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 둘..

[백준] 6549 : 히스토그램에서 가장 큰 직사각형 : https://www.acmicpc.net/problem/6549문제 조건 정리 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 아래 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.입력 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 ..

[백준] 15683 : 감시 : https://www.acmicpc.net/problem/15683문제 조건 정리 1. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다.사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. 2. CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.3. 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)둘째 줄부터 N개의 줄에는 사..

[백준 1520] 내리막 길 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 조건 정리 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 출발 : 최상단 좌측 도착 : 최하단 우측 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 입력 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 ..

[백준 22968] 균형 : https://www.acmicpc.net/problem/22968 22968번: 균형 이진 탐색 트리의 한 종류인 AVL Tree는 "높이 균형 성질"이라는 성질을 이용해 트리의 균형을 맞춘다. 또한, 높이 균형 성질을 만족하는 이진 탐색 트리는 전부 AVL Tree이다. 트리 $T$의 모든 내부 www.acmicpc.net 문제 조건 정리 양의 정수 V 가 주어지면, 최대 V 개의 정점을 사용해서 만들 수 있는 AVL Tree의 최대 높이를 출력하는 프로그램을 작성하자. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐 정점의 개수 V가 한 줄에 하나씩 주어진다. 문제를 풀기 전 그림을 그려보며 규칙을 쉽게 찾았음! 트리의 최대 높이 필..

[백준 1504] 특정한 최단 경로 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 조건 정리 방향성이 없는 그래프가 주어진다. -> 양방향으로 입력받기 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 임의로 주어진 두 정점은 반드시 통과해야 한다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 그러한 경로가 없을 때에는 -1을 출력한다..