1. 다항식의 곱셈 두 다항식의 곱셈은 구현하는 방법이 많이 있지만... 당장은 어려우니 일단 $O(k^{2})$으로 naive하게 구현 해보자. 다항식은 각 항의 계수를 배열에 저장하면 되는데 $f(x) = 2x^{2} + x + 1$이라고 한다면, a = [1,1,2]로 저장하면 된다. 곱셈하고자 하는 다항식이 $g(x) = x + 5$라고 한다면 b = [5,1]이고 두 다항식의 곱셈은 $f(x)g(x) = 2x^{3} + 11x^{2} + 6x + 5$로 [5,6,11,2]가 나와야한다. f(x)가 len(a)-1차수 다항식이고 g(x)가 len(b)-1차수 다항식이면, f(x)g(x)는 len(a)+len(b)-2차수 다항식이다. 위에서 len(a) = 3, len(b) = 2이고 각각 2차 1..
1. 연습문제1 n개의 원소와 q개의 질의가 주어졌을 때 n개의 원소에 대해 각 질의를 수행하는 프로그램을 작성해보세요. 질의의 종류는 다음과 같습니다. 1 a a번째 원소를 출력합니다. 2 a 숫자 a가 있는지를 판단합니다. 만약 있다면 해당 원소가 몇 번째 원소인지를 출력합니다. 숫자 a가 2개 이상 있다면 index가 더 작은 원소를 출력합니다. 만약 a가 없다면 0을 출력합니다. 3 a b a번째 원소부터 b번째 원소까지 순서대로 공백을 사이에 두고 출력합니다. 문제 요구하는대로 구현하면 된다 a번째랑 index가 a인 것은 다르니까 헷갈리지 말고 C++ 특성상 첫 숫자 1,2,3중 하나를 받아 1,2,3인지 체크하고, 1,2면 하나만 더 받고 3이면 2개를 받고 #include using nam..
1. 문제 25214번: 크림 파스타 (acmicpc.net) 25214번: 크림 파스타 각 \(A_i\)가 추가된 직후의 문제의 답 \(N\)개를 공백으로 구분하여 출력한다. www.acmicpc.net 2. 풀이 그냥 단순하게 생각해서 배열 원소의 최댓값과 최솟값을 기억해두고, n개의 원소를 처음부터 순회해서, A[i]가 최대인지 검사하고 최대라면 최댓값을 갱신한다음에, dp[i]에 최댓값 - 최솟값을 넣어주면 되는거 아녀? 새로 들어온 값이 최댓값이 아니라면, dp[i]는 이전에 구한 dp[i-1]과 같을거고 최댓값이 아닌 경우에 당연히 A[i]가 최솟값이 될 자격이 있으니까 A[i]가 최솟값인지 검사하고 A[i]가 최솟값이라면 최솟값을 갱신해준다 여기서 $i \leq j$인 i,j에 대하여 A[j..
1. 배열 값 참조 i번째 원소는 index i-1번에 위치한다. index 0 1 2 3 arr 1 5 2 8 만약 2번 원소 2를 9로 바꾸고 싶다면, 해당 값을 참조해서, 9를 할당하면 된다. arr[2] = 9; 다음은 2번 원소를 단순히 바꾸는 코드 #include using namespace std; int main() { int arr[4]; for (int i = 0; i > arr[i]; } cout arr[i]; } cout 55 4. 배열 초기화 C++에서는 자바와는 다르게 int 배열을 초기화할때, 기본값으로 0이 들어가지 않고 쓰레기값이 들어간다 그래서 모든 값에 0이 들어가게 초기화하고 싶다면,... // 숫자 별 출현 횟수. int count_ar..
1. 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) (acmicpc.net) 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 2. 풀이 투 포인터로는 원소를 포함시키면서 가장 긴 수열을 찾아가는 건데 어떻게 해야 최대 K번 원소를 삭제하면서 가장 긴 짝수만 포함된 연속 부분 수열을 찾을 수 있을까? 생각보다 간단하다 투 포인터 i,j로 범위를 확장해나가는데, j번 원소가 홀수라면, K값을 감소시키고 길이를 증가시키지 않는다. K가 홀수를 포함시킬 수 있는 최대 기회라고 생각한다면, 원소를 실제로 삭제하지 않고도 마치 삭제한..
1. 문제 1부터 n까지 적힌 카드가 아래에서부터 위로 순서대로 쌓여있다. 이제 다음과 같은 질문이 주어진다. x : 카드 뭉치에서 x번이 적힌 카드를 찾아 맨 아래로 내린다. -x : 카드 뭉치에서 x번이 적힌 카드를 찾아 맨 위로 올린다. 예를 들어 n = 5라고 하자. 카드가 [1,2,3,4,5]로 쌓여있다고 표현할 수 있고 [3,-2,1,-4,-5] 순서대로 질문이 주어진다. 3이 주어지면, [1,2,3,4,5]에서 3을 찾아 맨 아래로 내리면 [3,1,2,4,5] -2가 주어지면 [3,1,4,5,2] 1이 주어지면 [1,3,4,5,2] -4가 주어지면 [1,3,5,2,4] -5가 주어지면 [1,3,2,4,5] 최종 상태는 [1,3,2,4,5]가 된다. n개의 카드가 순서대로 쌓여있는 상태에서 q..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
