감자튀김 공장🍟

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

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

순회 이진 트리에서 데이터를 탐색하는 방법은 크게 세 가지 방법이 있다. 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal) 전위 순회 전위 순회는 Root를 제일 먼저 처리합니다. 순서 Root (자기 자신) 왼쪽 자식 오른쪽 자식 위의 트리에서 전위 순회로 순회를 한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서입니다. 중위 순회 중위 순회는 Root를 가운데 순번에서 처리합니다. 순서 왼쪽 자식 Root (자기 자신) 오른쪽 자식 위의 트리에서 중위 순회로 순회를 한다면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 순서입니다. 후위 순회 후위 순회는 Root를 가장 마지막에서 ..

트리(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 ..