![]()
국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 String Matching 문서에서 단어를 빠르게 찾으려면? 문서에서 특정 단어를 검색해서 찾는 경우가 종종 있을텐데 이때 찾으려는 단어를 pattern이라 함 이렇게 문서에서 단어를 찾을 때 빠르게 찾으려면 어떤 방법을 써야할지에 대한 알고리즘임 Problem Definition 입력은 길이 n인 문서 문자열 A, 길이 m인 패턴 문자열 P 가 주어지고 보통 n이 m보다 훨씬 큰 상황임 이때 출력은 패턴 문자열과 일치하는 A의 부분 문자열(sub-string) 위치를 출력하게됨 Naive Algorithm 문서 A의 모든 부분 문자열을 순차적으로 패턴 P에 매치해보는 알고리즘을..
![]()
국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Topological Sorting 위상정렬이란 작업들의 선후 관계를 방향 그래프로 표현할 때 선후 관계를 어기지 않도록 정점을 정렬하는 것임 => 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 앞에 위치하도록 정렬 대상이 directed graph로 cycle이 없어야함!= DAG Kahn's Algorithm 아이디어는 진입 간선이 없는 정점을 앞에 두는 것임 순서를 살펴보면 1. 진입 간선이 없는 정점을 골라 리스트에 넣음2. 고른 정점을 제거하고, 연결된 간선도 제거함모든 정점이 제거될 때까지 위 과정을 반복 Implementation Details pseudo co..
![]()
국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Shortest Paths Shortest Paths란 말 그대로 두 점 사이의 최단 경로임 => 두 점 사이의 경로 중 비용이 최소인 경로(경로 내 간선들의 비용 합) Single Source Shortest Paths 그럼 이번 포스팅의 주제인 Single Source Shortest Paths는 뭘까? 이는 한 점과 다른 모든 점 사이의 최단 경로를 의미함 => 시작 정점 (source node) s에서 다른 모든 점까지의 최단 경로 찾기가 곧, s가 root인 shortest-path tree 찾기임(일종의 spanning tree라고 볼 수 있음) Dijkstra's Al..
![]()
Kubernetes란? Google이 만든 Container Ochestration을 하기 위한 도구임 Container Ochestration이란? Container를 자동으로 관리해줌=> 중앙에서 관리Cluster 차원으로 관리일반 Docker만 사용하는 것과 다르게 확장의 용이성을 제공해주고 여러 서버를 동시에 관리할 수 있음Kubernetes가 제공해주는 가치? 관리 측면에서 여러가지를 자동으로 관리해주고, 추상화된 개념에서 접근하기에 훨씬 편함=> 대규모 환경 관리배포같은 것들도 매우 편리하고 합리적으로 해줌 Kubernetes 컴포넌트 쿠버네티스 Cluster는 컴퓨터 집합인 Node와 Control Plain 으로 구성됨 우선 Node는 두 가지 종류가 있음Master Node Clust..
![]()
국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Minimum Spanning Trees Spanning Tree란 그래프 G = (V, E)에서 간선을 |V| - 1 개만 남겨 트리가 되도록 만든 것 Minimm Spanning Tree란 Spanning Tree 중에서 edge weight의 합이 가장 작은 것=> 한 그래프에 여러개의 MST가 존재할 수 있음 어떻게 MST를 구할까..? Naive Solution을 생각해보면 모든 subgraph를 살펴보고, 그 중에서 spanning tree이면서 weight의 합이 가장 작은 것을 찾으면됨 => subgraph의 수는 각각의 edge가 있냐 없냐에 따라 결정되므로 2^|E..
![]()
국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Disjoint Sets Disjoint Sets란 서로 겹치지 않는 집합들을 의미함 => 어쩌피 교집합이 공집합이므로 intersect 연산은 따로 존재 X ∴ Disjoint Set 연산에는 make-set(u) : u를 유일한 원소로 갖는 집합 생성find-set(u) : u가 속한 집합 리턴union(u, v) : u가 속한 집합과 v가 속한 집합을 합침 https://www.acmicpc.net/problem/1717 집합의 표현 이라는 백준 문제를 Disjoint Set 연산으로 해결하는 코드를 살펴보자 python의 set을 쓴다면 union(u, v)를 할 때 u, ..
![]()
국민대학교에서 "클라우드 컴퓨팅" 교과목을 진행하시는이경용 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 시스템 가상화 기술 Virtual Machine Hypervisor (Virtual Machine Monitor)를 통한 여러 운영체제간 독립적 환경 제공각 VM은 독립적인 별도의 커널(운영체제), 시스템 프로세스 등을 관리하게됨=> 추가 오버헤드가 클 수 있음각각의 VM은 별도의 커널을 가질 수 있기에, 서로 다른 운영체제의 동시 동작 가능VMM을 통한 자원 공유로 인해 VM 간 간섭은 덜하지만 오버헤드가 있어 monolithic 구조에 적합Container Technologies Container 호스트 운영체제내에서 동작하며 커널 및 많은 시스템 자원을 호스트 기기와 공유극단적으..
![]()
국민대학교에서 "클라우드 컴퓨팅" 교과목을 진행하시는이경용 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Monolithic Application and Microservice Application Monolithic application 하나의 서버에서 다른 목적을 가지는 여러 프로세스가 동작서버의 용량이 커야 할 필요가 있음 (서비스 종류의 확장 보장)Scale-up 접근이 적당한 경우가 많음=> 하나의 서버에서 동작하므로Scale-out은 불가능한 경우가 많음=> 일부의 모듈이 수평확장을 지원하지 않을 경우 (ex. 데이터베이스)데이터 일관성, 무결성, 트랜잭션 처리(ACID 규칙) 등이 일반적인 RDBMS에서 매우 중요한 요소로 작용하기 때문에 DB는 본질적으로는 Scale-out ..
![]()
국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Greedy Algorithm 개요 Algorithmic Paradigms Brute-force methods=> 가능한 모든 경우를 살펴보기Divide and conquer=> 문제를 작은 문제로 분할하여 재귀적으로 해결Dynamic programming=> 작은 문제의 결과를 메모해두고 재활용오늘 다룰 주제는 Greedy algorithms 임! Greedy Strategy 지금 당장 가장 좋아보이는 것을 선택하는 전략임 => 미래의 상황은 고려하지 않음Greedy Algorithm 이란 최적해를 항상 보장하지는 않음현재의 선택이 미래에 미칠 영향을 고려하지 않기 때문에Loca..
![]()
국민대학교에서 "클라우드 컴퓨팅" 교과목을 진행하시는이경용 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 구동중인 서버에 문제 발생 시 해결 방안 => 가능한 모든 곳에서 자원의 시작, 종료, 설정을 자동화를 하는 것을 권장 수동으로 관리되는 자원들을 줄임으로 시스템의 안정성, 일관성, 효율성을 높이도록 해야함 DevOps Development : 서비스 개발 Operations : 서비스 운용 클라우드 서비스의 등장 및 웹 서비스 보편화에 따른 Development와 Operations의 경계 모호 웹 서비스의 빠른 개선 주기로 인한 간단한 릴리즈 사이클 필요=> 코드를 활용한 서비스 배포 보편화 (IaC) Infrastructure-as-Code (코드를 이용한 자원 관리) 서비..
![]()
국민대학교에서 "클라우드 컴퓨팅" 교과목을 진행하시는이경용 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 AWS High Availability (고가용성) Fault-tolerance와 Scalability 관점에서 살펴보자 고가용성 (High Availability)란? 서비스를 운용하는 사람이 관리를 하지 않아도 서비스가 동작하지 않는 시간을 최소화해서 사용자에게 예측된 성능을 제공해줄 수 있는 척도 고가용성의 구현 요소들 Fault tolerance 응용예제 자체에서 문제가 발생시에도 사용자에게 영향을 전파하지 않는 능력=> fault가 failure가 되지 않게백업 서버의 구동 등 Scalability 시스템의 디자인을 바꾸지 않고도 증가하는 요청을 처리할 수 있는 능력 사용자 ..
![]()
국민대학교에서 "클라우드 컴퓨팅" 교과목을 진행하시는이경용 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 AWS의 Region들 us-west-2, ap-southeast-1 처럼 되어 있는 것을 볼 수 있음 => 보통은 숫자 1로 갈수록 큰 도시를 의미하며 주요 Region부터 기능이 배포됨 AWS에서 Region을 선택할 때 고려 사항들 법률적 제약 사항=> 특정 데이터는 본국을 떠나서는 안됨 등의 제약 사항 고려주요 사용자와 가까운 곳에 위치=> 응답시간 측면에서 바라봐야함지역별로 가용한 서비스가 다름=> 주로 미국 서부(us-west-2) 및 동부 (us-east-1) Region 부터 새로운 서비스가 가능해짐Region 별로 가격이 다름=> 데이터센터의 장비 가격등을 고려해보면..
