복습노트 복습노트

문제 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 처음에 문제를 이해하지 못해 함참을 고민한 문제입니다. 광고판의 길이 L이 주어지면 광고판에는 어떤 광고가 무한히 반복적으로 나타납니다. 그때 광고판에 표시된 문자열에서 최소길이의 광고의 길이를 구하는 문제입니다. 예를 들어 광고판 L의 길이가 5이고 주어진 문자열이 babba라면 여기서 연속적으로 광고가 될 수 있는 문자열의 최소길이를 구하는 것입니다. babba (bab가 연속적으로 나타나기 때문에 광고가 가능한 최소 문자열의 길이는 3입니다. 다른 예시로 광고판 L의 ..

문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문자열이 주어지면 다음에 입력받은 문자열이 첫번째로 주어진 문자열에 있는지 구하는 문제입니다. 문자열 매칭 알고리즘인 KMP 알고리즘을 활용하였습니다. 먼저 fail 함수를 만드는 코드입니다. HTML 삽입 미리보기할 수 없는 소스 전체 문자열이 s이고 우리가 찾고자 하는 패턴 문자열이 t 입니다. 문제에서 공백도 포함해서 문자열을 입력받으므로 C++ 문법인 getline 함수로 입력을 받아주었습니다. 4번째 줄을 보면 변수 i와 j가 함께 있습니다...

문제 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보다 큰 크기에 대해서도 항상가능..

문제 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] 배열은 ..