본문 바로가기

자료구조 | 알고리즘7

[자료구조]해시 테이블 해시테이블이란 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조이다. 삽입은 O(1) 이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다. (상수시간만큼 걸린다는 의미) 간단히 말해서 사물함처럼 한정된 배열에 key를 index로 변환하여 값들을 넣는다. hashBrown처럼 값들을 잘게 잘라 값으로 넣는다고 생각하면 쉽다. 해시함수 : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수. HashCollision / 해시충돌이 일어난다면? 선형 탐사법 : 충돌이 발생하면 옆으로 한칸 이동한다. 제곱 탐사법 : 충돌이 발생하면 발생한 횟수의 제곱만큼 옆으로 이동한다. 이중 해싱 : 충돌이 발생하면 달느 해시 함수를 이용한다. 분리 연결법 : 버킷의 값을 연결.. 2023. 3. 2.
[자료구조] 큐 First In FIrst Out 이라는 개념을 가진 선형 자료구조. 선! 입! 선! 출! Linear Queue와 Circula Queue 가 존재. (Queue스펠링 진짜 이상하다..) Array로 표현하면 빈공간에 자동적으로 차는게 아니라 삭제는 Front(맨 앞의 인덱스)부터 사라짐. ->DeQueue 추가는 Rear(가장 마지막 인덱스) 부터 추가됨 -> EnQueue 만약 빈 인덱스에 값이 모두 추가가 되어 자리가 모두 찬 다면 값을 더이상 추가할 수 없다. (하지만 자바스크립트의 경우는 값에따라 증감되기때문에 배열의 크기가 무한정 커질 수 있다는 단점이 있다.) 따라서 앞당기는 작업이 필요함 //정리 : 배열중간에 추가 or 삭제를 하게되면 위치 이후의 요소들을 한 칸씩 당겨주거나 밀어야한다.. 2023. 2. 28.
[자료구조]스택 스택 LIFO(Last In First Out)이라는 개념을 가진 선형 자료구조다. 프링글스 통을 생각하면 된다. 스택을 구현하기 위해서는 스택의 상단에만 있는 요소에 접근할 수 있기 때문에 마지막으로 삽입되는 요소인 스택의 상단에 대한 포인터를 유지해야 한다. push() : 요소를 스택에 삽입 begin if stack is full return endif else increment top stack[top] assign value end else end procedure pop() : 스택에서 요소를 제거 begin if stack is empty return endif else store value of stack[top] decrement top return value end else end p.. 2023. 1. 18.
[자료구조]연결리스트 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다. 각 요소는 노드라고 부르며 데이터영역과 포인터 영역으로 구성된다. 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다. 탐색은 O(n)이 소요된다. 요소를 추가하거나 제거할 때는 O(1)이 소요된다. Sinlgy LInked List, Doubly linked List, Circular Linked List가 존재한다. 추가와 삭제가반복되는 로직이면 배열(순차적리스트) 대신 연결리스트가 더욱 적합하다. https://hans-j.tistory.com/121 [알고리즘]배열(순차리스트) 배열 (Array) 연관된 데이터를 연속적인 형태로 구성된 주고를 가진다. 배열에 포함된 원소는 순서대로 번호(index)가 붙는다. 배열의 크기는 고.. 2023. 1. 18.
[알고리즘]시간 복잡도 계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다.- 위키백과 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 빅 O 표기법 : 최악의 실행 시간을 표기 빅 오메가(Ω) 표기법 : 최상의 실행 시간을 표기 빅 세타(Θ) 표기법 : 평균 실행 시간을 표기 https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%.. 2023. 1. 18.
자료구조와 알고리즘의 차이점은? 자료구조 : Data Stucture 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미. 또한, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미. 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다. 일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것 ex)줄서기, 예매 데이터 구조의 예시 선형 데이터 구조: Linked List, Stack, Queue, Array. 계층적 데이터 구조: 트리, 힙, 트리. 기타 데이터 구조: 해시맵, 그래프, 행렬. 상황에 맞는 자료구조를 선택하는 것이 중요하다!! 알.. 2023. 1. 18.
[자료구조]배열(순차리스트) 배열 (Array) 연관된 데이터를 연속적인 형태로 구성된 주고를 가진다. 배열에 포함된 원소는 순서대로 번호(index)가 붙는다. 배열의 크기는 고정되어 있지 않고 가변적인 것을 명심하자!! index가 number가 아니어도 된다. 자바스크립트의 Array는 HashMap에 가깝다. 배열은 객체로 분류되기 때문에 객체처럼 사용이 가능하다. (하지만 추천하지는 않음) 추가와 삭제가 반복되는 로직이라면 배열 사용은 권장되지 않는다. 배열은 요소를 추가/삭제하고 앞으로 당기고/ 뒤로 미루는데 선형시간이 소요된다.O(n) 배열의 크기는 고정되어 있지 않고 가변적인 것을 명심하자!! index가 number가 아니어도 된다. 배열은 탐색이 많은경우에 유용함. //배열 생성 let arr1 = []; cons.. 2023. 1. 18.

티스토리툴바