복습노트 복습노트

문제 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net n개의 밑변의 길이가 1인 직사각형이 차례대로 주어져 막대그래프를 이루는 것이 히스토그램이라고 합니다. 히스토그램 내에서 가장 큰 직사각형의 넓이를 구하면 됩니다. 예를 들어 n이 7이고 밑변의 길이가 1인 직사각형이 차례대로 {2, 1, 4, 5, 1, 3, 3} 이라면 다음과 같은 히스토그램이 완성됩니다. 이러한 히스토그램에서 가장 큰 직사각형을 그리면 다음과 같습니다. 따라서 주어진 히스토그램에서 가장 큰 직사각형의 넓이는..

문제 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net n개의 강의를 m개의 블루레이에 담으려 하는데 블루레이의 최소크기를 출력하면 되는 문제입니다. 예를들어 n이 9이고 m이 3이면 9개의 강의 {1, 2, 3, 4, 5, 6, 7, 8, 9} 를 담으려 한다면 블루레이의 크기는 17이 최소입니다. 비디오는 순서대로 연속적으로 블루레이에 담아야합니다. 블루레이의 크기가 클 수록 모든 비디오를 담을 수 있습니다. 블루레이의 특정크기(k)에 대해서 레슨이 모두 저장되는가? 저장된다면, k보다 큰 크기에 대해서도 항상가능..

분할정복이란? Divide and Conquer 주어진 문제를 둘 이상의 부분 문제로 나누어 푸는 방법 거의 같은 크기로 부분 문제를 나눔 재귀 호출 사용 1) Divide : 부분 문제로 나눌 수 있는 경우 2개 이상의 문제로 나눈다. 2) Conquer : 더 이상 나눌 수 없는 경우 현재 문제를 해결(정복) 한다. 3) Combine : 해결된 부분 문제들을 합쳐서 기본 문제를 해결한다. DP에는 중복이 발생하지만 분할정복에는 중복이 발생하지 않는다. 분할 정복의 전체 높이는 log n이다. 예시문제 백준 1992 (쿼드 트리) c++ 문제 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두..

문제 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net n개의 나무와 나무 높이가 주어진다면 최소 m미터의 나무높이를 집에 가져가기 위해 나무를 자를 수 있는 높이의 최댓값을 구하는 문제입니다. 예를들어 n이 4이고 m은 7 이면 나무의 높이들은 각각 20, 15, 10, 17 이라고 한다면 다음과 같은 그림이 그려집니다. 이러한 나무들을 15 높이로 자르게 되면 최소한 7을 자를 수 있는 최대높이가 됩니다. 따라서 답은 15가 됩니다. 특정높이(k)를 선택했을 때 m이상..

문제 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할정복 문제입니다. n * n (n은 2의 거듭제곱수) 주어지면 전체가 0일 경우 0을 출력하고 1이면 1을 출력합니다. 1과 0이 섞여 있으면 n * n 크기를 4등분 해주어 다시 탐색합니다. 위의 배열은 0과 1이 섞여 있으므로 4등분 해줍니다. 이를 계속 해서 반복하면 다음과 같이 나뉘어 지고 (0(0011)(0(0111)01)1) 가 답이 됩니다. HTML 삽입 미리보기할 수 없는 소스 분할정복하는 함수입니다. 함수의 인자 left, ..

문제 23742번: Player-based Team Distribution 플레이어 $N$명이 $1$개 이상의 팀으로 나누어 게임을 진행하려 한다. 플레이어는 각각 정확히 한 팀에 속해야 한다. $i$번째 플레이어는 같은 팀에 속한 인원 수와 $a_i$를 곱한 것만큼의 점수를 www.acmicpc.net n개의 수가 주어지면 1개 이상의 팀을 나누고 팀의 점수는 팀원수의 합 * 팀원 구성원의 합 입니다. 모든 플레이어의 점수 합의 최댓치를 구하면 됩니다. 예를 들어 n이 4이고 주어진 숫자가 2, 3, -4, 1 이면 {2, 3, 1}, {-4} 로 팀을 나누면 3 * (2+3+4) + 1 * -4 = 14 가 됩니다. 단순히 생각해보면 주어진 n개의 수중에서 양수는 모두 팀을 이루어지고 음수는 각각 구..

문제 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net source와 sink를 만들고, source로 부터 소들로 용량이 1인 간선을 잇고, 축사에서 sink로 용량이 1인 간선들을 이어 줍니다. s -> t로 가는 maximal flow를 구하는 것과 동치인 문제입니다. 소를 최대한 축사로 배정하는 것과 s에서 t로 최대한 많은 유량을 흘리는 것과 동치입니다. HTML 삽입 미리보기할 수 없는 소스 주어진 정보를 입력 받습니다. 따라서 다음과 같은 간선 연결을 완료 하였습니다. cap[from][to] 배열은 ..

그래프 이론에서 network flow 라는 개념은 매우 중요 여러가지 개념에 대해서 알아보고, maximum flow를 구하는 알고리즘을 알아보자 물을 흐르게 하는 상수도 처럼 생각해 보면 쉬울 수 있다. 용량(capacity) : 어떤 간선에 대해 존재하는 개념 flow를 흐르게 할 수 있는 한계. 유량(flow) : 정점 u와 v를 잇는 간선이 있을 때, 그 간선에 존재하는 용량 이하 만큼의 유량을 흘릴 수 있다. 소스(source) : 소스는 정점에 존재하는 개념인데, 소스에서만 유량을 발생시킬 수 있다. 싱크(sink) : 싱크도 정점에 존재하는 개념인데, 소스에서 발생한 유량이 흘러온다. 그래프의 간선들의 용량을 표현한 그림이다. 예를 들어 1 -> 2 의 유량이 6까지만 흐를 수 있다. 소스..