게으름뱅이의 앞구르기

Queue란? 먼저 들어간 자료가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조 스케줄링, 탐색 알고리즘 등에 활용됨 Put : 큐에 데이터를 넣음 Get : 큐에서 데이터를 꺼냄 Front : 큐의 가장 앞쪽. 즉, 데이터를 Get할 수 있는 위치를 의미함 Rear : 큐의 가장 뒤쪽. 즉, 데이터를 Put할 수 있는 위치를 의미함 큐에도 Overflow, Underflow가 발생할 수 있음. Queue의 종류 선형 : 막대 모양으로 된 큐 환형 : 선형 큐의 문제점을 보완한 큐*. Front가 큐 끝에 닿으면 큐 맨 앞으로 데이터를 보내 원형으로 연결함 * 배열로 데이터 추가/삭제를 반복하다보면 마지막 배열에 도달 후, 데이터 공간이 있어도 데이터를 넣을 수 없음. 즉, 스..

Stack이란? 스택(stack)은 제한적으로 접근할 수 있는 나열 구조 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. (출처 : Wikipedia - 스택) Push : 스택에 데이터 추가 Pop : 스택에서 데이터 빼기 Top : 스택의 최상단을 의미. 이걸 넘어가면 Stack overflow 발생 스택에 더 이상 뺄 것이 없을 때 pop을 하면 Stack underflow 발생 스택의 구현방법 배열(배열을 이용할 경우 메모리 낭비가 발생할 수 있음) 스택을 선..

Linked List란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. (출처 : Wikipedia-연결리스트) Linked List의 필요성 일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고 나열할 수 있으나, 배열을 사용하..

자료구조의 필요성 데이터 효과적으로 저장, 처리하는 방법에 대한 이해 필요 불필요한 메모리 및 성능 낭비를 피하기 위해 기본적인 자료구조 선형 구조 배열 연결리스트 스택 큐 비선형 구조 트리 그래프 자료구조와 알고리즘 효과적인 자료구조 설계를 위해 알고리즘 지식 필요 효과적인 알고리즘 작성을 위해 적절한 자료구조 사용 성능 측정 방법론 시간 복잡도 : 사용되는 연산 횟수 Big-O 표기법 사용하며, 최악의 경우를 나타냄 O(n) ← n 만큼 반복 O(n²) ← 이중 for문을 사용해서 n의 2제곱만큼 반복됨 O(1) ← 한번에 처리됨 O(1) → O(n) → O(nlogn) → O(n²) → O(n³) (순서대로 1000 → 1,000,000 → ... → ...→ 10억번 연산(1초 이상 소요)) 시간..