우리들의 T'SPACE

문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다..

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 10 5 2 3 1 4 2 3 5 1 7 예제 출력 1 1 1 2 2 3 3 4 5 5 7 처음에는 당연히 vector에 수를 입력 받고 sort 함수로 정렬했다 근데 처음보는 Memory 초과... 제한된 메모리를 고려하고 있어서 어떻게 해야 할지 고민해보았습니다. 요즘 컴퓨터는 용량과 메모리가 크기 때문에 공간 복잡도를 크게 신경 쓰지 않아도 되지만, 가..

문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼..

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있..

대각 행렬은 위와 같이 i,j의 좌표가 같은 원소에만 값이 있는 행렬을 뜻 한다 쉽게말해 행렬에 죄측최상단 원소부터 대각선으로 내려오는 곳에 원소들만 있는 행렬이다 나머지는 0 그리고 그 원소들이 모두 1이면 Identity Matrix 항등 행렬이다 특징으로는 1) 대각행렬의 k승은 각 원소들을 각각 k승 한 것과 같다 2) 대각행렬의 역행렬은 각 원소들의 역수와 같다 3) determinent는 모든 원소들의 곱과 같다 4) Trace와 eigenvector(고유벡터)와의 관계에 의해 대각행렬의 각원소들은 그 대각행렬의 eigenvalue(고유값)이다 5) Symmetric, 대칭, 이다 https://tonnykang.tistory.com/96 eigenvalues & eigenvectors (고유..

일반적으로 고유값과 고유벡터를 배우면 위와 같은 식이 주어진다 이게 기하학적으로 무슨 뜻인지 확인해보면 A는 정방 행렬이고 λ는 고유값이고 (상수임!) x가 교유 벡터이다 Ax는 x라는 벡터를 A에 대해 선형 변환을 하는 것이다 λx는 x라는 벡터를 λ로 scaling (늘리거나 줄임) 것이다->왜냐 λ는 상수이기 때문이다 즉 A로 선형변환 했을 때 방향이나 차원등은 변하지 않고 λ의 크기로 scaling만 되는 벡터들이 고유 벡터인 것이다 그리고 그 고유 벡터가 A로 선형변환 됐을 때 커지거나 작아지는 정도 (scaling factor)가 λ인 고유 값이 된다 그래서 고유 벡터 마다 고유값이 있다 그러면 이들을 어떻게 구하는가? λ와 x 사이에 항등행렬(Identity Matrix)을 곱해준다 -> 일..

문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K) 를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤K ≤N) 출력 (N K) 를 출력한다. 경우에 따라 우리가 빠르다고 생각하는 방식과 컴퓨터가 빠르다고 생각하는 기준은 다르다 우리는 흔히 고딩때 부터 확통을 하면 nCk를 계산 할 때 n!/k!(n-k)!을 활용해 이미 약분 된 공식을 습관화 해서 사용한다 그러나 컴퓨터는 이것 보다 파스칼의 삼각형을 이용한 방법을 선호한다 #include #include #include #include using namespace std; int pascal(int N, int k) { if (k == 0) { return 1; } if (k == 1) { ..

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

​ 행렬의 Trace는 그 행렬의 대각 성분들의 합이다 (좌측 상단 부터 우측 하단) ​ N x N 크기의 정방 행렬이 있다면 그 행렬의 trace는 아래와 같이 정의 된다 ​ ​ 그래서 trace는 행렬의 대각 성분들의 합으로 계산되어 스칼라 값이 됩니다. 행렬의 트레이스(trace)는 선형 대수학 및 기타 수학 분야에서 여러 흥미로운 성질과 응용을 가지고 있습니다. 예를 들어, 유사 변환(similarity transformations) 하에서 불변하며(변하지 않음), 행렬의 고유값(eigenvalues)의 합과 동일합니다. 물리학에서는 트레이스가 종종 에너지-운동량 텐서(energy-momentum tensor)의 식에서 나타납니다. ​ For a 2x2 matrix: ​ For a 3x3 matr..

문제 정수 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개의 수들이 주어집니다. 이때, 주어진 M개의 수들 중에서 각각이 배열 A 안에 존재하는지를 판별하는 프로그램을 작성하면 됩니다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작습니다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. "이 포스팅은 쿠팡 파트너스 활동의 ..