개발/알고리즘 썸네일형 리스트형 탐색 - 해시 탐색법(Hash Search) 해시 탐색법은 데이터와 데이터를 저장할 인덱스를 연관시켜 짧은 시간에 찾을 수 있도록 한 알고리즘이다. 1. 넣을 값의 인덱스 찾기 값을 전체 사이즈로 나눈 값의 나머지로 인덱스를 정한다 (v % size = idx) 2. 값을 넣을 인덱스에 값이 있을때 아까 넣은 1과 21은 v%5 값이 같기 때문에 충돌이 일어난다!! 이럴때는 찾은 v%5값을 하나씩 증가하면서 빈 공간을 찾는다. idx 값이 2일 때 비어있으므로 여기에 넣는다!! 0. 구현 package com.bp.restart.search; public class HashSearch { private int [] BUCKTES = null; private int SIZE = 0; public HashSearch(int size){ this.BUC.. 더보기 탐색 - 이진탐색법(Binary Search) 순차탐색법(Linear Search) 보다 훨씬 좋은 성능을 보이는 탐색법이다. 그러나 이진탐색법을 이용하기 위해선 "배열에 저장된 데이터는 정렬되어 있어야 한다" 다음의 배열에서 숫자 5의 인덱스를 구해보자. int [] arr index 0 1 2 3 4 5 6 7 8 value 2 3 5 6 8 10 11 15 19 1. 배열의 가운데 숫자 arr[4] 가 3보다 크다. >> 숫자 5는 배열의 index가 0, 1, 2, 3 중에 하나 이다. 2. 배열의 index 가 0~ 3 의 중간인 arr[1] 가 2 보다 작다 >> 숫자 5 는 배열의 index 가 2, 3, 중에 하나이다. 3. 배열 index 가 2~ 3 의 중간인 arr[2] 의 값이 5이다!! 이러한 과정으로 배열에 길이가 n일때 1.. 더보기 탐색 - 순차탐색(Linear Search) 선형탐색법! 탐색법 중에 하나다 앞에서부터 하나하나 확인하면서 찾는 탐색법 가장 단순하고 가장 쉽다. public class Search { /** * 선형 탐색 * @param array : 찾을 배열 * @param find : 찾을 * @return 찾은 idx */ int linear(int [] array, int find){ for(int i = 0 ; i < array.length ; i++){ if(array[i] == find) { return i; } } return -1; } } 더보기 큐(Queue) - 배열 요즘 위 이미지와 같이 거리두면서 줄 잘 서고 계신가요? ㅎㅎ 줄 잘서는 자료구조 큐(Queue)를 해보겠습니다! ㅋㅋ 큐(Queue) 는 선입선출(FIFO : First In First Out)구조로 선형자료구조에 해당합니다. 스택과 같이 가장 기본이 되는 자료구조입니다. 스택은 넣고 꺼내는 입구가 하나였다면, 큐는 넣는 곳 빼는곳이 각각 따로 있습니다. 큐에 넣는것을 enqueue 큐에서 꺼내는 것을 dequeue 라고 합니다. 큐를 한번 그림으로 설명 해볼께요 우선, front와 rear 변수를 선언합니다. 이는 현재 queue의 상태를 확인 할때 사용합니다. front는 맨 앞, rear는 맨뒤라고 생각하시면 됩니다. 맨 처음 큐가 비었기 때문에 front와 rear 가 idx -1 을 가르킵니다.. 더보기 스택(Stack) " FILO : First In Last Out " 어디선가 본거 같은 문구 아닌가요 ? 네! 소방서에서 볼 수 있는 문구죠! 소방관 분들 항상 감사하게 생각하고 있습니다. 지금 이시간에도 열심히 일해주시는 소방관 분들 화이팅! 자료구조에도 이 말이 통하는 것이 있는데 바로 스택(Stack) 입니다! 스택은 아래 그림과 같은 형태의 선형자료구조입니다. 깊숙한 통에 책을 쌓아 올린다고 생각하면 좋습니다. 먼저 들어간 책이 가장 아래 놓이고, 그 위로 책이 차근차근 쌓이겠지요. 그 책을 꺼낸다면 맨위 책부터 하나하나 꺼내야 할 것이구요 그래서 후입선출구조 (LIFO : Last In First Out)의 구조라 합니다. 이 자료구조에는 넣는 함수 Push , 꺼내는 함수 Pop를 구현합니다. 우선 스택을 구.. 더보기 이전 1 다음