본문 바로가기

컴퓨터 과학(CS)/자료구조

 (4)
자료구조 - 큐(Queue), 배열로 큐 만들기 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조입니다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 인 점이 스택과 다릅니다. 큐 란? 큐(Queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다. 가장 먼저 꺼내는 선입선출 구조로 되어 있습니다. 생활에서 볼 수 있는 큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있습니다. 스택과 마찬기로 큐는 배열을 사용하여 구현할 수 있습니다. 처음이 끝과 연결되었다고 보는 자료구조입니다. 여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트(front) 와 리어(rea..
자료구조 - 스택(Stack) , 배열로 스택만들어 보기 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다. 스택이란? 스택(stack)은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out) 입니다. (가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다.) 스택에 데이터를 넣는 작업을 푸시(push)라 하고 ,스택에 데이터를 꺼내는 작업을 팝(pop)이라고 합니다. 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 합니다. 스택만들기 스택을 구현하는 프로그램을 만들어 보겠습니다. 스택 본체용 배열: stk 푸시된 데이터를 저장하는 스택 본체의 배열입니다. 인덱스 0인 요소가 스택의 바닥..
자료구조 - 이진 검색(binary search), 시간 복잡도(time complexity), 공간 복잡도(space complexity) 이진 검색법에 대해 알아보겠습니다. 이 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것입니다. 이진 검색은 선형 검색보다 좀 더 빠르게 검색 할 수 있다는 장점이 있습니다. 이진검색 이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다. 오름차순에서 어떤 수 x를 검색하는 과정을 생각해보 겠습니다. 먼저 배열의 중앙에 위치한 요소부터 검색을 시작합니다. 검색하려는 값이 중앙요소보다 큰 경우 검색 범위 중앙에 위치에서 값을 확인하여 일치하는 값을 찾는 검색입니다. 이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 입니다. 검색에 실패한 경우는 [ log..
자료구조 - 선형 검색(linear search), 순차 검색(sequential search) 선형 검색 요소가 직선 모양으로 늘어선 배열에서의 검색은 원한는 키 값을 갖는 요소를 만날 때까지 맨 앞에서 부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘입니다. 요솟수가 7개 이고 [ 6, 4, 3, 2, 1, 3, 0 ] 으로 되어 있고 검색을 2로 할 때입니다. import java.util.Scanner; public class SeqSearch { static int seqSearch(int[] a, int n, int key) { int i = 0; while(true) { if ( i == n ) return -1; if ( a[i] == key ) return i; i++; } } publ..

티스토리툴바