에라토스테네스의 체는 굉장히 빠르게 동작하는 소수 찾기 알고리즘입니다. 알고리즘에 대해 간단히 요약을 하자면 소수를 구할 때 소수가 아닌 수들의 배수는 소수가 아니기 때문에 그들을 모두 지워나가면서 남은 수(소수) 들을 찾는 방법인데, 수의 범위가 점점 커지면, 메모리 공간이 부족하기 때문에 이를 극복하기 위해 비트 마스크를 이용합니다. (기존 알고리즘 또한 웬만한 범위 내에서는 잘 작동합니다) 따라서 비트마스크를 사용하는 구간도 메모리 영역에 국한되는데, 기존 에라토스테네스의 체 구현 과정에서 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은 ..
문제 링크 : https://www.acmicpc.net/problem/1042210422번: 괄호‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net문제 설명괄호 문자열의 길이가 주어졌을 때, 올바른 괄호 문자열의 개수를 구하는 문제이다.출력에서 10억+7로 나눈 나머지를 출력..
문제 링크 : https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 문제 설명 N개의 숫자가 주어졌을 때, N-1 개의 수 가운데에 + 또는 - 를 추가하여 n번 째 수를 만들 수 있는 등식의 ..
문제 링크 : https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다. www.acmicpc.net 문제 설명 백준 11066번 파일 합치기 1 : https://suhwanc.tistory.com/76 와 같은 문제인데, 이 문제는..