감자튀김 공장🍟

빅 오 표기법의 정의 Big-O notation은 알고리즘의 시간 복잡도를 나타내는 표기법이며, O(f(n))으로 나타낸다. 그런데 여기서 시간 복잡도란 무엇일까? 시간 복잡도 알고리즘 분석에서는 2가지의 측면을 고려할 수 있다. 알고리즘의 수행시간과 알고리즘이 필요로 하는 기억 공간의 양이 그것이다. 알고리즘 수행 시간 분석을 시간 복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도(space complexity)라고 한다. 대게 알고리즘이 차지하는 공간보다 수행 시간에 더 관심이 있기 때문에 알고리즘의 복잡도는 대게 시간 복잡도를 말한다. 시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라(000ms) 알고리즘을 이루고 있는 연산들이 몇 번..

삽입 정렬 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입한다. 삽입 정렬의 과정 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드를 기존의 카드 사이의 올바른 자리를 찾아 삽입 하는데 그 경우와 똑같다고 생각하면 된다. 구현 코드 #include using namespace std; void insertionSort(int arr[], int len) { int i, j, temp; for (i = 1; i = 0; j--) { if (arr[j] < ..

연결 리스트 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked List)라고 한다. 연결 리스트는 배열의 단점을 보완하고자 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 연결 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 3가지 종류의 연결 리스트가 있다 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트 단순 연결 리스트 구현 구조 typedef struct ListNode { int data; struct ListNode* next; } ListNode; ​ 구조체 내부에 데이터를 저장하는 dat..

트리(Tree) 트리는 계층적인 자료를 표현하는데 적합한 자료구조이다. 데이터의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다. 트리의 용어 노드 (Node): 트리를 구성하고 있는 각 요소 ex) A, B, C ... J, K 간선 (Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node: 최상위 계층에 존재하는 노드 ex) A Level: 트리의 특정 깊이를 가지는 노드의 집합 ex) A의 level은 1, E의 level은 3 차수 (Degree): 어떤 노드가 가지고 있는 자식 노드의 개수 ex) B의 차수는 2, D의 차수는 3 깊이 (Depth, Height): 어떤 트리에서 노드가 가질 수 있는 최대의 레벨 ex) 위의 트리에서 깊이는 4 단말 노드(..

큐의 구조 큐의 특징 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다. FIFO(First-In First-Out): 먼저 들어온 데이터가 먼저 나가는 구조이다 A -> B -> C -> D의 순서로 큐에 삽입되었을 때 삭제 순서는 A -> B -> C -> D 이다. 큐에서 삽입이 일어나는 곳을 후단(Rear)라고 하며 삭제가 일어나는 곳을 전단(Front)라 한다. 스택과 다른 점은 삽입과 삭제가 다른 쪽에서 일어난다는 점이다. 큐의 연산 push(): 큐에 원소를 추가(rear) pop(): 큐에 있는 원소를 삭제(front) front(): 큐 제일 앞에 있는 원소를 반환 back(): 큐 제일 뒤에 있는 원소를 반환 empty(): 큐가 비어 있으면 tr..

스택의 구조 스택의 특징 스택의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. LIFO (Last-In-Fisrt-Out)의 형태를 가지고 있다. A -> B -> C -> D의 순서로 스택에 삽입되었을 경우 삭제 순서는 D -> C -> B -> A가 된다. 스택의 가장 위를 top이라고 하며 top 에서 삽입과 삭제가 이루어진다. 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다. 스택의 연산 push: 스택에 새로운 원소를 삽입 pop: 스택의 top 원소를 제거하고 반환 empty: 스택이 비어있는지 검사 size: 스택의 크기 swap: 두 스택의 내용을 바꿈 top: top에 있는 원소를 반환 스택 구현 코드 #include ..