자료구조

1. 시간복잡도와 공간복잡도가 무엇인가요?

• 시간 복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 즉, **어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’**이 걸리는지 나타내는데 쓰이며 보통 빅O 표기법으로 나타냅니다.
• 빅O 표기법 : 상한 접근으로, 최악의 경우를 고려하는 표기법입니다. 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가? 를 표기하는 방법으로, 입력 범위 n을 기준으로 해서 로직이 몇번 반복되었는지 나타내는 것입니다.
• 시간 복잡도는 효율적인 코드로 개선하는데 쓰이는 척도됩니다.
• 공간복잡도 : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 의미합니다.
• 총 필요 저장 공간 = 고정 공간(알고리즘과 무관한 공간, 코드 저장 공간 & 단순 변수 및 상수) + 가변 공간(실행 중 동적으로 필요한 공간)
• 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 의해 좌우됩니다.

꼬리질문 1. 시간 복잡도는 어떻게 계산하나요??

• 빅O 표기법은 입력 범위 n을 기준으로 해서 로직이 몇번 반복되는지 나타내는 것입니다.
• 간단한 예시로 n개의 데이터에서 어떠한 하나의 데이터를 찾기 위한 알고리즘을 제작할 때 반복문을 돌려 데이터의 인덱스가 1인 값부터 진행한다면, 이는 O(N)이 됩니다.
• 알고리즘 진행 시 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 제거합니다.

Ex) $10n^2 + n$ ⇒ $n^2$

시간 복잡도, 공간 복잡도

2. ArrayList와 LinkedList의 차이점

• ArrayList
  • 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조를 의미합니다. 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 때문에 Index를 통한 접근이 용이합니다.
  • 배열은 인덱스를 통한 빠른 접근 O(1)이 가능하지만, 삽입/삭제의 경우 시간 복잡도가 O(n)이기 때문에 오래걸리며, 배열 중간에 있는 데이터가 삭제되면 공간 낭비가 발생합니다.
• LinkedList
  • 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 Head, 마지막 노드를 Tail이라고 합니다.
  • 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다.
  • 이로 인해 배열과는 다르게 순차적으로 접근은 O(N)이 걸리지만, 노드가 연결된 구조이기 때문에 삽입과 삭제가 O(1)이라는 장점이 있습니다.

3. Stack과 Queue