CS 자주 나오는 질문 정리 (1)

알고리즘

• 시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?
  • 시간 복잡도(Time Complexity): 알고리즘이 문제를 해결하는 데 걸리는 시간을 분석하는 척도입니다. 이는 일반적으로 입력 크기에 대해 최악의 경우를 고려하여 표현되며, Big O 표기법을 사용해 나타냅니다. 예를 들어, O(n) 시간 복잡도는 입력 크기 n에 비례하는 시간이 걸린다는 것을 의미합니다.
  • 공간 복잡도(Space Complexity): 알고리즘이 문제를 해결하는 데 필요한 메모리 공간의 양을 분석하는 척도입니다. 이는 알고리즘 실행 중에 필요한 전체 메모리 공간을 의미하며, 이 역시 Big O 표기법으로 표현됩니다. 예를 들어, O(1) 공간 복잡도는 입력 크기와 상관없이 일정한 메모리를 사용한다는 것을 의미합니다.

→ 두 가지다 알고리즘의 성능 측정시 사용되는 개념입니다. 시간복잡도는 특정 알고리즘이 수행되는 시간을 의미하며 절대적인 시간이 아닌 알고리즘내에 연산의 횟수로 나타냅니다. 공간복잡도는 특정 알고리즘이 실행시 사용되는 메모리의 크기로 나타냅니다.

---

• 재미있게 공부한 알고리즘이 있다면 설명해주실 수 있을까요
  • X

---

• 포트폴리오에서 시간복잡도를 낮춘 사례가 있다면 설명해주실 수 있을까요?
  • X

---

• 이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?
  • 이분 탐색은 정렬된 배열에서 특정 요소를 찾는 알고리즘으로, 배열을 반으로 나누어 탐색 범위를 절반씩 줄여가며 찾습니다. 이 알고리즘의 시간 복잡도는 O(log n)으로, 각 단계마다 탐색 범위가 반으로 줄어들기 때문에 매우 효율적입니다

---

• 시간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?
  • 알고리즘 최적화: 더 효율적인 알고리즘을 사용하거나 기존 알고리즘을 개선하여 실행 시간을 줄입니다.
  • 자료구조 변경: 적절한 자료 구조를 사용하여 데이터 접근 및 관리 효율을 높입니다. 예를 들어, 해시 테이블은 탐색 시간을 상당히 단축시킬 수 있습니다.
  • 동적 프로그래밍(Dynamic Programming) 적용: 반복되는 계산을 저장하여 중복 계산을 줄이는 방법입니다.

---

• 공간복잡도가 높은 경우 취할 수 있는 일반 전략을 3가지 정도 설명해주실 수 있을까요?
  • 인플레이스(in-place) 알고리즘 사용: 추가적인 메모리 할당을 최소화하는 알고리즘을 사용하여 공간 복잡도를 줄입니다.
  • 데이터 압축: 데이터를 압축하여 메모리 사용을 줄입니다. 하지만 이는 CPU 사용량을 증가시킬 수 있습니다.
  • 스트리밍 알고리즘 적용: 데이터를 일부분만 메모리에 로드하여 작업을 수행하는 방식으로, 대규모 데이터셋 처리에 유용합니다.