🙋🏻 DFS를 사용하는 이유DFS는 미로 탐색과 같이 목표 노드가 멀리 떨어져 있다는 가정이 존재할 때, BFS보다 유리하다. 1. 메모리 사용량이 BFS보다 적다.한 경로의 탐색이 완전히 끝날 때까지 다른 경로상의 노드가 비교적 추가되지 않기 때문에같은 거리상의 모든 노드를 큐에 저장해두는 BFS보다 메모리 사용량이 비교적 적다. 2. 경로 탐색에 유리하다.BFS의 경우 같은 거리에 위치한 모든 경로를 점진적으로 탐색하지만,DFS의 경우 각 경로를 끝까지 탐색하다가 목표를 찾을 경우 즉시 종료하기 때문에멀리 떨어진 목표까지의 경로 탐색에 유리하다. ⭕️ 1240번 : 노드사이의 거리 (골드5)문제 유형 : tree, graph, dfs, bfs시간 복잡도 : O(n)풀이 방식 :- 트리 형태를 띄고..

⭕️ 16236번 : 아기 상어 (골드3)문제 유형 : graphs, bfs, implementation, simulation시간 복잡도 : O(n^2)풀이 방식 :- 상어가 먹을 수 있는 물고기들을 선택할 때 가장 가까운 거리에 위치한 물고기 중 선택해야하기 때문에 bfs를 이용- 거리가 같은 물고기일 경우 가장 왼쪽에 위치한 물고기, 왼쪽 거리도 같다면 가작 위쪽에 위치한 물고기를 선택해야하기 때문에 이에 맞게 우선순위큐의 compare 조건을 지정- 떨어진 거리가 물고기들만 우선순위 큐에 들어가야하기 때문에 현재 큐의 크기만큼만 빼내어 탐색- 거리 1당 시간이 1씩 걸리기 때문에 선택한 물고기로 이동할 때마다 떨어진 거리(물고기까지의 bfs시행 횟수)만큼 더하여 총 이동 시간을 구한다 ❌ 2206..

알고리즘 문제 중 그래프 탐색 문제, 그 중에서도 BFS 문제 풀이를 가장 좋아한다. 그래서 그런지 골드 문제 풀이 비중도 BFS가 가장 높고,나중에는 연속 문제풀이를 유지하기 위해 그래프 문제를 빠르게 해치웠었다. DFS로 풀 수 있는 문제도 항상 BFS로 풀어서 코멘트를 남긴 문제가 꽤 많기 때문에,골드4~5와 골드1~3으로 나눠서 정리해보겠다. 🙋🏻 BFS를 사용하는 이유최소거리, 최소시간 등을 구해야하는 문제에 사용한다.  Queue를 사용하여 구현하기 때문에 항상 거리(시간)이 똑같은 케이스들이 먼저 나온다는 점이 핵심이다. 이러한 특징 때문에 조건에 맞는 첫 케이스가 항상 최소 거리(시간)임을 확정할 수 있어 사용한다.  ⭕️ 7576번 : 토마토 (골드5)문제 유형 : graphs, bf..

MSA 수강신청 프로젝트를 진행할 때,시스템 가용성을 유지하기 위해 오토 스케일링을 적용해보게 되었다.(애초에 오토 스케일링을 위해 MSA로 배포했다) 쿠버네티스는 Load Balancing, Persistance Volume 등 오케스트레이션에 도움이 되는 기능들을 제공한다. 이번에는 그 중 Horizontal Pod Autoscaler(HPA)를 사용했다.  HPAHPA는 CPU, Memory와 같은 리소스 사용량에 따라 Pod의 개수를 조절하는 기능이다. 제한 리소스량을 yaml 파일을 통해 지정하면 해당 제한을 넘칠 경우 Pod이 늘어나고,다시 제한 아래로 일정시간 내려갈 경우 Pod이 줄어든다.(트래픽 분산의 경우 알아서 일어난다) 실제 사용했던 yaml 파일을 살펴보자.apiVersion: a..

개요과거 진행한 프로젝트에서 최적화를 진행했는데,관련 내용을 기록해두지 않은게 생각났다. 프로젝트에서 스크린샷 수집을 위해 셀레니움을 활용했었다. 매 요청 당 최대 1000개씩 발생하기도 하는데,드라이버 하나로 스크린샷 1000개를 생성하다니 수집률이 너무 떨어졌었다. 이런 이유로 멀티 스레딩을 활용한 병렬 처리가 필수적이었는데,각 스레드에서 크롬 드라이버를 '열고 캡쳐하고 닫고'를 하자니 오버헤드가 너무 컸다. 이 문제를 전공 지식을 활용해 해결한 것에 대한 내용이다.  파이썬 멀티 스레딩을 사용해보자!파이썬 multiprocessing.pool 라이브러리의 ThreadPool 이용했다. 사용 이유:1) Multi Threading 지원2) Thread 개수 지정 가능 (Chrome Driver는 CP..

기본적으로 Envoy AccessLog는 IP주소를 기반으로 생성된다. 한 번의 통신이 발생 했을 때 통신의 주체의 각 Envoy가 로그를 생성하기 때문에 2개의 로그가 만들어진다. 이때 생성 된 로그의 IP 주소가 깔끔하게 나오는 게 아니라 매우 난해하게 생성된다. 로그 내 필드와 실제 로그를 분석해 보면서 알게 된 Upstream, DownStream에 대해 정리해보겠다. UpStream? DownStream?두 개념은 트래픽의 방향성이 중요하다. 일반적으로UpStream이란 클라이언트에서 목적지로의 데이터 트래픽을 의미하고,Outbound는 서버에서 요청지로 보내는 데이터 트래픽을 의미한다. Envoy에서는UpStream이란 Envoy에게 요청을 받고, 응답을 보내주는 호스트 즉, 서버를 의미하고,..

로그와 매트릭을 수집하는 Pod에 문제가 발생하여 스트림이 끊긴 이후에Pod이 회복되면 알아서 스트림을 다시 연결하고 전송하는 것을 본 경험이 있다. 내가 경험하기론 재연결 로직을 따로 구현하지 않으면 스트림을 다시 열지 않았기 때문에Envoy Proxy는 어떻게 구현되어 있을 지 궁금해졌다.(참고로, Stream의 경우 연결이 끊어진 순간 사라지기 때문에 재사용이 불가능하다고 한다)  먼저, Envoy Proxy의 AccessLogs 패키지 문서를 봤다.(https://pkg.go.dev/github.com/envoyproxy/go-control-plane/envoy/service/accesslog/v3) 재연결의 경우 클라이언트 측에서 시도할 것이기 때문에 클라이언트 코드를 주로 살펴봤다. Envoy..

저번 글에서 gRPC를 이용해 Envoy Proxy의 로그 및 매트릭을 전송 받는 기반을 다졌다. 이제 길을 닦아놨기 때문에 당연히 문을 열어야 된다. Envoy Proxy가 gRPC 클라이언트 입장이기 때문에 서버를 구성해야 했다. go언어로 AccessLog서버를 구성해봤다. 먼저 protobuf와 서비스 정의를 필요하기 때문에 공식 패키지를 임포트했다."github.com/envoyproxy/go-control-plane/envoy/service/accesslog/v3"(accesslogs로 alias했다) gRPC 구성 과정추후 정리할 예정이지만, 간단하게 과정을 살펴보자면1. tcp 리스너 생성2. gRPC 서버, gRCP 서비스 생성3. gRPC 서버에 서비스 등록 (컴파일된 protobuf ..