내가 그때 이걸 알았더라면

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. 문제 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 ..

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의 합을 출력한다. (= 트리의 지름) 한 노드에..

1. 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다. https://..