소수를 구할 때 가장 빠른 시간에 구할 수 있는 에라토스테네스의 체의 방법을 알아보자

환경 및 선수조건

• C++

에라토스테네스의 체

2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.

1. 2부터 시작해서 n까지 진행한다.
2. 가장 작은 수를 선택한다.
3. 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.

• 시간복잡도: O(n*log(log(n)))

코드

• count: 저장된 소수의 개수
• c[n+1]: 2 ~ n까지 수에서 제거된 숫자를 체크하는 배열, true(제거됨), false(제거되지않음)
• p[n]: 소수를 저장하는 배열

example.cpp

bool c[1000001]= {false,};
int p[1000000];
int count = 0;

//0~1000000까지 소수 구하기
for(int i=2; i<=1000000; i++){
	if(c[i] == false){
		// 추가
		p[count++] = i;
		// i의 배수 지우기
		for(int j=i+i; j<=1000000; j+=i){
			c[j]=true;
		}
	}
}

참고자료

• 코드플러스 알고리즘 기초
• https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

업데이트(2018.04.29): a mod b 부분 추가

유클리드 호제법을 통해서 최대공약수를 공하고 최대공약수를 통해서 최소공배수를 구해보자

환경 및 선수조건

• C++

최대공약수 공식(유클리드 호제법)

• a,b: 최대공약수를 구하고자 하는 두 수
• r: a를 b로 나눈 나머지 = ( a%b ) = ( a mod b )
• 식: gcd(a,b) = gcd(b,r)

코드(최대공약수)

example.cpp

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

최소공배수 공식(최대공약수를 이용)

• a,b: 최소공배수를 구하고자 하는 두 수
• gcd(a,b): a와b의 최대공약수
• (최소공배수 * 최대공약수 = a * b)를 이용
• 식: a * b / gcd(a,b)

코드(최소공배수)

example.cpp

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

int lcm(int a, int b){
    return a * b / gcd(a,b);
}

참고자료

• 코드플러스 알고리즘 기초

알고리즘 문제를 풀 때 연산의 결과가 너무 커서 어떠한 수로 나눈 나머지를 통해 해를 답을 구하는 경우가 있는데 이 때 어떻게 이용할 수 있는지 보자

환경 및 선수조건

• C++

공식

• 합: (A + B) % M = ((A % M) + (B % M)) % M
• 곱: (A X B) % M = ((A % M) X (B % M)) % M
• 차: (A - B) % M = ((A % M) - (B % M) + M) % M
• 뺄셈의 경우에는 % 결과가 음수로 나올 수 있기 떄문에 M을 더해준다

유도(덧셈만)

다음 아래 사진처럼 식 유도가 가능합니다

참고자료

• 코드플러스 알고리즘 기초

for문 조건문으로 strlen으로 조건을 주었을 때 발생하는 문제에 대해 생각해보자.

환경 및 선수조건

• C++

비교

• strlen을 for문에 사용하였을 경우
• 시간 복잡도: O(n^2)

...
for(int i=0; i<strlen(s); i++){
    // Do Something
}
...

• strlen를 for문 밖에 사용하였을 경우
• 시간 복잡도: O(n)

...
int len = strlen(s)
for(int i=0; i<len; i++){
    // Do Something
}
...

참고자료

• 코드플러스 알고리즘 기초

업데이트(2021.10.11): pyenv 설정 관련 값 추가

pyenv와 Anaconda를 같이 사용할 때 환경변수 순서 때문에 pyenv 환경에서도 Anaconda가 실행될 때가 있다. 이 때 해결 방법을 알아보자

환경 및 선수조건

• pyenv, virtualenv
• Anaconda

문제

분명히 pyenv를 통해서 virtualenv를 실행했음에도 불구하고 다음처럼 python이 Anaconda의 python으로 잡히는 경우가 있다.

아래와 같은 경우는 3.6.2가 나와야 하는데 Anaconda의 3.6.1버전의 python이 나오고 있는 모습

해결방법

아래처럼 ~/.bash_profile에 쉘스크립트를 작성하면됩니다.

쉡스크립트를 작성할 때 반드시 Anaconda에 대한 설정보다 아래에 pyenv관련 정보를 불러와야합니다.

bash_profile

# added by Anaconda3 4.4.0 installer
export PATH="/Users/taewoo/anaconda/bin:$PATH"

# Load pyenv automatically
eval "$(pyenv init --path)"
eval "$(pyenv init -)"
eval "$(pyenv virtualenv-init -)"

참고자료

• https://stackoverflow.com/questions/40944277/pyenv-and-anaconda-issue-with-export-path