![]()
AC 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #include using namespace std; int waysToBuy(const vector& psum, int k) { const int MOD = 20091101; int ret = 0; vector count(k, 0); //overflow를 방지 for (int i = 0; i
데큐(dequeue) 를 이용한 간단 풀이입니다 AC 코드 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std; int main(){ int c; scanf("%d", &c); while (c--) { int n, k; scanf("%d %d", &n, &k); int ans; deque dq; for (int i = 2; i
AC 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include #include #include using namespace std; const int INF = 987654321; int n, k, m, l; //prerequisite[i] = i번째 과목의 선수과목 집합 int prerequisit..
에라토스테네스의 체는 굉장히 빠르게 동작하는 소수 찾기 알고리즘입니다. 알고리즘에 대해 간단히 요약을 하자면 소수를 구할 때 소수가 아닌 수들의 배수는 소수가 아니기 때문에 그들을 모두 지워나가면서 남은 수(소수) 들을 찾는 방법인데, 수의 범위가 점점 커지면, 메모리 공간이 부족하기 때문에 이를 극복하기 위해 비트 마스크를 이용합니다. (기존 알고리즘 또한 웬만한 범위 내에서는 잘 작동합니다) 따라서 비트마스크를 사용하는 구간도 메모리 영역에 국한되는데, 기존 에라토스테네스의 체 구현 과정에서 bool 배열로 범위 내 소수가 아닌 수들의 인덱스를 모두 false 처리하고, 소수들을 true 처리해서 소수들을 골라냈다면 이번엔 비트마스크를 이용해서, check 역할을 하는 배열을 unsigned char..
![]()
저번 시간에는 행렬 간의 기본적인 연산과 인덱싱에 대해 알아보았었다. 따라서 이번에는 저번 시간에 배운 기본적인 연산을 이용해 행렬 변환과 행렬식을 구하는 방법에 대해 글을 써보려 한다. 1. vector를 가지고 행렬 transformation 하기 임의의 벡터 x를 가지고 어떤 행렬 A에 대해 transformation을 하는 방법은 간단하다. 단, 벡터와 행렬의 공간이 맞아야 한다. (벡터 공간의 수와 행렬의 행) 예시를 보자 3 x 3 행렬 A에 대해 (1,2,3)으로 정의된 vector x의 transformation을 나타내려면 행렬 A의 각 행에 대해서 vector를 내적 하면 된다. 하지만 좀 보기 불편해 보인다. 사실 transformation을 하는데에 따로 함수를 정의할 필요는 없다...
![]()
우선 이번 주차 설명에 앞서서.. 학교 강의에서 나오는 실습 예제나 stack overflow나 다른 사람들의 numpy 코드를 보면 for loop, 즉 반복문을 numpy에선 잘 쓰지 않는다. 심지어 실습 문제에는 그냥 대놓고 for문 쓰지 말 것~이라고 주어지길래 왜 그런건지 찾아보니 for loop를 쓰면 numpy 함수를 쓴 것보다 속도가 상당히 느리다. 그래서 얼마나 느린 건지 직접 검증해보았다. numpy.arange를 통해 리스트를 만든 경우 0~999999 배열을 만드는 데에 6.49ms 가 걸렸다. for loop 를 통해 리스트를 만든 경우 동일한 크기의 배열을 만드는 데에 398ms 가 걸렸다. 실험 결과 약 50배가량의 시간 차이가 나버리는 것을 볼 수 있는데, 왜 그런것인지는 n..
![]()
어제 numpy를 처음 보고, 몇몇 함수들을 찾아보니 vector, matrix 관련한 식을 계산하는데 정말 유용하고 말도안되는 함수들이라서 깜짝 놀랐다. 그래서 까먹지 않기 위해 몇 가지 골라서 정리를 해본다. 1. 기초 함수들 아래 함수들은 "import numpy as py"가 위에 쓰여있다고 가정하고, 작성했습니다! np.array(arr) : 인자로 들어오는 "[]" 모양 리스트를 vector space로 만들어준다. 인자로 리스트를 직접 만들어줘도 되고, 리스트 변수를 인자에 넣어줘도 된다. np.full(arr_size, value) : 배열의 크기(arr_size)만큼 값(value)을 꽉 채워 넣어준다. arr_size에 들어가는 값이 다차원 배열이어도 된다. np.zeros(size),..
![]()
문제를 풀다가 다른 사람 코드를 봤더니 queue를 쓰던 map을 쓰던 새로운 요소 혹은 객체를 삽입할 때 make_pair, make_tuple을 이용해 객체를 만들고 push 하는 것이 아니라 그냥 emplace 함수를 이용해 간편하게 넣는 걸 보고 간편하다고 생각되어 찾아보니 효율도 대체적으로 좋은 듯하여 따로 찾아 정리를 해본다. (안 좋은 경우도 있다고 합니다.) 1. 정의 c++ reference 에서 emplace를 찾아보니 이러한 설명이 나왔다. 컨테이너에 키가있는 요소가 없는 경우 지정된 인수로 구성된 컨테이너에 새 요소를 삽입한다. emplace를 주의해서 사용하면 불필요한 복사 또는 이동 작업을 피하면서 새로운 요소를 구성할 수 있다. 반복자 및 참조자가 무효화되지 않는다. 여기서 말..
![]()
문제 링크 :https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다. LCS 문자열 찾기 : https://suhwanc.tistory.com/80 LCS 알고리즘 1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다...
![]()
문제 링크 : https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCR www.acmicpc.net 풀이 가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다. LCS 문자열 찾기..
![]()
문제 링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 가장 대표적이고 기본적인 LCS 길이 찾기 문제이다. LCS 길이 찾기 방법 : https://suhwanc.tistory.com/80 LCS 알고리즘 1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence..
1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데 연속된 부분 문자열을 나타내는 부분 문자열(Substring) 도 있다. (따라서 string 헤더파일의 substr()은 substring을 의미한다) 두 부분 문자열의 차이는 예를 들자면 pringles sangeles 이렇게 두 문자열이 있을 때 가장 긴 Subsequence는 pringles sangeles "ngles" 가 되고 가장 긴 Substring은 pringles sangeles "les" 가 된다. 위에서 알 수 있듯 가장 긴 Substring은 ..
