본문 바로가기

algorithm18

선택 정렬 알고리즘(Selection Sort) ✔ 선택 정렬(Selection Sort) 선택 정렬은 가장 원시적이고 기초적인 방법 중 하나입니다. 선택 정렬은 이름 그대로 선택한 값을 제일 앞으로 보내서 정렬하는 알고리즘이다. 선택한 값이란 오름 차순일 경우 최솟값을 얘기하고, 내림 차순일 경우 최댓값을 얘기한다. ✔ 선택 정렬 동작 과정 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고, 교환 대상과 교환 대상 이후의 리스트를 전체 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap) 첫 번째 인덱스는 정렬된 상태이기 때문에 고정. 두 번째 인덱스를 교환(Swap) 대상으로 선정하고, 첫 번째 인덱스를 제외한 전체 리스트를 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap) 정렬이 완료될 때까지.. 2022. 11. 9.
[Algorithm] 소수 구하기 ✔ 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. ✔ 알고리즘 에라토스테네스의 체 방식은 위와 같이 2부터 시작해 해당 배수의 값을 지워 나가면 된다. 에라토스테네스의 시간 복잡도는 O(nloglogn) 이다. 사실 O(nloglogn)이 어느 정도인지 모르겠다... 다만, O(n)인 선형 알고리즘보다 빠르다고 생각하고 있다. 배수의 값을 미리 지우기 때문이라고 생각한다.(DP 느낌? 👀) #include #include using namespace std; int main() { int n=120, cnt=0; vector v(n+1, 1); for(int i=2; i*i 2022. 4. 5.
[Algorithm] 알고리즘 읽기와 분석(시간복잡도) ·코딩 테스트를 준비하면서 지금까지 알고리즘 문제를 풀 때 시간 복잡도/공간 복잡도 등에 대해서는 생각을 안 하고, 문제를 읽고 해당 문제의 조건으로 구현해서 제출하고 맞으면 다른 사람의 풀이 보고 넘어가고 틀리면 "왜 틀렸지?"라고 막연히 생각만 했었다. 그러다 좋은 강의로 인해 시간복잡도 등 분석에 대해서 알게 되어서 기록 및 공유하고자 한다. 먼저 시간 복잡도에 대해서 간단히 얘기하면, 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 시간 복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. $$ O(N!) > O(2^N) > O(N^2) > O(NlogN) > O(N) > O(\sqrt{N}) > O(logN).. 2022. 3. 16.
하노이 탑 이동 순서 ✔ 하노이 탑 하노이의 탑에는 크기가 다른 원반이 n개 있고 원반을 끼울 수 있는 기둥이 세 개 있다. 하노이의 탑 문제는 어떻게 하면 원반 n개를 모두 가장 왼쪽 기둥(출발점, 1번 기둥)에서 오른쪽 기둥(도착점, 3번 기둥)으로 옮길 수 있을까 하는 문제이다. ※ 하노이 탑 규칙 - 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. - 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력. 단, 이동 횟수는 최소가 되어야 한다. ✔ 하노이 탑 풀이 원반이 3개일 때 원반 전체를 'C'로 옮기려면, 3원반이 'C'로 먼저 옮겨져야 하니깐, 1,2원반이 'B'로 옮겨져야 한다. 그러면 위와 같이 3원반을 'C'로 옮길 수 있다. 이제 'B'에 .. 2021. 4. 12.
피보나치 수열 알고리즘 피보나치 수열 0과 1부터 시작해서 바로 앞의 두 수를 더한 값을 다음 값으로 추가하는 방식으로 만든 수열을 피보나치 수열이라고 한다. 즉, 0+1=1, 1+1=2, 1+2=3 0 1 1 2 3 5 8 13 a[0] a[1] a[0]+a[1]=1 a[1]+a[2]=2 a[2]+a[3]=3 a[3]+a[4]=5 a[4]+a[5]=8 a[5]+a[6]=13 n번째 피보나치 수를 구하는 알고리즘을 재귀 호출을 이용해서 구현 Python Language def fibo(n): if n 2021. 4. 4.
[Algorithm] 최대공약수(GCD), 최소공배수(LCM) ✔ 유클리드 최대공약수(GCD) 수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다. a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같습니다. 즉 gcd(a, b) = gcd(b, a%b)입니다. 어떤 수와 0의최대공약수는 자기 자신입니다. 즉, gcd(n, 0) = n입니다. ex) 60과 24의 최대공약수 gcd(60, 24) = gcd(24, 60%24) = gcd(24, 12) = gcd(12, 24%12) = gcd(12, 0) = 12 81과 27의 최대공약수 gcd(81, 27) = gcd(27, 81%27) = gcd(27, 0) = gcd(27, 0) = 27 a와 b의 최대공약수를 구하기 위해서 (a, b)보다 좀 .. 2021. 4. 4.

티스토리툴바