자료구조, 알고리즘

index.ys 2023. 7. 18. 23:49

자료구조, 알고리즘

데이터를 효율적으로 저장하고 관리하는 방법을 제공하는 컴퓨터 과학 분야
자료구조는 데이터를 조직화하고 액세스하며 수정하는데 사용
자료구조는 데이터를 저장하는 방법과 데이터에 접근하는 방법을 결정
데이터를 효율적으로 관리하기 위해 적절한 자료구조를 선택하는 것이 중요함

선형자료구조

데이터가 일렬로 배열된 형태
ex) 배열, 스택, 큐

비선형자료구조

데이터가 계층적 구조로 구성된 형태
ex) 트리, 그래프

변수

cpu에 계산을 시키려면 메모리에 값이 존재해야함
변수를 이용해서 메모리에 값을 저장할 수 있음
변수는 어떤 값을 메모리에 쉽게 저장하기 위한 이름있는 공간

https://velog.io/@southbig89/%EB%B3%80%EC%88%98Variable

배열

변수를 많이 선언하기 않고 같은 종류의 데이터를 쉽고 효율적으로 메모리에 저장할 수 있는 자료구조
같은 종류의 데이터를 모아 순서대로 메모리에 저장함
요소(element)와 색인(index)로 구성되어있음
색인은 배열의 오프셋, n개의 요소를 가진 배열은 0~n-1까지의 색인에 접근할 수 있음
배열의 각 요소들은 연속된 영역에 저장되기 때문에 색인을 사용해서 요소에 접근가능
특정 요소에 접근하는 속도는 빠르지만 특정요소를 추가, 삭제하는 작업을 시간이 오래걸림 => 요소가 추가되거나 삭제 될때 요소 뒤에 있는 메모리 공간들을 추가되려는 요소만큼 뒤로 밀고, 밀린 영역에 새로 추가되는 요소들을 넣어야 하기때문에 메모리 영역을 뒤로 미는동안 오버헤드가 발생함
정적자료구조 => 배열을 만들기 위해서는 미리 그 크기를 정해놔야함, 연속된 메모리 주소 할당
시간 복잡도 : O(1) => 임의 접근 방식을 사용하기 때문에 데이터를 찾을때 처음부터 찾지 않아도됨, 인덱스를 통해 원하는 요소의 값을 빠르게 찾을 수 잇음

https://velog.io/@eagle5424/%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%B0%B0%EC%97%B4array

링크드 리스트

동적 자료구조 => 노드에 저장된 데이터값고 다음 데이터가 있는 메모리주소를 가르킴, 데이터들이 연속적으로 메모리에 저장되어 있지 않고 떨어져 있어도 포인터가 다음 데이터의 메모리 주소를 가리키고 있기 때문에 선형구조로 데이터 저장이 가능
데이터 탐색시 O(n)의 시간복잡도를 가짐 => 첫번째 노드 부터 순차적으로 데이터를 찾아 나가야 하기때문에
데이터의 접근, 탐색 => 배열
데이터의 추가, 삭제 => 연결리스트

https://velog.io/@wmc1415/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A7%81%ED%81%AC%EB%93%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%8B%A8%EC%9D%BC

스택

한쪽 끝에서만 데이터를 삽입하거나 삭제 할 수 있는 선형 자료구조 => LIFO구조
데이터를 추가하거나 삭제하는 작업이 매우 빠르고 간단하기 때문에, 프로그래밍에서 자주 사용됨
주요 연산은 peek(), pop(), push()가 있음 순서대로 맨위에 값을 확인, 맨위의 값을 빼냄, 맨위에 값을 추가

큐

데이터를 일시적으로 저장하기 위한 선형 자료구조
일종의 대기열, 먼저 도착한 데이터가 먼저 처리됨 (cpu 스케줄링 큐)
FIFO 형태 자료구조
enqueue와 dequeue,peek 구성됨

해쉬 테이블

해시함수

입력된 데이터(key)를 고정길이의 불규칙적인 숫자로 변환해 주는 함수
해시 함수를 거쳐서 반환된 불규칙한 숫자를 hashvalue 라고함 일반적으로 hashvalue는 16진수로 표기됨

해시함수 자바스크립트 예시

dog(key) : 99646(hashvalue)

function hashFunction(str) {
  let hash = 0;
  if (str.length === 0) {
    return hash;
  }
  for (let i = 0; i < str.length; i++) {
    const char = str.charCodeAt(i);
    hash = (hash << 5) - hash + char;
    hash = hash & hash; // 비트 연산을 통한 해시 충돌 방지
  }
  return hash;
}

hashFunction('dog')//99646

반환되는 데이터의 길이가 바뀌지 않음 ex) cat => 98262 , dog => 47565, elepant => 45756 길이가 같음
ex) SHA-1 함수는 출력데이터가 항상 20바이트로 고정됨 => 긴 데이터, 짧은 데이터 둘다 해쉬 함수를 거쳤을때 20바이트 고정됨
동일한 데이터를 넣으면 반환되는 데이터도 동일한 숫자가 반환됨 dog => 99646, cat => 47565
전혀 다른 데이터 (key)를 해시 함수에 넣었을때 낮은 확률로 value가 동일한 값이 출력 될 수 있음 => 해시 충돌
해시 테이블은 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 검색 속도가 빠름 => 배열의 index처럼 해시 테이블의 key값을 찾아 데이터를 검색하기 때문
key를 해시함수의 인자로 넣고, 해시값을 반환함
반한된 해시값을 index삼아 value를 저장함
index = hashfunc(key) % 배열의 길이
index에 value를 저장 ex) 5 강아지
해시 테이블은 데이터에 접근할 때 해시 함수를 1번만 수행하므로 빠르게 데이터를 저장, 삭제 , 조회
시간복잡도는 모든 처리에 대해 O(1) 이고, 충돌 발생시 O(K)이다 적재율 => 적재된 key갯수 K/해시 테이블의 크기 N

해시 충돌

해시 함수에 전혀 다른 key를 넣었을때 동일한 해시값이 반환되는 상황
ex) 철수 : 영희 , 짱구 : 맹구 => 철수, 짱구 두개의 다른 key를 해시 함수에 넣었을때 같은 해시 값이 반환되어 버킷의 같은 인덱스에 영희와 맹구가 저장될 수 있음
해결방법 : 해시값이 동일한 경우 기존에 있던 value값의 뒤에 링크드 리스트로 새로 추가된 value를 붙혀 해결할 수 있음

트리

배열과 링크드 리스트 자료구조의 단점을 보완하여 여러 데이터를 계층적으로 구조화 할때 사용하는 비선형 자료구조
링크드 리스트와 같이 데이터 필드와 포인터 필드로 구성되어 있음
데이터 삽입 삭제시 메모리 내에서 요소를 이동하지 않고 포인터만 변경해주면 됨
링크드 리스트 처럼 데이터 조회시 선형으로 모든 데이터를 조회 하지 않고 하위 노드에 있는 데이터를 조회 하기 때문에 검색 속도가 빠름
부모 노드가 없는 노드를 ROOT NODE 라고함 부모노드 => 자식노드 (부모노드) => 자식노드
같은 노드를 가지는 노드를 형제노드라고함 , 자식 노드가 없는 노드를 단말 노드라고함
노드를 서로 연결하는 선을 간선이라고하며 자신을 포함한 모든 자식 노드의 개수를 노드의 크기(size)라고함
각 노드가 지닌 자식노드의 수는 차수(degree)라고함
각 층은 레벨로 표현하며 트리의 최고 레벨을 높이라고함 ex) 레벨4 => 트리의 높이4

알고리즘

일련의 문제를 해결하기 위한 명령어들의 집함
컴퓨터 과학에서 이러한 명령어들은 데이터를 입력으로 받아드리고 이를처리하여 원하는 결과를 출력
ex) 문제해결, 딥러닝 머신러닝, cpu의 자원할당 및 관리, 데이터 베이스에서 데이터를 검색, 처리

시간 복잡도

알고리즘이 문제를 해결하는데 걸리는 시간을 측정하는데 사용

O(1)

입력데이터의 크기에 상관없이 처리속도는 일정하기 이루어짐
ex) array , linked list

O(log n)

입력데이터의 크기가 커지더라도 처리속도는 달라지지 않음
실행시간이 지날수록 처리해야 하는 데이터의 양이 절반으로 줄어드며 실행시간은 증가하지만 속도는 감소
ex) Binary search

O(n)

입력데이터의 크기에 비례해서 처리시간이 증가하여 메모리 사용이 증가

O(n^2)

입력데이터의 크기에 딸라 걸리는 시간은 제곱에 비례함
ex) 이중 for문

O(C^n)

문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n제곱

자료구조별 시간복잡도

공간 복잡도

알고리즘이 사용하는 메모리의 양을 측정
알고리즘의 효율성과 성능을 평가하고 개선할수잇음