cs

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

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

그래픽 탐색이란? 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것 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를 방문했다..