Computer Science
-
리액트(React.js) 개요Computer Science/React 2021. 2. 17. 11:50
1. 리액트의 아이디어 대규모 애플리케이션 중 프론트엔드 사이드에서 돌아가는 애플리케이션 구조를 관리하려면, 순수 자바스크립트로만 하기에는 다소 골치 아프다. 여러 프레임워크들이 이를 저마다의 관점에서 해결하려고 했고, 이들은 MVC, MVVM, MVW 등과 같은 여러 아키텍쳐들을 제시해왔다. 이들이 공통적으로 가진 것은 모델과 뷰. 모델은 애플리케이션의 데이터를 관리하는 영역이고, 뷰는 데이터를 기반으로 사용자에게 보이는 부분이다. 모델 데이터가 조회/수정되면, 변경 사항이 뷰에 반영되는 식이다. 업데이트하는 항목에 따라 어떤 부분을 찾아서 변경하는 작업은 간단한 듯하지만, 규모가 커지면 상당히 복잡해지면서 제대로 관리하지 못하면 성능이 떨어질 수 있다. 리액트를 개발한 페이스북 개발팀이 고안해낸 아이..
-
힙(heap)의 삽입과 삭제Computer Science/자료구조&알고리즘 2021. 2. 16. 17:27
힙(heap)의 삽입과 삭제 최대 힙을 기준으로 설명한다. 힙의 삽입 힙은 배열로 구현된 완전 이진 트리이다. 배열의 끝 인덱스부터 시작하여, 그 부모 노드와 비교하며 해당 노드보다 키 값이 더 크면 부모 노드의 인덱스를 증가시키는(트리에서 밑으로 끌어내리는) 과정을 키 값이 더 큰 부모 노드를 만날 때까지만 반복한다. 반복이 끝나면 현재 인덱스의 원소에 삽입할 키 값을 대입하고 힙의 삽입 과정이 종료된다. 수도코드 insert_max_heap(heap h, int item){ int i = ++(h.size); while(i > 0 && h[i/2]
-
BFS (Breadth First Search) : 너비 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:12
BFS, 너비 우선 탐색이란, 그래프 상에 존재하는 정점을 방문할 때마다 그 다음으로 주변의 인접한 정점들을 우선적으로 탐색해나가는 탐색 방법을 말한다. 반복문과 큐를 이용하여 구현할 수 있다. 수도코드 bfs(int i){ queue q; q.push(i); visited[i] = true; while(!q.empty()){ int v = q.pop(); for(i in adjacent vertices of v){ if(!visited[i]){ q.push(i); visited[i] = true; } } } } 노드를 방문할 때마다 방문하지 않은 주변 노드들이 큐에 들어간다. 큐에 한번 들어가는 순간 방문이 예정되어 있으므로 방문 표시를 한다. (그래야 중복 방문이 제대로 방지된다.) 큐에 들어간 순서..
-
DFS (Depth First Search) : 깊이 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:01
DFS, 깊이 우선 탐색이란, 그래프 상에 존재하는 정점에서 인접한 정점 중에 방문하지 않은 정점이 없을 때까지 계속 인접한 다른 임의의 정점으로 이동하며 탐색한다. 인접한 정점 중에 방문하지 않은 정점이 없으면 이전 정점으로 이동한 뒤 다른 정점으로 이동하는 과정을 반복한다. 구현 방법은 재귀함수를 이용한 것과, 반복문과 스택을 이용한 것으로 2가지가 있다. 수도코드 - 재귀함수로 구현 dfs(int v){ visited[v] = true; for(u in adjacent vertices of v){ if(!visited[u]){ dfs(u); } } } 인접한 노드를 하나씩 연이어서 계속 방문한다. 그러다가 방문할 노드가 없으면 이전 노드의 인접 노드를 탐색하게 된다. 수도코드 - 반복문과 스택으로 ..
-
그래프Computer Science/자료구조&알고리즘 2021. 2. 13. 21:41
그래프 : 정점(Vertex)과 간선(Edge)의 집합. 트리는 사이클이 허용되지 않는 일종의 그래프이다. Undirected Graph : 간선이 방향을 갖지 않는 그래프. 무향 그래프. Directed Graph (Digraph) : 간선이 방향을 갖는 그래프. 유향 그래프. Degree (차수) : 각 정점에 연결된 간선의 개수 Outdegree : 유향 그래프에서 정점으로부터 밖으로 나가는 간선의 개수 Indegree : 유향 그래프에서 정점으로 들어가는 간선의 개수 가중치 그래프(Weight Graph) : 간선에 가중치 정보를 둔 그래프. 부분 그래프(Sub Graph) : 어떤 그래프의 부분집합에 해당하는 그래프 (해당 그래프의 정점과 간선들 중 일부만 가지고 있는 그래프) 그래프의 구현 방..
-
자료구조 기초 정리 (시간 복잡도, 추상 데이터 타입, 선형 자료구조, 트리)Computer Science/자료구조&알고리즘 2021. 2. 13. 16:13
시간 복잡도 : 인스턴스에 따른 실행 시간 변화 추이를 나타내는 척도 추상 데이터 타입 (ADT) : 자료구조의 명세서, 사용 설명서 같은 것. 데이터가 저장되는 방식과 데이터의 인터페이스 역할을 하는 메소드들의 정의로 이루어져 있다. 배열(Array) : 탐색 시간이 O(1)이지만, 삽입과 삭제가 worst case의 경우 O(n)이다. 링크드 리스트(Linked List) : 삽입과 삭제 시간이 O(1)이지만, 탐색 시간이 worst case의 경우 O(n)이다. 스택과 큐 : 둘 다 선형 자료구조이다. 스택(Stack) : LIFO(Last In First Out) 방식의 자료구조. 큐(Queue) : FIFO(First In First Out) 방식의 자료구조. 트리(Tree) : 비선형 자료구조..