순차 탐색 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 데이터 크기에 따라 효율이 다르기 때문에 데이터가 많다면 비효율적인 방법 최악 : O(n) 이진 탐색 데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 비교할 때마다 탐색 범위를 반으로 줄이면서 특정한 값의 위치를 찾는다 분할 정복 알고리즘 - 리스트 개수 0,1개일 때 처리하고 2개 이상일 때 재귀 호출로 구현 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료 (mid=key) 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다. (mid < key) 중간 값보다 검색 값이 작다면 중간값 기준 배열의..
스택은 데이터의 입력과 출력이 이루어지는 공간이 top 하나뿐이고 FILO or LIFO 인 자료구조이다. 큐는 이와 반대로 입력과 출력 공간이 따로 존재하고 제일 먼저 들어간 데이터가 제일 먼저 나오는(FIFO) 자료구조이다. 그렇다면 큐를 왜 사용하는 것일까? 데이터 입력이 폭주하는 경우를 생각해보자. 먼저 입력받은 데이터의 처리가 안 끝났는데 그 뒤에 새로운 데이터가 계속 입력되면 그 데이터는 보관할 곳이 없기때문에 모두 버리게 된다. 이때 밀려드는 데이터를 저장하기위해 큐를 쓴다. 우리는 이런 구조를 자바에서 쉽게 찾아볼 수 있다. 바로 버퍼(Buffer)가 큐를 사용한다. 큐의 주요 기능 : 삽입과 제거 큐의 기본적인 구조는 아래와 같다. 큐는 삽입은 후단(rear), 제거는 전단(front) ..
스택이란 스택은 뭔가를 아래에서부터 위로 쌓아 얹어 올리도록 하는 자료구조이다. 스택은 오직 top에서 삭제, 추가가 이루어지기 때문에 중간 인덱스에 데이터 변경을 할 수 없다. 특정위치의 데이터를 추가/삭제 하고싶다면 해당 위치까지 pop을 해야한다. 따라서 스택은 가장 마지막에 들어간 데이터가 제일 먼저 나오고(Last In - First Out) 가장 먼저 들어간 데이터는 가장 나중에 나오게(First In - Last Out)된다. 스택의 주요 기능 삽입 제거 스택의 대표적인 기능은 위와 같이 2가지 연산이 있다. 먼저 삽입은 스택 위에 새로운 요소를 쌓는 작업이다. 제거는 스택에서 최상위 요소를 걷어내는 작업이다. 스택 구현 방식 스택을 구현하는 방식으로는 아래와 같이 2가지가 있다 배열을 이용..
더블 링크드리스트란? 링크드리스트의 탐색 기능을 개선한 자료구조이다. 링크드리스트는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색할 수 있었는데 더블 링크드리스트는 양방향으로 탐색이 가능하다. 아래는 더블 링크드리스트의 노드 구조이다. class Node { private Object data; private Node prevNode; private Node nextNode; public Node(Object newData) { this.data = newData; this.prevNode = null; this.nextNode = null; } } 주요 연산 링크드리스트와 동일하며 이전 노드를 처리하기 위한 구현이 더 추가될 뿐이다. 노드 생성 Node CreateNode(Object newData) ..
링크드리스트란 기본적으로 배열을 선언할 때 new int [10]으로 크기를 지정해서 선언한다. 허나 배열의 용도에 따라 계속 크기가 변할 수 있다면 결과를 예상해 크기를 선언하기엔 메모리 낭비가 발생하여 애매모호합니다. 이때 유연하게 크기를 바꿀 수 있는 자료구조를 사용해야 하는데 그중에 하나가 링크드리스트이다. 노드 링크드리스트 내의 각 요소는 노드(Node)라고 부른다. 이 노드에는 데이터를 보관하는 필드와 다음 노드와의 연결고리 역할을 하는 포인터로 이루어져 있다. 링크드리스트는 아래처럼 리스트의 첫 번째 노드인 헤드와 마지막 노드인 테일을 갖고 있다. 이런 구조라면 데이터의 크기를 미리 알지 못해도 된다. 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 되기 때문이다. 리스트 사이에 노드를 ..
