개요

자료구조와 알고리즘

자료구조는 데이터를 저장하고 사용하는 구조를 나타내며, 데이터의 종류에 따라 저장 방식과 처리 방법이 다릅니다.

알고리즘은 문제를 해결하는 절차로, 선택한 자료구조에 따라 다양한 알고리즘이 존재할 수 있습니다.

즉, 적절한 자료구조를 선택한 후, 이를 효율적으로 처리하는 알고리즘을 적용해 원하는 결과를 얻습니다.

시간복잡도

시간복잡도는 알고리즘의 성능을 평가하는 기준입니다.

알고리즘의 실행 시간은 컴퓨터 성능에 따라 다르므로, 실제 시간을 측정하는 대신 반복문과 같은 성능에 큰 영향을 미치는 요소를 기준으로 평가합니다.

시간복잡도는 여러 경우로 나뉘며, 최악의 경우(O), 평균의 경우(Θ), 최선의 경우(Ω)로 나뉘는데, 주로 빅오 표기법(O)을 사용해 성능을 표현합니다.

빅오 표기법은 입력이 늘어날 때 계산량의 증가율을 나타내며, 가장 큰 항만을 표기해 성능을 간략히 표현합니다.

예시: 3n^2 + 2n + 100 ⇒ O(n^2)

자료구조

배열 (Array)

- 특징: 메모리에서 연속된 공간을 할당하여 데이터를 저장. 배열의 시작 주소만 기억하고, 인덱스 참조는 O(1) 성능.

- 장점: 빠른 읽기, 쓰기, 참조.

- 단점: 삽입, 삭제 시 성능 저하. 배열 크기를 미리 알아야 하고, 메모리 낭비가 발생할 수 있음.

- JavaScript 배열: 불연속적 메모리를 할당하지만, 사용자에게는 연속된 배열처럼 보임.

연결 리스트 (Linked List)

- 구성: 노드(Data + 다음 노드를 가리키는 포인터)로 이루어짐.

- 장점: 데이터의 삽입/삭제가 쉽고, 메모리 공간을 유연하게 사용.

- 단점: 참조 시 성능이 O(n)으로 배열보다 느림.

스택 (Stack)

- 특징: FILO(First In Last Out) 구조로, 되돌리기와 문법 검사 등에 사용.

큐 (Queue)

- 특징: FIFO(First In First Out) 구조로, 운영체제의 프로세스 작업 처리에 주로 사용.

- 성능 개선: 마지막 노드를 가리키는 tail 변수를 사용하면 O(1) 성능으로 데이터 제거 가능.

덱 (Deque)

- 특징: 헤드와 테일에서 데이터의 삽입/삭제가 모두 가능한 자료구조. 스택과 큐를 모두 구현할 수 있음.

해시테이블 (Hash Table)

- 특징: 해시 함수를 사용해 데이터를 효율적으로 저장 및 검색할 수 있는 자료구조.

- 장점: 데이터 삽입, 수정, 삭제가 O(1)로 매우 빠름.

- 단점: 해시 충돌 시 성능이 O(n)으로 저하될 수 있음. 메모리 효율이 떨어지고, 데이터를 골고루 분배 시켜주는 좋은 해시 함수 구현이 중요.

셋 (Set)

- 특징: 데이터의 중복을 허용하지 않으며, 해시 테이블 기반으로 구현. key가 데이터로 사용됨.