내가 그때 이걸 알았더라면

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 양의 정수 n(1 ≤ n ≤ 100,000)과 n개의 원소로 이루어진 수열 An이 주어진다. 이때, An에서 가장 큰 구간합을 구하여라. 2. 해결 방법 1. Brute Force 먼저 가장 간단한 방법은, Brute Force 방식으로 크기 n의 int 배열을 만들어 i번째 자리에서 1~i-1번째 자리부터에서의 합을 구해 O(n^2)(1~i에서 O(n), 이를 1번째부터 i-1까지 반복하므로 O..

1. 문제 https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 집합 A에는 속하지만, B에는 속하지 않는 원소들의 개수와 원소들을 모두 출력하는 문제이다. 집합에서 A - B (차집합)의 개념이 등장한다. 2. 풀이 방법 배열이나 리스트 등을 사용하면 해당 자료형 안에 특정 원소가 있는지 확인하려면 O(1)의 시간이 걸리기에, 접근하는데 시간이 O(1)이 걸리는 맵 자료형을 이용하여 문제를 해결했다. 먼저 A와 ..

1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 길이가 n일 수열이 주어질 때, 이 수열에서 가장 긴 증가하는 부분 수열의 길이(연속일 필요는 없지만 증가해야 함)를 구하면 되는 문제이다. 2. 풀이 방법 LIS 문제의 해결법은 이 블로그에 잘 나와 있다. https://seungkwan.tistory.com/8 가장 긴 증가하는 부분 수열 (Longest..

1. 문제 https://www.acmicpc.net/problem/19566 19566번: 수열의 구간 평균 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어진다. 구간에 있는 모든 수들의 평균이 정확히 $K$인 구간의 개수를 구해 보자. www.acmicpc.net 길이가 n인 수열이 주어질 때, 이 수열에서 평균이 k인 구간의 개수를 구하면 되는 문제이다. 2. 해결 방법 1. 먼저 평균의 의미를 다시 생각해보자. 평균 = 원소들의 합 / 원소들의 개수이다. 양변에 원소들의 개수를 곱하면, 다음과 같이 쓸 수 있다. 구간합 = 평균 * 구간길이 이다. 즉, 구간합을 원소들의 개수로 나눠 이를 평균과 비교할 것이 아니라, 구간합이 구간길이 * 평균과 같은지만 비교해주면 된다는 것..

- 목차 1. 설명 2. 문제 리스트 3. 각 문제 풀이 및 개선할 점, 코드 1. 설명 22-10-30 21:00:00~ 23:00:00 2시간동안 진행한 모의대회 2 관련 풀이 정리 https://www.acmicpc.net/group/practice/view/15679/17 로그인 www.acmicpc.net 2. 문제 리스트 A - 제곱수의 합 (solved) https://www.acmicpc.net/problem/1699 B - 골드바흐의 추측 (solved) https://www.acmicpc.net/problem/6588 C - 기상청 인턴 신현수 (solved) https://www.acmicpc.net/problem/2435 D - 수열의 구간 평균 https://www.acmicpc...

1. 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제에서는 밭의 가로, 세로 크기와 심어진 배추의 개수, 각 배추의 위치가 주어진다. 이때 배추들을 건강하게 키우기 위한 최소 배추흰지렁이 개수를 구하면 되는 문제이다. 2. 해결 아이디어 dfs, bfs 등을 이용하여 쉽게 해결할 수 있는 문제이다. 다만 이번 문제를 해결하면서 작은 문제를 마주쳐 그것에 대해 기록하려고 글을 쓴다... 3. 개선할 점 코드에서 전역으로 밭(field), visit..

1. 문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicp..

1. 문제 문제 어떤 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는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 ..

1. 문제 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다. 우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다. A=000 B=111 C=010 D=110 E=001 두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다. 우리는 이진 코드들에..

1. 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 2. 해결 아이디어 1) 각 노드마다 갈 수 있는 최대 cost를 2개까지 저장한 뒤(재귀 방식이라 시간 복잡도 O(n)), 모든 노드의 최대 cost값 2개의 합을 비교하면서 가장 큰 최대 cost의 합을 출력한다. (= 트리의 지름) 한 노드에..