프로그래밍 썸네일형 리스트형 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)와 Kruskal, Prim 알고리즘 Spanning Tree (신장 트리) 란? Spanning Tree (신장 트리)란 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리이다. 무방향 그래프란 방향성이 없는 그래프로 그림상에서 화살표가 아닌 실선으로 이루어진 그래프를 뜻한다. 즉, Spanning Tree는 최소의 간선을 이용하여 모든 정점을 연결한 그래프이다. 너비 우선 탐색을 이용하여 생성된 신장 트리를 BFS (Breath First Spanning tree, 너비 우선 신장 트리)라고 하고, 깊이 우선 탐색을 이용해 생성된 신장 트리를 DFS (Depth First Spanning tree, 깊이 우선 신장 트리)라고 한다. Spanning tree는 최소의 도로를 이용한 도로망 건설이나 최소의 네트워크선을 이.. 더보기 [AWS] EC2 사용자 데이터를 사용하여 웹서버 구동 간단 테스트해보기 AWS에서 VPC 구성을 하며 해당 EC2가 정말로 외부 접속이 불가능한지 테스트해보고 싶어졌다. EC2를 만들고 시험 삼아 웹서버를 구성해 직접 접속해보고자 할 때 가장 간단한 방법을 소개한다. 바로 EC2에서 제공하는 사용자 데이터를 활용하는 방법이다. 사용자데이터는 인스턴스를 시작할 때 자동으로 실행하는 일종의 Script이다. 인스턴스를 재부팅하는 경우가 잦은 경우 필요한 명령어를 입력해두는 용도로 사용해도 좋다. 먼저 AMI는 Amazon Linux 2 를 사용했다. 나머지 설정을 완료한 이후 고급 세부 정보 탭을 열어보면 사용자 데이터 폼이 있다. 사용자 데이터에 아래의 코드를 입력한다. #!/bin/bash yum install httpd -y service httpd start 이렇게하면 .. 더보기 [스프링 부트] 개발환경 구성 1. JDK 설치 터미널을 열어 아래의 명령어를 입력한다. java -version 만약 위와 같이 나오면 아직 JDK가 설치가 되어있지 않은 것이다. JDK를 설치하기 위해서는 먼저 아래의 주소에 들어가 https://adoptopenjdk.net/ AdoptOpenJDK AdoptOpenJDK provides prebuilt OpenJDK binaries from a fully open source set of build scripts and infrastructure. Supported platforms include Linux, macOS, Windows, ARM, Solaris, and AIX. adoptopenjdk.net 아래와 같이 원하는 OpenJDK 버전과 JVM을 선택한 후 본인의 O.. 더보기 서비스별 클라우드 서버 평생 무료, 크레딧 제공 정리 토이 프로젝트 등 개발을 하다 보면 배포와 테스트를 위해 라이트 한 서버가 필요한 경우들이 생긴다. 가볍게 사용하는 용도에서 돈을 내고 서버를 구성하기에는 아까운 마음이 든다. 이번 기회에 무료로 사용할 수 있는 클라우드 서버들을 정리해 보았다. 본인의 환경에 맞추어 잘 활용하면 좋을듯하다. (개인적으로 무료 제공량은 오라클이 넘사벽인 것 같다!) 평생 완전 무료 GCP 무료 리소스: f1-micro (1 vCPU, 614M RAM, 30GB 디스크, 1G 트래픽) 오라클 클라우드 무료 리소스: VM.Standard.E2.1.Micro (AMD 프로세서, OCPU1개, 1GB RAM, 100GB 스토리지, 고정 IP 무료 제공, 0.48 Gbps Network bandwidth) 무료 사용 VM 개수: .. 더보기 [용어-AWS] 고가용성과 내결함성의 차이 1. 고가용성 사람이 개입하지 않아도 전체 시스템이 항상 작동하고 액세스를 가능하게 하는것으로 가동 중지를 최소화하도록 보장하는것이다. 대표적인 AWS의 서비스들로는 ELB, Auto Scaling, EIP, Route53, 다중 AZ 등이 있다. 2. 내결함성 애플리케이션 관점에서 시스템의 일부 구성요소에 장애가 있어도 계속 작동할 수 있도록 하는것이다. 대표적인 AWS의 서비스들로는 S3, RDS, SQS 등이 있다. 더보기 [용어] Fault와 Failure의 차이 1. Fault: 결함 defect나 bug라고도 하며 인간의 실수가 sotware에 포함된 것이다. 2. Failure: 고장, 장애, 실패 프로그램 수행 중 회복할 수 없는 오류가 발생하여 의도한 수행을 계속할 수 없는 상태를 나타내는 말이다. 잘못된 input이 들어올 때 fault가 failure이 원인이 되기도 한다. 이번 카카오 사태를 빗대어 설명해보자면 데이터 센터에 불이나 전력이 차단된 것은 Fault(결함)이지만, 이에 대비하지 못해 서버가 바로 다운되어버린 상황을 Failure(장애)라고 할 수 있을 것이다. 현재 티스토리 관리페이지 상단에 해당 사태에 대한 사과 공지가 있는데 카카오 측에서도 "장애"로 표현하고 있음을 알 수 있다. 더보기 [알고리즘] Stable sorting algorithm, In-Place algorithm Stable Sorting Algorithm (안정 정렬 알고리) - 크기가 같은 데이터가 정렬된 이후에도 입력된 순서를 그대로 유지하게 하는 정렬 알고리즘이다. Stable Sorting Algorithm Bubble Sort Insertion Sort Cocktail Shaker Merge Sort Unstable Sorting Algorithm Selection sort Heap Sort Shell Sort Quick Sort Exchange Comb In-place Algorithm - 입력 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요한 알고리즘이다. - 정렬을 하는 과정에서 추가적인 메모리 공간이 "거의" 안든다고 생각하면 쉽다. - Quick Sort의 경우는 정의에 따라서 No.. 더보기 정렬 알고리즘 총정리 1. Bubble Sort (버블 정렬) 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도는 O(n^{2})로 매우 느리다. (효율성은 나쁘지만 코드가 단순하기 때문에 교육용으로(?) 자주 사용되는 것 같다.) Stable 하고 In-place 하다. (https://blog.wookingwoo.com/27 참고) 이미지 출처: https://www.cs.mtsu.edu/~xyang/2170/bubbleSort.html Bubble Sort Complexity Average (평균 시간복잡도) O(n^2) Best Case (최선 시간복잡도) O(n) Worst Case (최악 시간복잡도) O(n^2) Space Complexity (공간복잡도) O(1) C++ 코드 예시 void swap(in.. 더보기 이전 1 2 3 다음
