Computer Science Basics

SWEA 기준Algorithm 총 17개Data Structure 총 10개목표 : 1월 12일까지 위 파트 숙지 및 각 항목별 중복 포함 문제 10개 이상씩 풀기 -> 최대 270문제DS : Stack, Queue, Linked List, Priority QueueA

왜 굳이 리턴값을 value라는 매개변수에 간접적으로 리턴하는가? 리턴값과 실제 데이터값을 분리하기 위함. 보통 pop이 불가능한 경우(stack이 비어있을 경우)에 -1같은 sentinel 값을 쓰긴 하지만, 실제로 -1이라는 값이 엄연히 사용되는 수일 수도 있다.

C++ 스타일로 Queue를 구현해보고, Java 스타일로도 구현해보면서Abstract Data Type이라는 게 무엇인지 더 감이 확실히 왔다.강의 자료에서 보면 Queue ADT는Data : 'stores sequence of ordered elements(?)'라

큰 문제를 같은 구조의 작은 문제로 쪼개서, 그 답을 저장해 두고 재활용한다!1\. 점화식(재귀 관계) 세우기. \- ex) dp\[i] = dp\[i-1] + dp\[i-2]2\. Memoization(저장) \- 이미 계산한 값은 배열이나 표에 저장. \- 다

이런 식으로 std::ios::sync_with_studio(false)와 std::cin.tie(nullptr)를 사용하면 잘 나온다.std::ios::sync_with_studio(false): C와 C++ 입출력 버퍼 동기화 해제 -> cin/cout 속도 향상.

Abstract Data TypeA mathematical model of the data objects that make up a data type as well as the functions that operate on these objects.Defined ind

rear(back)에서 Enqueue, front에서 Dequeue가 일어나는 ordered list.FIFO schemeTypically implemented with array or LLenqueue(Object) from rearObject dequeue() fr

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 ~ O(n^2)Best case : O(n) by flagWorst case : O(n^2)Average case : O(n^2)Best case : O(n^2)Worst case : O(n^2)Av

Strategy > - Break down into smaller problems > - Solve the smaller problems > - Combine results > - Recursive Sorting via divide-and-conquer Merge S

get(key)put(key, value)remove(key)size()isEmpty()entrySet()keySet()values()put : O(1), but if uniqueness needed, O(n).get, remove : O(n) in the worst

Divide the problem into a nnumber of subproblemsConquer the subproblems by solving them recursively. If the subproblem sizes are small enough, just so

.

A graph G = (V, E) : finite set of vertices V and finite set of edges E.V, E는 집합이므로 V에 속한 각 v와 E에 속한 각 e는 unique하다.Edge : (u, v), u와 v는 V에 속한 vertices

Vertices and edgesendVertices(e) : an array of two endvertices of e.opposite(v, e) : the vertex opposite of v on e.areAdjacent(v, w) : true if and onl

Subgraph that contains all vertices of the original graph and is a tree.즉, 기존 그래프의 모든 노드들을 최소한의 엣지로 연결한 그래프. 사이클 X.ST는 여러 그래프를 가질 수 있다.ST중에서 각 edge we

Find the shortest path from a starting vertex to all other vertices.The graph is connected.The edge weights are nonnegative.처음 노드에서부터 'cloud'(이미 start