분류 전체보기

[알고리즘] 다익스트라(Dijkstra) 알고리즘 : MinHeap 사용

다익스트라(Dijkstra) 알고리즘이란 무엇인지, 단순하게 MinHeap 구조 없이 구현하는 방법은 다익스트라(Dijkstra) 알고리즘이란?에서 확인할 수 있다. 위의 글의 소스코드 처럼 단순하게 다익스트라를 구현할 수 있지만, 이러한 경우 시간복도가 O(N^2)로 형성된다. 그러나 가장 저렴한(min값 인) 경유지를 선택할 때 다익스트라에 Min Heap을 사용하면, 성능을 더 높일 수 있고, 이때 시간복잡도가 O(NlogN)으로 형성된다. MinHeap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은, 즉 항상 가장 작은 값이 루트(root)에 존재하는 이진 트리이다. 실제로 여러 다익스트라 문제에서 MinHeap을 사용하지 않고 단순히 구현했을 때 시간 초과가 발생하는 경우를 직면할 ..

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 재귀호출 없이 다이나믹 프로그래밍을 이용하여 최단거리(최소비용)을 구하는 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. DP(Dynamic Programming)으로 분류되는 이유는 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 단, 음의 간선(가중치)이 있는 경우에는 사용할 수 없는 알고리즘이다. 다익스트라 알고리즘의 원리 다음과 같은 규칙을 반복하면 최소 비용을 구할 수 있다. 가장 저렴하게 갈 수 있는 곳을 경유지로 선택한다. 선택된 경유지를 거쳐 다른 곳으로 이동할 때, 더 저렴한 지 확인한다. 더 저렴하다면, 최소비용 전광판 result에 갱신한다. 다익스트라 알고리즘의..

(C++) 백준 1647 : 도시 분할 계획 (MST, Kruskal)

문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에..

[알고리즘] MST(최소신장트리), 크루스칼(Kruskal) 알고리즘이란?

✔️ MST란? MST는 Minimum Spanning Tree의 약자로, 그래프에서 최소 비용으로 모든 구간을 연결한 Tree(최소 신장 트리)를 말한다. 무향 연결 가중 그래프에서 간선의 가중치의 합이 최소인 신장(Spanning) 트리(Tree)이다. MST의 특징 MST는 Tree이기 때문에, Cycle이 존재하면 안된다. 따라서 신장 트리는 정점의 갯수가 n개일 때, 간선이 n-1개가 된다. 답은 여러개가 될 수도 있다. ✔️ 크루스칼(Kruskal)이란? 크루스칼(kruskal) 알고리즘은 MST를 구하는 대표적인 알고리즘이다. 크루스칼 알고리즘의 시간복잡도는 O(nlog𝑛)이다. 여기서 n은 연결되는 간선의 수를 의미한다. Kruskal 알고리즘의 과정 가중치 값을 기준으로 정렬(sort) ..

(C++) 프로그래머스 level3 : 정수 삼각형

문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 출처 : http..

[알고리즘] Union Find(서로소 집합)란?

✔️ Union Find란? Union Find(서로소 집합)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고할 수 있다. Union Find 자료구조를 사용하면 각 Data들이 같은 그룹에 속해있는지, 다른 그룹인지 확인할 수 있다. 즉 서로소 집합은 교집합이 공집합인 집합(서로 집합)들의 정보를 확인(Find)하고, 조작(Union)할 수 있는 자료구조이다. 그렇다면 왜 Union Find 자료구조를 사용할까❔ Data들이 어떤 조직에 속하는지 관리하기 쉬우며, 빠른 속도로 조직을 통합 처리 가능하다. ✔️ Union Find 자료구조의 조직 관리 방법 같은 트리에 묶여있으면 같은 그룹이라고 간주한다. 아래 트리에서 (A,B,C,D) (E,F,G) (H,I) 는 그룹이다...

(C++) 백준 1976 : 여행 가자 (feat. Union-find)

문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다. 입력 첫 줄에 도시의 수 N이..

(C++) 프로그래머스 level2 : 주차 요금 계산

문제 설명 ​ 주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다. 요금표 기본 시간(분) 기본 요금(원) 단위 시간(분) 단위 요금(원) 180 5000 10 600 입/출차 기록 시각(시:분) 차량 번호 내역 05:34 5961 입차 06:00 0000 입차 06:34 0000 출차 07:59 5961 출차 07:59 0148 입차 18:59 0000 입차 19:09 0148 출차 22:59 5961 입차 23:00 5961 출차 자동차별 주차 요금 차량 번호 누적 주차 시간(분) 주차 요금(원) 0000 34 + 300 = 334 5000 + ⌈(334 - 180) / 10⌉ x 600 = 14600 0..

(C++) 프로그래머스 level2 : n^2 배열 자르기

문제 설명 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. 1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. 2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 2-1. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다. 3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. 4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다. 정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해..

ArgoCD란? ArgoCD 개요 및 설치

GitOps GitOps는 DevOps의 실천 방법 중 하나로, 애플리케이션의 배포와 운영에 관련된 모든 요소들을 Git에서 관리(Operation) 한다는 뜻이다. GitOps는 Git Pull 요청을 사용하여 인프라 프로비저닝 및 배포를 자동으로 관리한다. Git 레포지토리에는 전체 시스템 상태가 포함되어 있어 시스템 상태의 변화 추이를 확인, 감사할 수 있다. GitOps의 원칙 모든 시스템은 선언적으로 선언되어야 한다. 시스템의 상태는 Git의 버전을 따라간다. 승인된 변화는 자동으로 시스템에 적용된다. 배포에 실패하면 이를 사용자에게 경고해야 한다. ArgoCD ArgoCD는 GitOps 방식으로 관리되는 Manifest(yaml) 파일의 변경사항을 감시하며, 현재 배포된 환경의 상태와 Gith..

[Kubernetes] AWS EKS : Cluster Autoscaling 및 Container Insights 설정

📌Index Cluster AutoScaling 수동 스케일링 자동 스케일링 CloudWatch Container Insight ✔️ Cluster AutoScaling Kubernetes의 Cluster Autoscaling Kubernetes는 Cluster AutoScaler를 통해 동적으로 인프라를 확장할 수 있다. Kubernetes Cluster Autoscaler는 Pod가 실패하거나 다른 노드로 다시 예약될 때 클러스터의 노드 수를 자동으로 조정하며, Pod의 리소스 요청에 따라 클러스터의 노드를 추가하거나 제거한다. 만약 리소스 부족으로 인해 스케줄링 대기 상태(Pending)의 Pod가 존재하는 경우 Cluster AutoScaler가 노드를 추가한다. 추가 시, 설정한 Min, Max..

[Kubernetes] k8s Monitoring : Metrics-Server

📌Index Metrics-Server란? Metrics-Server 설치하기 ✔️ Metrics-Server란? 쿠버네티스의 Metrics-Server는 각 노드에 설치된 kubelet을 통해 node 및 pod의 CPU, Memory의 사용량 Metric을 수집한다. 과거에는 Heapster를 사용했으나, 더 이상 개발되고 있지 않기 때문에(지원 중단) 이를 대체하는 Metrics-Server를 사용한다. Metrics-Server가 있어야 kubectl top 명령어를 사용하여 CPU/메모리 사용량 등을 확인할 수 있으며, HPA(Horizontal Pod Autoscaler) 및 VPA(Vertical Pod Autoscaler)을 사용할 수 있다. ✔️ Metrics-Server 설치하기 다음 ..