IT/Data Structure
[자료구조] 리스트 (ArrayList vs LinkedList)
1. 리스트 1.1 리스트란? 리스트(List)란 앞에서 공부한 배열, 스택, 큐 등과 같은 선형 자료구조이다. 그렇다면 이들과 리스트의 차이점은 무엇일까? 스택과 큐의 경우 자료의 접근이 전단(front) 혹은 후단(rear)에 제한되어 있다. 하지만 리스트는 이러한 제한이 없다. 즉, 임의의 위치에 있는 항목에 접근이나 연산이 가능하다는 것이다. 1.2 배열 vs 리스트 배열(array) 또한 임의의 위치에 접근이 가능하다. 그렇다면 배열과 리스트의 차이는 무엇일까? 배열은 각각의 원소에 순서대로 index가 할당되어 있다. 위 배열에서 c 원소를 삭제하는 경우 아래와 같은 형태가 된다. 삭제한 c의 메모리 공간은 빈 공간으로 남아있으며, d와 e의 index는 변함이 없다. 만약 위의 행위가 리스트..
[자료구조] 덱 (Deque)
덱 (Deque) 덱? 덱(Deque)이란 Double-Ended Queue의 줄임말이다. 즉, 앞쪽 front와 뒤쪽 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 덱 ADT 객체 전단과 후단 양쪽에서의 삽입과 삭제를 허용하는 동일한 자료형의 요소들의 모음 연산 addFront(x) : 요소 x를 덱의 맨 앞에 추가 addRear(x) : 요소 x를 덱의 맨 뒤에 추가 deleteFront() : 큐의 맨 앞의 요소를 삭제하고 반환 deleteRear() : 큐의 맨 뒤의 요소를 삭제하고 반환 getFront() : 큐의 맨 앞의 요소를 삭제하지 않고 반환 getRear() : 큐의 맨 뒤의 요소를 삭제하지 않고 반환 isEmpty() : 큐가 비어있으면 true 아니면 false 반환 isF..
[자료구조] 큐 (Queue) - 피보나치 수열 계산, BFS
1. 큐 (Queue) 1.1 큐? 큐(Queue)란 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 놀이동산의 놀이기구를 타기 위해 줄을 서있는 모습을 생각하면 이해하기 편할 것이다. 1.2 큐 ADT 객체 FIFO 접근방법을 유지하는 동일한 자료형의 요소들의 모음 연산 enqueue(x) : 요소 x를 큐의 맨 뒤에 추가 dequeue() : 큐의 맨 앞의 요소를 삭제하고 반환 peek() : 큐의 맨 앞의 요소를 삭제하지 않고 반환 isEmpty() : 큐가 비어있으면 true 아니면 false 반환 isFull() : 큐가 가득 차 있으면 true 아니면 false 반환 size() : 큐 내의 모든 요소 개수를 반환 display() : 큐 ..
[자료구조] 스택 (Stack) - 괄호검사, 수식계산, DFS
1. 스택 (Stack) 1.1 스택이란? 스택(Stack)이란 데이터의 삽입과 삭제를 한 쪽(top)에서만 할 수 있는 LIFO(Last In First Out) 형식의 자료구조이다. LIFO(Last In First Out)란 후입선출 방식이라고 하며, 가장 최근에 들어온 데이터가 가장 먼저 나가는 것을 의미한다. 1.2 스택 ADT 객체 LIFO 접근방법을 유지하는 동일한 자료형의 요소들의 모음 연산 push(x) : 요소 x를 스택의 맨 위에 추가 pop() : 스택의 맨 위의 요소를 삭제하고 반환 peek() : 스택의 맨 위의 요소를 삭제하지 않고 반환 isEmpty() : 스택이 비어있으면 true 아니면 false 반환 isFull() : 스택이 가득 차 있으면 true 아니면 false ..
[자료구조] 배열과 클래스 (Array & Class)
배열 (Array) 배열(Array)은 같은 자료형의 변수가 연속적인 형태로 구성된 구조이다. 각각의 원소에는 순서대로 index가 붙으며, 원소들이 연속적으로 배치되어 있기에 임의의 index에 접근(access)하는데 걸리는 시간복잡도는 O(1)이다. 따라서 배열은 임의 접근(Random Access)가 가능하다. 배열 ADT 객체 - 인덱스와 값 의 쌍으로 구성된 집합. 연산 - create(n) : n개의 요소를 가지는 배열 생성 - retrive(A, i) : A배열에서 i번째 index를 가지는 값 반환 - store(A, i, v) : A배열에 쌍을 삽입 C++에서의 배열 // 만약 배열이 없는 경우 int score1; int score2; ... int score10; // 배열 선언 i..