본문 바로가기

algorithm16

[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.

티스토리툴바