CS

큐 (Queue) 선입선출 FIFO(First In First Out)의 자료구조이다. 데이터가 들어오는 위치는 가장 뒤에 있고, 나가는 위치는 가장 앞에 있어서, 선입선출의 구조를 갖게된다. 즉, 먼저 들어온 데이터가 먼저 제거된다. 큐의 동작 1️⃣ Enqueue : 큐에 데이터를 추가한다. 큐가 꽉 차있을 때 Overfolw condition이 된다. 2️⃣ Dequeue : 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 빠져나온다. 큐가 비어져 있을 때는 Underflow condition이 된다. 3️⃣ Front : 큐의 앞부분의 데이터를 가진다. 4️⃣ Rear : 큐의 뒷부분의 데이터를 가진다. 큐의 종류 큐를 구현하기에 front(머리)와 rear(꼬리) 두가지 지표를 추적해야 한다..

스택(Stack)이란? 1️⃣ 스택은 뒤로 넣고 뒤만 뺄 수 있는 연결리스트이다. 2️⃣ 스택은 실행이 되는 특정한 순서를 따르는 선형적 데이터 구조이다. 두가지 순서로 동작한다. 1️⃣ LIFO(Last In First Out) : 후입선출 2️⃣ FILO(First In Last Out) : 선입 후출 JS에서는 pop()과 push() 메서드를 이용하면 된다. 중요한 포인트!!! 스택은 크기를 고정해서 사용하기 때문에, 고정된 크기의 스택에 데이터를 계속 넣게 되면 다른 메모리 영역을 침범한다. 이를 StackOverFlow라고 한다. 스택 메모리 영역은 프로그램이 자동으로 사용되는 임시 메모리 영역이다. (지역변수, 매개변수, 리턴 값 같이 잠시 사용되고 사라지는 데이터를 저장하는 영역) 프로세스..

자료구조란? 🔰자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다. 데이터(data)는? 1️⃣ 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. ◾이름, 나이, 키, 등 데이터로 분류가 가능하다. 2️⃣ 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다. ◾나이라는 데이터를 갖고있으면, 사람의 나이인지 동물의 나이인지 알 정보가 없다. 3️⃣ 데이터는 분석하고 정리하여 활용해야만 의미를 갖는다. ◾분석, 정리, 활용 4️⃣ 데이터는 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용한다. 5️⃣ 필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고, 활용해야 한다. 데이터를 체계적으로 정리하여 저장하면 데이터 활용에 있어 훨씬 유리하다. ..

탐욕법(그리디) 알고리즘 정의 현제 상황에서 가장 좋은 것 (최선의 선택)을 고르는 알고리즘 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안됨 최선의 결과를 선택해 나가지만, 최종 결과가 가장 좋은 결과라는 보장은 없다. 최선의 선택이란? 현제 상황에서 선택할 수 있는 것들 중 가장 좋은 것. 그리디 알고리즘 조건 탐욕스러운 선택 조건 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. '안전하다'란 이 선택으로 인해 전체 문제의 최적해를 반드시 도출 할 수 있어야 한다는 것이다. ➡그리디 문제가 나왔을 때, '이 조건이 만족하는 가?'를 생각해 충족하면 그리디 알고리즘을 사용한다. 최적 부분 구조 조건 문제에 대한 최종 해결 방법이 부분 문제에 대해서 최..

그래픽 탐색이란? 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지 너비 우선 탐색 (BFS, Bredth-First-Search) 정의 루트 노드(혹은 임의의 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점부터 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문하는 방법 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. 사용하는 곳 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때. 특징 1) 직관적이지 않은 점 - BFS는 시작 노드에서 거리에 따라 단계별로 탐색한다고 본다. 2) 재귀적인 동작을 하지 않는다. 3) 어떤 노드를 방문했는지 여부를 기록하여 무한루프에 빠질 위험을 제거 4) 방문..

깊이 우선 탐색 (DFS, Depth-First-Search) 정의 루트 노드 (혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 넓게 탐색하기 전에 깊게 탐색하는 것이다. 특징 1) 깊이 우선이 너비 우선(BFS)보다 간단하지만 느리다. 2) 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다. 3) 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 순회는 모두 DFS의 한 종류이다. 주의점 그래프 탐색의 경우 어떤 노드를 방문했는지 검사해야 무한루프에 빠질 위험이 없다. 동작원리 a노드(시작노드) 방문 - 방문을 표시한다 a와 인접한 노드들을 차례로 순회 - 인접한 노드가 없다면 종료 a와 이웃된 노드b를 방문했다..