When they go low, We go high

Hash개념임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수 라고 한다해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다 해시함수위에 설명한 것과 같이 키에 대한 해시값을 만드는 함수계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수 (충돌이 일어나지 않을수록 좋다)대표적으로 나눗셈법(Division Method)와 곱셉법(Multiplication Method..

트리(Tree)- 비선형 자료구조 - 계층적 자료구조- 노드 들이 링크로 연결되어 있다 - 목적 : 탐색(의사결정, 파일 시스템, 검색엔진, 라우터 알고리즘 등에서 사용) 용어루트노드 : 레벨 = 1 잎노드(단말노드) : 자식 노드가 0인 노드서브트리(sub tree) : 트리 내부의 작은 트리포레스트(Forest) : 트리가 여러 개 모인 것레벨(level) : 루트에서 그 노드 까지의 거리를 말함높이(depth) : 트리의 최대 레벨차수(degree) : 자식 노드의 개수 Binary tree 종류완전 이진트리 (Complete Binary tree)- 노드가 위에서 아래로 왼쪽에서 오른쪽으로 채워진다- 잎노드 두개의 레벨 차가 1 이하이다- heap구현시 완전 이진트리를 기본으로 하며 , 전통적으로..

데크(Deque)- 데이터 삽입 삭제가 양 쪽 끝에서 이루어지는 자료구조- 스택과 큐의 장점을 가지고 옴- Doubly Ended Queue의 약자로 Dequeue- Head Tail Linked List 라고도 함- 입력제한데크( Scroll ) , 출력제한데크( Shelf )가 있다- 큐와 동일하게 Front 와 Rear를 사용한다 Scroll(입력제한데크) Shelf(출력제한데크)

큐(Queue) - 스택과 다르게 선입선출(FIFO) 구조를 가진다- 쉽게 말해 데이터를 저장하는 입구와 데이터를 삭제(출력)하는 출구가 다른 저장 방식 - 예를 들어 번호표를 먼저 뽑은 손님이 먼저 서비스를 받는 상황- front에서 데이터 삭제가 일어나고 , rear에서 데이터 삽입이 일어남- 삭제를 Dequeue 라고하고 삽입을 Enqueue 라고 표현함- peek : 스택 처럼 front에 있는 데이터를 읽음 기능isEmpty- 큐가 공백인지 아닌지 확인 isFull- 큐가 포화상태인지 아닌지 확인 enQueue- 데이터 삽입 deQueue- 데이터 삭제 peek- front 위치에 있는 데이터 읽음 Java 로 구현한 큐(Queue) 메인함수 구현 결과 순환 큐(Circular Queue)- 큐..

스택(Stack) - 사전적 의미: 쌓다, 더미- 후입선출(LIFO) 구조를 갖는 자료구조로써 데이터 삽입과 제거가 한쪽 끝에서만 이루어짐- 쉽게 말해 한쪽이 막힌 저장공간에 자료를 하나의 입구를 통해서 넣고 빼는 방식- PUSH(저장)/POP(삭제)- 가장 먼저 처리해야 할 것을 가장 가까운 곳에 둔다는 개념 *LIFO(Last In First Out) : 후입선출 = FILO(선입후출) 기능push- 데이터를 스택에 저장(추가)한다- 데이터 갯수가 증가하므로 top의 위치를 +해준다 (top++;)pop- 데이터를 스택에 삭제(출력)한다- 데이터의 갯수가 감소하므로 top의 위치를 - 해준다(top--;) peek- 맨위에(top)의 위치에 있는 데이터를 읽어준다 - 데이터 갯수 변동 없음 Java로..

List- 선형 자료구조 - 순서를 가진 항목들의 모임- 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 새로운 장점을 취한 자료구조- 중복된 데이터의 저장 허용- ArrayList , LinkedList등 여러 인터페이스를 구현한 자료형이 있다- 자바스크립트,파이썬 같은 경우에는 리스트를 따로 구현하지 않고 배열에 List의 기능 중 일부를 제공- List에서는 인덱스가 중요하지 않다- 리스트의 핵심은 element간의 순서- 다른말로 순서라는 의미의 시퀀스(sequence)라고도 함- 수학적으로 유한수열을 표현한 것 기능(operation)- 처음,끝에 데이터 삽입기능- 리스트에 데이터가 있는지를 체크하는 기능- 리스트의 모든 데이터에 접근할 수 있는 기능 위와 같은 기능을 가지..

ADT(Abstract Data Type, 추상자료형)- 구체적인 기능의 완성을 언급하지 않고 순수하게 기능이 무엇인지를 나열한것 - 실제 자료를 내부적으로 어떻게 저장하고 처리하는지에 대한 것은 따지지 않고 이자료형을 이용할 때의 기능만 이야기하는 것- 따라서 ADT에는 성능에 대한 평가를 하지 않는다 정의An Abstract Data Type is data type that is organized in such a way that the specification of the objects and specification of the operation on the objects is separated from representation of objects and the implementation of ..

배열- 연관된 데이터를 그룹핑해서 관리하기 위한 방법- 하나의 변수에 여러 정보를 담을 수 있다- 반복문과 결합하여 효율적으로 사용이 가능- 인덱스를 통해 빠른 데이터 조회 가능 Java에서의 배열배열 생성- int[] 변수명 ; 으로 선언- 배열도 객체이므로 new연산자를 사용해 생성ex) int[] numbers = new int[6]; // 크기6을 갖는 numbers 라는 int타입의 1차원 배열 생성String[] strings = new String[100]; // 크기 100을 갖는 strings 라는 String타입의 1차원 배열 생성 배열의 값- 배열의 값은 배열의 인덱스를 이용하여 접근한다ex)numbers[0] = 1 ; // 정수형 배열 numbers 의 첫번째 칸에 정수 1을 저장..

퀵정렬- 정렬방식중 가장 효율적이고 빠른 방식- 분할 정복(Divide and Conquer)방식 이용- pivot이라는 기준값을 이용하여 작은 값은 왼쪽 큰 값은 오른쪽으로 옮기는 방식으로 진행- 가장 많이 사용 되는 방식 정렬 방식- 먼저 PIVOT 계수를 정한다 PIVOT 계수는 임의로 선정할 수 있으나 중간 크기의 수자를 PIVOT계수로 산정하는 것이 가장 효율적이므로 3개의 임의의 숫자를 랜덤으로 선택한 후 3개중 가운데 값을 PIVOT계수로 설정- PIVOT 값과 LEFT값을 비교한다 만약 LEFT값이 PIVOT값 보다 크다면 PIVOT값과 RIGHT값을 비교한다RIGHT값이 PIVOT값 보다 크다면 Right 인덱스를 왼쪽으로 위치시킨 후 다시 PIVOT값과 비교한다- RIGHT값이 PIVO..

삽입정렬- 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입함- 시간 복잡도:O(n^2)- 배열의 두 번째 데이터 부터 연산을 시작함 정렬방법- 두번째 인덱스 부터 시작( 해당 인덱스를 키값으로 지정)- 키값 왼쪽에 위치한 배열은 정렬 된 상태(처음엔 정렬되어 있다고 가정 : 배열의 크기가 1이므로)- 정렬된 배열의 값이 키값보다 크면 위치를 교환한다- 정렬된 배열의 값이 키값보다 작으면 교환을 중지한다(정렬된 배열중 자기자신 보다 작은 값 뒤 큰 값 앞에 위치)- 키값으로 지정되었던 인덱스 까지 정렬되었으므로 다음 인덱스를 다시 키값으로 지정하고 반복 ex) 사진 예시 [1회전] [2회전] [3회전] [4회전] Java로 구현한 삽입정렬