Computer Science
이번 내용은 데이터베이스를 왜 사용해야하는지에 대한 정말 기본적이면서도 가벼운 이야기이다. 딱히 어려운 내용도 없고 모르고 넘어가도 학습하는데 크게 지장이 없기 때문에 심심할 때 읽어보길 추천한다. 나중에 DB에 관련하여 학습을 다 하고 읽어보아도 좋은 내용이라고 생각한다. Why Databases? 현재 대부분 website들은 강력한 Database를 가지고 있다. 세계적인 기업 Google만 봐도 회원정보, 게시글 등 대부분의 정보는 데이터베이스를 통해 저장, 관리되고 있다. 최근에는 데이터의 양이 극도록 많아지면서 빅데이터 기반의 산업 또한 활발해지고 있다. 즉, 데이터를 어떻게 다루고 관리할 것인지에 대한 기술이 점점 중요해지고 있다. Data management Senario 여기서 한 가지 ..
All materials are copyrighted and licensed under MIT license. © Alexander Amini and Ava Amini MIT Introduction to Deep Learning IntroToDeepLearning.com MIT Deep Learning 6.S191 MIT's introductory course on deep learning methods and applications. introtodeeplearning.com 이 강의 자료에 대한 모든 저작권은 MIT 에 있으며, 관련 자료가 필요하신 분은 위 사이트로 들어가면 누구나 자료를 다운받을 수 있으니 참고하길 바란다. 시험기간 제외하고 일주일에 한 강좌씩 보는게 목표였는데 종프랑 여러 과제때..
Union Find 문제 상황 N개의 정점 ( 0 ~ V-1 ) 이 주어졌을 때 두 정점 a, b ( 0 ids[3] = 0 -> ids[0] = 0 == 0 (root = 0) 즉, 두 개의 root가 0으로 같으니 connected의 결과는 True이다. 핵심 알고리즘 1. 자료구조 정의 및 초기화 connected component를 tree 형태로 봄 ids[i] : 객체 i 의 parent ids[i] == i 이면 root root(i) = ids[ids[ ... ids[i] ...]] 2. union(a, b) root(a)를 root(b) 아래로 붙이기 3. connected(a, b) root(a) == root(b) : True else False 코드 # Quick Union V = ..
All materials are copyrighted and licensed under MIT license. © Alexander Amini and Ava Amini MIT Introduction to Deep Learning IntroToDeepLearning.com MIT Deep Learning 6.S191 MIT's introductory course on deep learning methods and applications. introtodeeplearning.com MIT에서 2023년 3월 10일부터 5월 12일까지 매주 아침 10시에 진행된 Introduction to Deep learning 강좌가 진행되었다. 이 강의는 매년 진행되는 것으로 보이고, 학교 교수님께서 혼자 인공지능을 더..
그리디 알고리즘에 해당하는 Scheduling 문제들에 대해 정리해보았다. Job Scheduling 문제는 크게 3가지 유형이 있다. Interval Scheduling Interval Partitioning Scheduling to Minimize Lateness Interval Scheduling 시작시간과 종료시간이 존재하는 job이 여러 개 있을 때 시간이 겹치는 job은 overlab될 수 없다. 이 때 최대로 실행할 수 있는 job subset을 구하는 문제이다. 이 문제에 대해서는 Greedy 알고리즘을 소개하면서 '활동 선택 문제' 라고 해서 설명한 적이 있다. 그렇기 때문에 아래 글을 참고하길 바란다. 2023.06.08 - [Computer Science/Data structure &..
2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] Minimum Spanning Tree - Kruskals [Algorithm] Minimum Spanning Tree - Kruskals Spanning Tree Spanning Tree는 어떤 그래프의 정점을 모두 포함한 가장 작은 subgraph를 의미한다. spanning tree를 찾는 가장 쉬운 방법은 DFS와 BFS를 이용하는 것이다. 2023.06.13 - [Computer Science/Data structure & Algo mobuk.tistory.com 위 글과 이어진 글이다. 먄약 MST가 무엇인지 궁금해서 들어왔다면 위 글을 참고하시길 바란다. Prim..
Spanning Tree Spanning Tree는 어떤 그래프의 정점을 모두 포함한 가장 작은 subgraph를 의미한다. spanning tree를 찾는 가장 쉬운 방법은 DFS와 BFS를 이용하는 것이다. 2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] BFS, DFS [Algorithm] BFS, DFS 그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 mobuk.tistory.com Minimum Spanning tree 모든 정점 사이의 비용 (weight) 이 있다고 해보..
https://www.acmicpc.net/problem/2150 문제 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다. 입력 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어..
Connected Components 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프이다. connected components는 단순히 연결되었는지 아닌지만 판단하면 되기 때문에 BFS나 DFS로 찾을 수 있다. ( Search가 가능하면 연결된거니까) 2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] BFS, DFS [Algorithm] BFS, DFS 그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 mobuk.tistory.com Strongly Connected..
그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 필수적으로 알고 있어야 하는 개념이다. 원래 귀찮아서 글을 안썼는데 알고리즘 시험 범위에 들어가있어서 이번 기회에 정리했다. BFS (Breadth First Search) 너비우선탐색 : 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법 Queue를 이용하여 구현한다. 과정 q와 visitied을 이용해 구현할 것이다. - q : 다음 방문할 노드를 담아두는 자료구조 - visited : 노드의 방문 여부를 기록해두는 곳 -> visited를 사용하지 않으면 무한 루프에 돌 수 있다. 시작 정점을 q에 삽입..
