문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,0..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 예제 입력 1 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 1 1 0 0 1 풀이 이진 탐색과 퀵정렬을 이용해서 풀었다. 둘의 ..

문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을 출력한다. 소수점 이하 ..

순서대로 나열되어 있는 배열이 있습니다. 이 배열에서 target 값을 찾으려 하는데, 배열 요소가 100만개라 모두 비교하면 시간이 많이 걸립니다. 이때 더 빠르게 target 값을 찾을 순 없을까요? 이 필요성을 채워주는 것이 이분 탐색 알고리즘입니다. 📌 이분 탐색 정의 이분 탐색은 정렬된 배열을 1/2씩 줄여서 타겟 값을 찾아나가는 알고리즘입니다. 이분 탐색의 프로세스는 다음과 같습니다. (1) 배열의 중간 값을 찾는다. (2) target 값과 중간 값을 비교하여 (low, same, high)큰지, 작은지, 같은지를 판단한다. (3) target이 작다면 중간 값 이전의 배열을, 크다면 중간 값 이후의 배열을 대상으로 다시 이분 탐색을 진행한다. (4) 만약 같다면, 중간 값이 바로 targe..

행렬의 영공간에 대해 알아보는 포스팅입니다. 행렬은 어느정도 이해가지만, 영공간은 대체 무슨 말인지 모르겠습니다. 영공간을 이해하기 위해선 먼저 부분 공간에 대한 복습이 이뤄져야 합니다. 📌 부분공간과 조건 Subspace S가 R^n의 부분 공간이라고 생각하겠습니다. 그렇다면 S가 정말 유효한 부분공간이기 위해서는 다음 3개의 조건을 만족해야 합니다. (1) 영벡터를 포함한다. (2) 벡터 v1, v2가 S에 포함된다면, v1+v2도 S에 포함된다. (3) 벡터 v1이 S에 포함된다면, cv1도 S에 포함된다. 이 조건을 잘 기억해두고 다음 단계로 넘어가시길 바랍니다. 📌 유효한 부분공간인가? m행 n열인 행렬 A를 정의해보겠습니다. 그리고 곧바로 동차 방정식을 1개 세웠습니다. 행렬 A와 벡터 x를 ..

행렬과 벡터를 곱하면 어떻게 될까요? 오늘은 행렬 벡터의 곱에 대해 다뤄보도록 하겠습니다. 📌 행렬 A와 벡터 x의 곱셈 행렬과 벡터는 서로 곱할 수 있습니다. 하지만 어떻게 곱해지는지 잘 살펴야 제대로 활용할 수 있습니다. 결론부터 말하자면, 행렬 A(m*n)와 벡터 x(n*1)을 곱하면 벡터 b(m*1)이 나옵니다. 벡터 b의 첫 번째 열인 b1은 (a11*x1 + a12*x2 +.... + a1m*xn)과 같습니다. 밑의 예시를 보면 더 확실하게 이해할 수 있습니다. 즉, 행렬과 벡터의 곱은 행렬의 각 열과 벡터 내적의 집합니다. 이해가 안 갈 것을 예상했으므로, 좀 더 쉬운 관점을 보여주겠습니다. 📌 첫 번째 관점 : 행 벡터와 벡터 x의 내적 행렬 A를 두 개의 행벡터 a1과 a2가 있는 행렬이..