4.1 ~ 4.4 자료구조

자료구조 : 이름 그대로 어떠한 구조로 데이터를 다룰지 학습하는 과목이다.

알고리즘 : 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차

시간복잡도와 공간복잡도

시간 복잡도 - 입력의 크기에 따른 프로그램 실행 시간의 관계

공간복잡도 - 입력의 크기에 따른 프로그램 실행 공간의 관계 (메모리)

여기서 사용하는 표기법이 Big O임.

Big O란 무엇인가

성능판단 척도 , 점근적 상한을 표기하는 방법

• 점근적 : 어떤 값이나 상태에 점점 가까워지지만 완전히 도달하진 못한다.
• 상한 : 넘을 수 없는 한계

실행 시간이 대략 이 이상(상한)은 커지지 않을 것.

Ex)

• O(1) : 시간이 상수값보다 오래 걸리지 않을 것
• O(n) : 시간이 n값에 따라 걸릴 것
• O(n^2) : 시간이 n의 제곱만큼 걸릴 것

등등 표로 나타내면 이렇다.

시간복잡도 성능(빠른 → 느린 순) 예시 알고리즘

O(1)	🚀 초고속 (최고)	배열에서 인덱스로 접근, 해시 테이블 조회
O(log n)	⚡ 매우 빠름	이진 탐색, 균형 이진트리 (AVL, Red-Black), 힙
O(n)	🙂 보통	단순 반복문 (리스트 탐색, 선형 탐색)
O(n log n)	🐢 조금 느림	퀵정렬, 병합정렬, 힙정렬
O(n²)	🐌 느림	버블 정렬, 삽입 정렬, 선택 정렬
O(2^n)	🦥 엄청 느림	피보나치 재귀 (단순 구현)
O(n!)	☠️ 최악	순열 생성 (브루트포스)

빅오에서 log 사용 방법

1. 기본적으로 log는 이진로그(log₂ n)그 를 의미하는 경우가 많다.
   1. ex) 이진탐색 , 힙정렬 , 균형 트리 연산
2. 하지만 log의 밑(base)는 보통 무시한다.
   • O(log₂ n), O(log₃ n), O(log₁₀ n) 모두 같은 O(log n)으로 취급.
   • 왜냐면 로그의 밑이 바뀌어도 상수 차이밖에 없기 때문 (logₐ n = log_b n / log_b a).
3. 특정 상황에서 log n 대신 log² n , n log n 같은 표현이 나옴

• O(log² n): 로그 연산을 두 번 해야 할 때 (예: 이진 트리에서 경로 압축).
• O(n log n): 정렬 알고리즘에서 흔히 등장 (퀵정렬, 병합정렬).

O(n) 은 n 번 반복 하지만,

O(log n) 은 반씩 줄어들며 실행 되서 훨씬 적은 횟수만 돌면 된다.

정리

• O(log n)은 이진 탐색이나 트리 연산처럼 반씩 줄어드는 알고리즘에서 등장.
• O(n log n)은 정렬(퀵정렬, 병합정렬)에서 자주 등장.
• 로그의 밑(base)은 보통 신경 안 써도 됨 (log₂ n이든 log₁₀ n이든 무시).
• O(log n)은 상당히 빠른 알고리즘이므로, 가능하면 O(n)보다는 O(log n)으로 최적화하는 게 좋음.

빅오 표기법 외엔 빅세타 표기법 , 빅오메가 표기법이 있음

• 빅오(O) 표기법: 최악의 경우에 대한 실행 시간의 점근적 상한 (최대 얼마나 오래 걸리는지).
• 빅세타(Θ) 표기법: 평균적인 실행 시간을 나타내며, 최악과 최선이 같은 경우 사용.
• 빅오메가(Ω) 표기법: 최선의 경우에 대한 실행 시간의 점근적 하한 (최소 얼마나 빠를 수 있는지).

정렬 알고리즘 시간 복잡도

삽입 정렬	O(n²)
선택 정렬	O(n²)
버블 정렬	O(n²)
병합 정렬	O(n log n)
퀵 정렬	O(n log n)
힙 정렬	O(n log n)

---

02. 배열과 연결 리스트

배열

일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조

각 요소는 0부터 인덱스가 메겨진다.

배열은 가장 기본적인 자료구조인 만큼 활용도가 매우 높다.

• 이차원 배열 : 배열 속에 배열 [ [] , [] ]
• 삼차열 배열 : 배열 속에 배열속에 배열 [ [ [] ] ]

연결 리스트

노드의 모음으로 구성된 자료구조다.

• 노드 : 데이터(들), 다음노드의 위치(메모리상 주소)를 포함한 연결 리스트의 구성 단위

• 헤드 : 첫번쨰 노드
• 꼬리 : 마지막 노드

연결리스트를 구성하는 모든 노드는 반드시 메모리 내에서 순차적으로 저장되어 있을 필요가 없다.

⇒ 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용하게 사용할 수 있다.

연결리스트 접근 O(n)

⇒ 연결리스트에서 특정 요소에 접근할 때는 앞에서 부터 순차적으로 접근할 수 밖에 없기 때문

연결리스트 추가 & 삭제 : O(1)

• 중간에 요소를 추가하거나 삭제하는 연산에서 재정렬이 불필요하기 때문

새로운 노드를 삽입 혹은 삭제할 위치가 주어지면 노드의 위치를 막론하고 노드에 접근하는 시간이 동일함.

연결 리스트 종류

1. 싱글 연결 리스트 (Singly Linked List)

• 한 방향(→)으로만 연결된 노드들의 집합
• 각 노드는 데이터 + 다음 노드의 주소(포인터) 를 가짐
• 처음(Head)부터 끝(Tail)까지 한 방향으로만 이동 가능
• 삽입, 삭제 연산이 빠르지만, 뒤에서 앞으로 접근이 어려움
• 사용 예시: 스택(Stack), 큐(Queue)

📌 구조

[Head] → [노드1 | 주소] → [노드2 | 주소] → [노드3 | null]

 

2. 이중 연결 리스트 (Doubly Linked List)

• 각 노드가 앞쪽(←)과 뒤쪽(→) 두 개의 포인터 를 가짐
• 앞으로도 가고, 뒤로도 갈 수 있음
• 노드 삭제나 삽입이 편리하지만, 포인터가 2개라 메모리 사용량 증가
• 사용 예시: 웹 브라우저 뒤로가기/앞으로가기, 음악 플레이어의 이전/다음 곡

[Head] → [노드1 | 주소] → [노드2 | 주소] → [노드3 | Head의 주소] (순환)

구조

 

3. 환형 리스트 (Circular Linked List)

• 끝(Tail)이 다시 처음(Head)과 연결된 구조 (원처럼 연결됨)
• 싱글/이중 연결 리스트 모두 환형으로 만들 수 있음
• Head부터 Tail까지 갔다가 다시 Head로 돌아올 수 있음
• 사용 예시: 프로세스 스케줄링(운영체제), 멀티플레이 게임에서 플레이어 턴 관리

📌 구조

• 싱글 환형 리스트

[Head] → [노드1 | 주소] → [노드2 | 주소] → [노드3 | Head의 주소] (순환)

• 이중 환형 리스트

 

 

📌 정리

유형 특징 장점 단점 사용 예시

싱글 연결 리스트	한 방향	메모리 절약, 간단함	뒤로 못 감	스택, 큐
이중 연결 리스트	앞뒤로 이동 가능	삽입, 삭제 쉬움	메모리 낭비 (포인터 2개)	웹 브라우저, 음악 플레이어
환형 리스트	끝에서 다시 처음으로	무한 루프 구조	종료 조건 신경 써야 함	프로세스 스케줄링, 게임 턴 관리

---

📌 한마디로 정리하면

• 싱글 연결 리스트: 한 방향만 간다
• 이중 연결 리스트: 앞뒤로 간다
• 환형 리스트: 원처럼 돈다

---

03. 스택과 큐

스택(LIFO , 후입 선출) - 한쪽에서 데이터 삽입 및 삭제

큐(FIFO, 선입 선출)

📌 스택(Stack) vs 큐(Queue) 차이점

특징 스택(Stack) 큐(Queue)

구조	LIFO (Last In First Out, 후입선출)	FIFO (First In First Out, 선입선출)
삽입 (Push/Enqueue)	한쪽(Top)에서만 가능	한쪽(Rear)에서만 가능
삭제 (Pop/Dequeue)	한쪽(Top)에서만 가능	반대쪽(Front)에서만 가능
사용 예시	실행 취소(Undo), 재귀 함수 호출 스택	프린터 대기열, 요청 처리

• 스택(Stack): 나중에 들어온 놈이 먼저 나가는 구조. (push, pop)
• 큐(Queue): 먼저 들어온 놈이 먼저 나가는 구조. (enqueue, dequeue)

---

스택( LIFO )

제일 위에 탑이라는 놈을 가지고 Push , Pop하는 구조.

• push(value) → 스택의 맨 위(top)에 데이터 추가
• pop() → 스택의 맨 위(top)에서 데이터 제거하고 반환
• LIFO (Last In, First Out) 구조

최근 호출된 함수의 매개변수가 가장 먼저 활용되고, 가장 먼저 메모리에서 삭제

---

큐 ( FIFO )

 

임시 저장된 데이터를 차례차례 내보내거나 꺼내와야 하는 각종 버퍼로도 활용 된다.

⇒ 줄 세우기 에 자주 사용된다.

<aside> ❓

버퍼: 데이터 임시 저장소 (속도 차이 보완)

</aside>

• 인큐(enqueue) : 한쪽에서 데이터 삽입하는 연산
• 디큐(dequeue) : 다른 한쪽 끝으로 데이터 빼내는 연산

그리고 큐도 여러 종류가 있는데 종류마다 시간복잡도가 다르다.

JS 코테 스터디 할 땐 배열에 관한 큐만 해서 큐는 O(n)인 줄 알았는데 O(1)이라는 말을 들었다.

배열 기반 큐는 대부분의 언어에서 삽입 - O(1) , 삭제 - O(n)이라 총 O(n)이라 한다.

push() , shift() 구조와 unshift() , pop() 구조 두개 다 FIFO 원칙을 지키니 반대로 써도 상관 없다.

그치만 연결리스트가 O(1)이라 성능으로써 연결리스트 쓰는 게 좋다고 한다.

큐 종류	삽입 (Enqueue)	삭제 (Dequeue)
기본 큐	O(1)	O(1)
배열 기반 (단순)	O(1)	O(n)
원형 큐	O(1)	O(1)
연결 리스트 큐	O(1)	O(1)
우선순위 큐 (힙)	O(log n)	O(log n)

 

 

 

---

원형 큐 : 데이터를 삽입하는 쪽 , 삭제하는 쪽, 양쪽을 하나로 연결해 사용하는 자료구조

• 공간 낭비 없음 → front와 rear가 배열 끝에 도달하면 다시 처음으로 돌아감.
• 고정 크기 → 동적 배열보다 메모리 절약 가능.
• 사용 예시
  • CPU 스케줄링 (라운드 로빈 방식)
  • 프린터 스풀링
  • 멀티 태스킹 큐
• 덱 : 양방향 큐의 약자. 양쪽으로 데이터를 삽입/삭제할 수 있는 큐
• 우선순위 큐 : 저장된 요소들이 선입선출로 처리되는 것이 아니라 우선순위가 높은 순서로 처리되는 큐

---

04. 해시 테이블

• 키(Key): 저장하고 싶은 데이터의 식별자
• 해시함수(Hash Function): 키를 입력받아 해시 인덱스를 계산해주는 함수
• 해시 인덱스(Hash Index): 해시함수가 계산해낸 고정된 범위의 인덱스
• 값(Value): 실제 저장하고 싶은 데이터

키와 값의 대응으로 이루어진 표(테이블)와 같은 형태의 자료구조

• 키는 해시 테이블에 대한 입력,같은 키를 얻고자 하는 데이터
• 해시 테이블은 운영체제 내부에서도 자주 사용한다.
• 키를 통해 얻고자 하는 데이터는 버킷에 저장되어 있다.

 

버킷이란?

같은 해시값(=같은 인덱스)으로 계산된 데이터들을 저장하는 공간이다.

해시 충돌을 해결하기 위함

• 해시 테이블 : 큰 서랍장
• 버킷 : 같은 번호(인덱스)에 해당하는 서랍 속 폴더

 

해시함수

임의의 길이를 지닌 데이터를 고정된 길이의 데이터로 변환하는 단방향 함수

그러니까 키→값으로 변환해주는 함수

값 →키는 안된다.

출력값이 없으면 undefined를 출력해야 함.

해시 함수의 연산방법은 해시알고리즘이라고 한다.

해시 값은 문자열이 한글자만 달라져도 크게 달라질 수 있다.

해시함수의 특징은 이렇다.

• 검색,삽입,삭제연산이 빠르고 O(1)
• 안정적이고(같은 입력 = 같은 출력)
• 잘 만들어진 해시함수라면 충돌 적고(해시값 잘 분산)
• 복원 불가능해야한다.(단방향)

단점

속도가 빠른만큼 많은 메모리 공간 소모 ⇒ 데이터가 매우 많을 경우 공간복잡도가 우수하지 않다.

특징 설명

입력 동일 → 출력 동일	같은 입력이면 항상 같은 해시값 반환
빠른 계산 속도	O(1) 속도로 빠르게 해시값 생성
충돌 최소화	다른 입력값이 같은 해시값을 가지면 안 됨
균등 분포	해시값이 골고루 퍼져야 함
단방향성	해시값으로 원본 복원 불가능
입력 크기 제한 없음	짧은 것도, 긴 것도 다 가능
출력 크기 고정	해시값은 항상 같은 길이로 출력

이러한 특징으로 인해 아래의 경우 사용된다.

• 무작위 값을 만들거나 단방향 암호를 만들 때
• 데이터의 무결성을 검증하기 위해 사용
• 해시 함수를 이용한 해시 값은 비밀번호를 저장할 때도 사용

---

해시 충돌

해시 테이블에서 충돌은 다른 키가 같은 해시 값(인덱스)을 가질 때 발생하는 문제다.

해시 함수가 아무리 좋아도 충돌은 피할 수 없으므로, 충돌 해결 방법이 필요하다.

 

충돌 해결 방법은 크게 2가지

🔹 1. 체이닝(Chaining, Separate Chaining)

🔹 2. 개방 주소법(Open Addressing)

 

해당 글에 자세히 넣어놨다.

https://dailycoding777.tistory.com/106