CS공부 ) 자료구조와 알고리즘

배열과 연결 리스트의 차이점은?

	배열	연결리스트
작동방식	연속된 메모리 공간에 데이터를 저장	각 노드는 자기 자신의 데이터와 다음 노드를 가리키는 포인터를 저장
저장	물리적으로 연속된 메모리 주소에 저장된다	각 노드가 별도의 메모리 블록에 저장
접근속도	O(1) (인덱스로 직접 접근 가능)	O(N) (앞에서부터 순차적으로 탐색)
삽입/삭제 속도	O(N) (중간에 삽입/삭제 시 요소들을 이동해야 함)	O(1) (포인터만 변경하면 되므로 빠름)
검색 속도	순차 검색(Linear Search, O(N)) - 첫 번째 원소부터 끝까지 하나씩 비교하며 찾음 이진 탐색(Binary Search, O(log N)) - 가운데 값을 기준으로 반씩 줄여가며 검색	처음부터 끝까지 하나씩 확인 O(N) (순차 검색만 가능!)
메모리 효율성	추가적인 포인터 저장이 필요 없으므로 메모리 사용량이 적음	각 노드마다 포인터가 필요하여 메모리 사용량이 많음
크기 조정	배열을 동적으로 확장할 때, 기존 배열의 데이터를 새로운 더 큰 메모리 공간으로 복사하는 방식으로 동작하기 때문에 크기 변경이 어렵고, 확장 시 새 배열을 만들어야 함	연속된 메모리 공간이 필요하지 않고, 각 노드가 별도의 메모리 블록에 할당되기 때문에 동적으로 크기를 조절할 수 있음
장점	빠른 인덱스 접근 구현이 간단함	크기 변경이 어려움 삽입/삭제 속도가 느림
단점	크기 변경이 자유로움 삽입/삭제가 빠름 메모리 조각화 문제 없음	검색 속도가 느림 메모리 사용량 증가 → 각 노드가 데이터를 저장하는 것 외에도 포인터(다음 노드의 주소)를 저장해야 하므로 추가적인 메모리 공간 필요. 캐시 효율성이 낮음 → 노드들이 메모리에 흩어져 있기 때문에, CPU 캐시 히트율이 낮아 성능이 저하될 수 있음.
예	redis, mongodb	mysql

 

📌 어떤 경우에 어떤 걸 선택해야 할까?

✅ 배열을 선택하는 경우

• 검색이 자주 필요할 때 (O(1)로 빠르게 접근 가능)
• 데이터 크기가 미리 정해져 있고 변경이 적을 때
• 캐시 효율성이 중요한 경우

✅ 연결 리스트를 선택하는 경우

• 삽입/삭제가 빈번할 때 (O(1)로 빠르게 처리 가능)
• 데이터 크기가 유동적일 때 (메모리 효율적 사용 가능)
• 연속된 메모리 공간을 확보하기 어려울 때

 

정렬 알고리즘 중 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)의 시간 복잡도와 차이점은?

시간복잡도

	퀵정렬	병합 정렬
시간 복잡도 (최선)	O(n log n)	O(n log n)
시간 복잡도 (최악)	O(n²) (피벗 선택이 나쁠 경우)	O(n log n) (항상 일정)

병합정렬은 2개의 배열이 될때까지 데이터를 반으로 나누고 각 부분을 정렬한 뒤 모든 배열을 비교해서 병합하는 방식으로 작동합니다. 그렇기 때문에 logn횟수 만큼 배열의 나누고, n번 횟수만큼  병합하기 때문에 어떠한 상황에도 n log n만큼의 시간복잡도가 됩니다. 

 

퀵정렬은 피벗을 기준으로 배열을 두 부분으로 나누고, 각 부분을 재귀적으로 정렬하는 방식으로 작동합니다. 나누는 과정에서 배열을 나누는 작업은 O(n) 시간이 걸리고, 이 과정을 재귀적으로 반복하는데, 계속해서 가장 왼쪽 또는 가장 오른쪽 값을 pivot값으로 선택하면 n + (n-1) + (n-2)... 값을 반복하게 되므로 n의 제곱만큼 재귀되기 때문에 n의 제곱만큼의 시간복잡도를 갖을 수 있습니다. 최선의 경우는 배열이 이미 균등하게 나누어지는 경우입니다. 최선의 경우에는 매번 배열을 균등하게 나누기 때문에, 분할 작업이 log n번 발생하고, 각 분할에 대해 O(n) 시간이 걸립니다. n log n만큼의 시간 복잡도를 갖습니다. 

차이점

	퀵정렬	병합정렬
메모리 사용량	O(log n) 설명: 퀵정렬은 분할 후 재귀적으로 두 개의 부분 배열을 정렬합니다. 배열을 절반씩 나누면서 진행되기 때문에, 최선 및 평균적인 경우에는 재귀 호출의 깊이가 log n이 됩니다	O(n) (새로운 리스트 생성) 설명: 각 재귀 호출마다 배열을 반으로 나누고 각 부분을 정렬한 후 두 개의 배열을 병합하는데, 이 과정에서 새로운 배열이 생성됩니다. 병합정렬은 배열을 병합할 때마다 새로운 공간을 필요로 하므로 메모리 사용량이 더 많습니다
저장장치	메모리만 사용한다(그렇기 때문에 메모리 용량 이상의 데이터에서 메모리 부족으로 강제로 종료되거나 오류 발생)	메모리 내에 담을 수 없을만큼 클 때 하드디스크도 사용하기 때문에 안정성 보장
안정 정렬 (Stable Sort)	❌ (같은 값들의 순서 보장하지 않음) 설명: 같은 값을 가진 요소들이 정렬 후 순서가 바뀔 수 있다	✅ (같은 값들의 순서 보장함) 설명: 예를 들어, 학생들을 성적순으로 정렬하되, 이름순으로 같은 성적의 학생들이 정렬되도록 해야 할 때 병합정렬이 유리
실제 사용	mysql에서는 단일 컬럼 정렬이고 sort_buffer_size 보다 작은 데이터에서 활용된다	sort_buffer_size보다 큰 데이터에서 사용된다. sort_buffer_size은 mysql설정에서 수정할 수 있다
index_db의 활용	직접적인 관계는 없음.	인덱스 생성 과정에서, 데이터베이스는 디스크에 저장된 데이터를 읽고 병합정렬을 통해 정렬 후 인덱스를 만듭니다. 이때 병합정렬은 디스크 기반 정렬을 최적화할 수 있기 때문에 인덱스 DB를 효율적으로 만들 수 있습니다

O(N) Vs O(logN)의 시간 복잡도 비교