개발자 당당근

📖이전글 검색 알고리즘(1)-선형검색 목차 이진검색 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행하는 알고리즘이다. 전제 조건은 요소가 오름차순 또는 내림차순으로 정렬되어 있어야 한다. 키 값은 21이다. 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 가운데 인덱스를 pc 라고 한다. 제일 가운데 요소인 a[3] 부터 검사한다. 검색하려는 값 21은 a[3] 값인 10보다 크다. 때문에 왼쪽의 값들은 제외한다. 그 다음 a[4]~a[6] 의 가운데 요소인 a[5] 를 검사한다. 21은 a[5] 값인 22보다 작기 때문에 오른쪽의 값들은 제외한다. a[4] 값인 21을 찾고 검색 종료. 여기서 중요한 것은, 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 거의 반으로 좁혀진..

목차 검색 알고리즘 검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다. 원하는 값을 찾기 위해서는 키(key) 값이 필요하다. 서울에 사는 사람을 찾기 위해서는 키값을 '서울' 로 지정해야 한다. 20세 이상 30세 미만인 사람을 찾기 위해서는 키 값을 20세 이상 30세 미만 으로 설정해야 한다. 대부분의 경우에서 키는 데이터의 일부이다. 선형 검색 무작위로 늘어놓은 데이터 모임에서 검색을 수행하는 방법이다. 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 키 값이 '1' 이라면 세번째 시도에서 성공하고, 키 값이 '4' 라면 검색에 실패한다. 선형 검색 종료 조건 다음 조건 중 하나라도 성립하면 검색을 ..

목차 큐(queue) 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조이며 순서를 기억하고, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 자료구조를 큐(queue)라고 한다. 큐의 특징 큐는 아래와 같이 데이터를 저장하고 사용한다. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 형태이다. 한쪽 끝에서 자료의 삽입이 이루어지고, 다른쪽 끝에서 자료의 삭제가 이루어진다. 그림으로 표현하면 이러한 형태이다. 큐에 맨 뒤에 데이터를 넣는 작업을 인큐(enqueue) 라고 한다. 큐에서 맨 앞의 데이터를 꺼내는 작업을 디큐(equeue) 라고 한다. 데이터를 꺼내는 쪽을 front 라고 한다. 데이터를 넣는 쪽을 rear 라고 한다. 큐 만들기 일반 큐 에..

목차 스택(stack) 데이터를 순서대로 저장하지만 사용할때는 가장 나중에 넣은 데이터를 먼저 꺼내도록 하는 자료구조를 스택(stack)이라고 한다. 스택의 특징 스택은 아래와 같이 데이터를 저장하고 사용한다. 가장 나중에 넣은 데이터가 가장 먼저 나가게 되는 후입선출(LIFO, Last In First Out) 형태이다. top에서 자료의 삽입과 자료의 삭제가 이루어진다. 중간 데이터를 삭제할 수 없다. 그림으로 표현하면 이러한 형태이다. 스택에 데이터를 삽입하는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 푸시와 팝을 하는 위치를 꼭대기(top) 이라고 하고, 스택의 가장 아래부분을 바닥(bottom)이라고 한다. 스택 만들기 스택 본체 데이터를 저장하는..

자료구조의 개념 자료구조의 의미 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다. 쉽게 말해 데이터를 어떻게 저장하고 어떻게 꺼내올 것인지 정의한 것. 자료구조는 왜 배워야 하는가? 데이터를 효율적으로 이용하기 위해 자료구조를 사용한다. 알고리즘이 단순해질 수 있는 방법 중 하나가 자료구조를 잘 만드는 것이다. 알고리즘과 무슨 관계가 있는가? 자료구조를 잘 만들면 알고리즘을 단순하게 만들 수 있다. 알고리즘을 아무리 잘 짜더라도 자료구조가 좋지 못하면 좋은 코드가 나오지 않는다. 1. 자료와 정보 사이의 관계 자료(data) : 현실 세계에서 관찰이나 측정을 통해 수집된 값(value) 나 사실(fact) 이다. 정보(information) : 어떤 상황에 대해서 의사결정을 할 수 있게 ..