1. 시간복잡도와 공간복잡도가 무엇인지 설명해주실 수 있을까요?

시간복잡도는 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됩니다.

메모리 사용량에 해당하는 것이 공간 복잡도 Space Complexity

빅오 표기법의 종류

O(1) : 입력값에 상관없이 일정한 실행시간을 최고!의 알고리즘이라 할 수 있다. 하지만 상수 시간에 실행된다 해도 상수값이 상상 이상으로 클 경우 사실상 일정한 시간의 의미가 없다. 최고의 알고리즘이 될 수 있지만 그만큼 신중해야 한다.

O(log n) : 로그는 매우 큰 입력값에서도 크게 영향을 받지 않는 편이다. 매우 견고한 알고리즘으로 이진 탐색의 경우가 이에 해당한다.

O(n) : 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라 부른다. 정렬되지 않은리스트에서 최대 또는 최솟값을 찾는 경우가 해당되며 모든 입렵값을 적어도 한 번 이상은 살펴봐야 한다.

O (n log n) : 병합 정렬등의 대부분 효율이 좋은 알고리즘이 이에 해당 한다. 아무리 좋은 알고리즘이라 할지라도 n log n 보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수 있다.

O(n^2) : 버블 정렬 같은 비효율저긴 정렬 알고리즘이 이에 해당 한다.

O(2^n) : 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 한다. n^2와 혼동되는 경우가 있는데 2^n이 훨씬 더 크다.

O(n!) : 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.

2. 스택, 큐에 대해 설명해주실 수 있을까요?

큐는 선입선출 First In First Out의 자료구조입니다. 시간복잡도는 enqueueO(1) , dequeueO(1) 입니다. 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등이있습니다.
LIFO인 stack과 다르게 FIFO구조임을 기억하고 Circular Queue자료구조를 알고있어야한다.
array베이스 는 남는메로리로인해 서큘러 큐 형식으로 구현함.
list 베이스 는 링크드리스트와 같이 재할당을해야하거나 메모리낭비를 걱정할 필요가 엄슴.

스택은 후입선출 LIFO(라스트 인 퍼스트 아웃)의 자료구조입니다. 시간복잡도는 push O(1), pop O(1) 입니다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹브라우저 방문기록(뒤로 가기),깊이 우선탐색(DFS)딩이 있습니다.

3. 배열, 링크드리스트를 비교하여 설명해주실 수 있을까요?

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조 입니다. Linked list는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다.

그래서 각 operation의 시간복잡도가 다릅니다. 데이터 조회는 Array의 경우 O(1), Linked list는 O(n)의 시간복잡도를 갖습니다. 삽입/삭제는 Array O(n), Linked list O(1)의 시간복잡도를 갖습니다.

따라서 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회를 많이 한다면 Array를 사용하는 것이 좋습니다. 반면에 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked list를 사용하는 것이 유리합니다.

4. 트랜잭션이란 무엇이고 원자성, 일관성, 고립성, 지속성이란 무엇인지 설명해주실 수 있을까요?

데이터베이스 내에서 수행되는 작업의 최소 단위로, 데이터베이스의 무결성을 유지하며 DB의 상태를 변화시키는 기능을 수행합니다. 트랜젝션은 하나 이상의 쿼리를 포함해야 하고 , ACID라고 칭해지는 원자성, 일관성 , 고립성, 지속성의 4가지 규칙을 만족해야합니다.

원자성은 트랜젝션에 포함된 작업은 전부 수행되거나 아니면 전부 수행되지 말아야 합니다. arr or noting
일관성은 트랜잭션이 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 유지하는 것을 의미한다. 송금 전후 모두 잔액의 데이터 타입은 인티저 이여야 한다는 것이 일관성의 한 예가 될 수 있습니다.

고립성은 여러 트랜젝션은 동시에 수행됩니다. 이때 각 트랜젝션은 다른 트랜잭션의 연산 작업이 끼어들지 못하도록 보장하여 독립적으로 작업을 수행합니다. 따라서 동시에 수행되는 트랜잭션이 동일한 데이터를 가지고 충돌하지 않도록 제어해줘야합니다. 이를 동시성제어 concurrency control 라고 합니다.

지속성은 성공적으로 수행된 트랜젝션은 데이터베이스에 영원히 반영되어야 함을 의미합니다. 트랜젝션이 완료되어 저장이 된 데이터베이스는 저장 후에 생기는 정전,장애,오류 등에 영향을 받지 않아야 합니다.

5. 정규화란 무엇이고 대표적인 장점과 단점은 무엇이 있을까요?

정규화의 기본적인 목표는 테이블 간에 중복되는 데이터가 발생하지 않도록 하는 것이다. 중복된 데이터를 허용하지 않음으로써 데이터의 무결성을 유지할 수 있고, 이로 인해 데이터베이스 관리에 필요한 저장 공간을 축소시키는 효과가 있다.

장점
1. 데이터베이스 변경 시 이상현상 제거,
2. 효과적인 검색 알고리즘 생성,
3.데이터 구조의 안정성, 무결성 유지 등

단점
1. Join연산의 증가로 응답 시간이 저하