자료 구조와 알고리즘

배열이란?배열(array)또는 순차 리스트(sequential list)는 인덱스와 값의 쌍으로 이루어진 연속적인 메모리 위치의 집합이다.배열을 위해서는 운영체제가 연속된 공간을 할당한다.배열의 시작 주소만 알면 인덱스로 시작 주소 + 1이런 식으로 값을 찾아낸다. 따

스택이란?스택(stack)은 말 그대로 '쌓아놓은 더미'를 뜻한다. 먼저 들어간 데이터가 나중에 나오는 규칙. First In Last Out = Last In First Out = LIFO연결리스트로 스텍 구현하려면 삽입시도 헤드에 삭제시도 헤드를 삭제하면 됨. 한쪽

큐란?큐(Queue)는 질서 있는 줄을 의미한다.First In First Out먼저 들어간 데이터가 먼저 나오는 규칙. 스택과 반대의 특징.운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 cpu가 순서대로 처리 = fifo 스케줄링삽입은 가장 앞으로 넣고

덱이란?덱(Deque)은 데이터의 삽입과 삭제를 head와 tail에서 자유롭게 이루어지는 자료구조이다.덱을 이용하면 스택과 큐를 구현할 수 있다.addFirst,RemoveFirst 혹은 addLast,RemoveLast를 이용하면 스택이 된다.반대로, addFirs

해시 테이블이란?해시 테이블은 해시, 맵, 해시맵, 딕셔너리등 다양한 이름으로 불리는 자료 구조로 해시와 테이블이 합쳐진 구조를 가지고 있다.테이블 = 표. 프로그래밍에서는 배열의 인덱스와 데이터의 형태로 저장한다. 메모리를 절약하기 위해서 인덱스에 해시 함수를 활용.

셋(Set)이란?셋(Set)은 데이터의 중복을 허용하지 않는 자료 구조. 해시 테이블을 사용한다고 해서 해시 셋이라고도 불림.셋은 해시 테이블의 value 값은 사용하지 않고 key만 사용해서 구현. key가 key임과 동시에 데이터로 활용됨.

재귀란?재귀는 어떤것을 정의할때 자기 자신을 참조하는 것을 뜻한다.콜스택:함수가 호출되면서 올라가는 메모리 영역.스택이라고도 불림. 스택은 first in first out함수를 호출하면 콜스택에 올라가고 함수가 종료되면 콜스택에서 제거. 재귀함수는 호출할때마그 콜스택

버블 정렬: 구현은 쉽지만 성능은 좋지 않음. 앞에 있는 숫자와 옆의 숫자를 비교해서 자리를 바꾸는 알고리즘. 마지막 원소는 정렬이 된것이기 때문에 빼고 정렬. 성능 : 등차수열의 합만큼 실행됨. (n-1) + (n-2) +... + 2 + 1 = n(n-1)/2

재귀를 사용할 경우 콜스택에 계속 쌓이고 성능 문제가 있음. 메모이제이션: 피보나치 수열과 같은 하향식 문제에서 중복된 계산이 성능에 많은 영향을 끼침. 계산 결과를 저장해서 여러번 계산하지 않도록 하는 것. 빠른 데이터 탐색, 삽입, 삭제가 가능한 해시테이블을 사