시간 복잡도에 대해서 들어보셨지요? 🤔
시간 복잡도를 처음 공부하시면, 예제와 함께 하는 것이 정말 많은 도움이 됩니다. 저도 역시 그랬고요.. 📚
사실, 예제 찾기가 쉽지가 않아요. 🔍
그리고, 시간복잡도를 구하는 문제가 면접에서 나온다면, 잘 기억하세요.
⚠️ 집중해서 풀어보세요! ⚠️
내가 만든 코드가 아닌데 거기서 시간 복잡도를 구하려면 먼저 자세히 살펴봐야 합니다.
👀 무턱대고 구하시면 틀릴 가능성이 커요. 왜냐하면, 함정을 숨겨 놓을 것이라서요. 분명! 🪤 시간 복잡도 때문에 집중하지 못해서 면접에서 떨어졌다면? 걱정마세요.. 🙋
그렇다고 절대 당신이 실력이 없는 것이 아닙니다.
이 시간복잡도는 중요하지만, 아주 아주 작은 빙산의 일각일 뿐이에요. 🧊
내가 작성한 코드의 시간복잡도만 정확히 구하실 줄 알면 됩니다. 장기적으로 그런 의미에서 이 예제들이 많이 도움이 되었으면 좋겠습니다. 🙏
그럼 이제 25개의 시간 복잡도 문제를 살펴보겠습니다. 각 문제 아래에 답과 간단한 설명을 달아두었습니다. 📔
🚀 준비되셨나요? 시작해 봅시다! 🚀
문제 #1
이 코드의 시간복잡도를 구해보세요.
정답 보기
답: O(N + M)
설명: 첫 번째 루프는 N-1번, 두 번째 루프는 M-2번 실행됩니다. 따라서 전체 시간 복잡도는 O(N + M)입니다.
문제 #2
이 코드의 시간복잡도를 구해보세요.
정답 보기
답: O(N^2)
설명: 중첩된 for 루프가 N^2번 실행되고, 마지막 단일 for 루프가 N번 실행됩니다. 따라서 전체 시간 복잡도는 O(N^2 + N) = O(N^2)입니다.
문제 #3
이 코드의 시간복잡도를 구해보세요.
정답 보기
답: O(N^2)
설명: 외부 루프는 N번 실행되고, 내부 루프는 N, N-1, N-2, ..., 1번 실행됩니다. 이는 등차수열의 합으로 N(N+1)/2가 되어 O(N^2)입니다.
문제 #4
우리는 두가지 알고리즘을 가지고 있습니다, 'Algo A'와 'Algo B' 이지요. 여기서, 'Algo A'가 'Algo B' 보다 점근적으로 더 효과적이라는 말은 무슨 뜻인지 아래 선택 답지에서 골라보세요.
a) Algo A가 어떤 크기의 입력이 들어와도 항상 빠르다.
b) Algo A가 입력 크기가 클 경우 빠르다.
c) Algo A가 입력 크기가 작을 경우 빠르다.
d) Algo B가 항상 더 빠르다.
e) Algo A가 입력 크기에 따라 메모리 관리능력이 효과적이다.
정답 보기
답: b) Algo A가 입력 크기가 클 경우 빠르다.
설명: '점근적으로 더 효과적'이라는 말은 입력 크기가 충분히 클 때 더 효율적임을 의미합니다.
문제 #5
이 코드의 시간복잡도를 구해보세요.
정답 보기
답: O(log N)
설명: 매 반복마다 i가 2로 나누어지므로, 이 루프는 log₂N번 실행됩니다.
문제 #6
a) O(N * N)
b) O(N * log N)
c) O(N * log(log(N)))
d) O(N)
e) O(N * Sqrt(N))
정답 보기
답: b) O(N * log N)
설명: 외부 루프는 log N번 실행되고, 내부 루프는 N, N/2, N/4, ..., 1번 실행됩니다. 이는 N + N/2 + N/4 + ... + 1 ≈ 2N이 되어 O(N log N)입니다.
문제 #7
a) Θ(n)
b) Θ(nLogn)
c) Θ(n^2)
d) Θ(n^2 / Logn)
e) Θ(n^2Logn)
정답 보기
답: b) Θ(nLogn)
설명: 외부 루프는 n/2번 실행되고, 내부 루프는 log₂n번 실행됩니다. 따라서 전체 시간 복잡도는 Θ(n log n)입니다.
문제 #8
이 코드의 시간복잡도를 풀어보세요.
정답 보기
답: O(log(min(n, m)))
설명: 이는 유클리드 알고리즘으로, 최악의 경우 시간 복잡도는 O(log(min(n, m)))입니다.
문제 #9
다음 보기중 O(n^2)가 아닌 것은 무엇인가요?
a) (15^10) * n + 12099
b) n^1.98
c) n^3 / (sqrt(n))
d) (2^20) * n
정답 보기
답: a) (15^10) * n + 12099
설명: 이 식은 O(n)입니다. 나머지는 모두 n^2보다 큰 차수를 가집니다.
문제 #10
아래 보기 중 가장 빠른 반복문을 고르세요.(n은 양의 정수)
a) for(i = 0; i < n; i++)
b) for(i = 0; i < n; i += 2)
c) for(i = 1; i < n; i *= 2)
d) for(i = n; i > -1; i /= 2)
정답 보기
답: c) for(i = 1; i < n; i *= 2)
설명: 이 루프는 O(log n)의 시간 복잡도를 가지며, 다른 옵션들보다 빠릅니다.
문제 #11
가장 빠른 순서대로 나열하세요.
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = n Log n
f4(n) = n^(Log n)
f5(n) = n!
a) f3(), f2(), f4(), f1(), f5()
b) f3(), f2(), f1(), f4(), f5()
c) f2(), f3(), f1(), f4(), f5()
d) f2(), f3(), f4(), f1(), f5()
정답 보기
답: a) f3(), f2(), f4(), f1(), f5()
설명: n이 증가함에 따라 함수의 증가 속도를 비교하면 이 순서가 됩니다.
문제 #12
a) O(sqrt N)
b) O(log N)
c) O(log^2 N)
d) O(N)
e) O(N * log N)
f) O(N * sqrt N)
정답 보기
답: d) O(N)
설명: 최악의 경우(모든 원소가 k와 같을 때), 이 함수는 모든 원소를 확인해야 하므로 O(N)입니다.
문제 #13
a) O(RClog(RC))
b) O(2^(R + C))
c) O(RC)
d) O(R + C)
e) O(RR + CC)
정답 보기
답: c) O(RC)
설명: 이는 동적 프로그래밍 접근법으로, 각 셀을 한 번씩만 계산합니다. 따라서 시간 복잡도는 O(RC)입니다.
문제 #14
a) O(n)
b) O(n^2)
c) O(nlogn)
d) O(n(logn)^2)
정답 보기
답: a) O(n)
설명: j는 루프 전체에서 최대 n번만 증가하므로, 전체 시간 복잡도는 O(n)입니다.
문제 #15
이론적으로 QuickSort의 최악의 시간 복잡도는 어떻게 됩니까?
a) O(n)
b) O(log n)
c) O(n^2)
d) O(n log n)
e) O(n(log n)^2)
정답 보기
답: c) O(n^2)
설명: QuickSort의 최악의 경우(이미 정렬된 배열이나 모든 원소가 같을 때)에는 O(n^2)의 시간 복잡도를 가집니다.
문제 #16
정답 보기
답: O(n)
설명: 이 함수는 매번 자신을 두 번 호출하지만, 입력 크기를 절반으로 줄입니다. 따라서 총 호출 횟수는 n + n/2 + n/4 + ... ≈ 2n이 되어 O(n)입니다.
문제 #17
정답 보기
답: O(2^n)
설명: 이는 피보나치 수열을 계산하는 재귀 함수입니다. 각 호출에서 두 개의 재귀 호출이 발생하며, 이는 이진 트리 형태로 확장되어 O(2^n)의 시간 복잡도를 가집니다.
문제 #18
정답 보기
답: O(n^2)
설명: 외부 루프는 n번 실행되고, 내부 루프는 n, n-1, n-2, ..., 1번 실행됩니다. 이는 등차수열의 합으로 n(n+1)/2가 되어 O(n^2)입니다.
문제 #19
다음 중 O(n log n) 시간 복잡도를 가진 정렬 알고리즘이 아닌 것은?
a) 퀵 정렬 (평균 경우)
b) 병합 정렬
c) 힙 정렬
d) 삽입 정렬
정답 보기
답: d) 삽입 정렬
설명: 삽입 정렬의 시간 복잡도는 O(n^2)입니다. 나머지 정렬 알고리즘들은 평균적으로 O(n log n)의 시간 복잡도를 가집니다.
문제 #20
정답 보기
답: O(log n)
설명: 이진 검색은 매 단계마다 검색 범위를 절반으로 줄이므로, 시간 복잡도는 O(log n)입니다.
문제 #21
정답 보기
답: O(n log n)
설명: 외부 루프는 n번 실행되고, 내부 while 루프는 log n번 실행됩니다 (k가 2배씩 증가하므로). 따라서 총 시간 복잡도는 O(n log n)입니다.
문제 #22
다음 중 공간 복잡도가 O(1)인 정렬 알고리즘은?
a) 퀵 정렬
b) 병합 정렬
c) 힙 정렬
d) 버블 정렬
답: d) 버블 정렬
설명: 버블 정렬은 추가적인 메모리 공간을 사용하지 않고 입력 배열 내에서 원소들을 교환하며 정렬합니다. 따라서 공간 복잡도는 O(1)입니다.
문제 #23
답: O(3^n)
설명: 이 함수는 매 호출마다 세 개의 재귀 호출을 합니다. 이는 3진 트리 형태로 확장되어 O(3^n)의 시간 복잡도를 가집니다.
문제 #24
답: O(n^3)
설명: 첫 두 개의 루프는 각각 n번 실행되고, 세 번째 루프는 평균적으로 n/2번 실행됩니다. 따라서 총 시간 복잡도는 O(n * n * n/2) = O(n^3)입니다.
문제 #25
다음 알고리즘들의 평균 시간 복잡도를 가장 빠른 것부터 나열하세요:
- 버블 정렬
- 퀵 정렬
- 선형 검색
- 이진 검색
- 병합 정렬
답: 4 (이진 검색) < 3 (선형 검색) < 2 (퀵 정렬) = 5 (병합 정렬) < 1 (버블 정렬)
설명:
- 이진 검색: O(log n)
- 선형 검색: O(n)
- 퀵 정렬과 병합 정렬: O(n log n)
- 버블 정렬: O(n^2)
이렇게 25개의 시간 복잡도 관련 문제와 답변을 제공했습니다. 이 문제들을 통해 다양한 알고리즘과 코드 패턴의 시간 복잡도를 이해하고 분석하는 능력을 기를 수 있을 것입니다.