본문 바로가기

전체 글176

(24.11.25) DP(Dynamic Programming) 과 전체탐색(BFS, DFS)에 대한 정리 DP(Dynamic Programming)은 간단하게 부분합을 사용해서 전체 합을 구하는 알고리즘이라고 넘어갔지만, 계속해서 찾아보고 알고리즘 문제를 풀어보면서  BFS와 DFS와의 구분이 애매한 것 같아서 스스로 구분하고적절하게 알고리즘을 사용하기 위해서 정리했다. 예제는 GPT를 활용해서 가장 많이 사용하는 경우를 간단하게 정리했다.DP(Dynamic Programming) & 전체 탐색DP 알고리즘모든 경로에 대해서 계산을 통해서 **“최적의 값”**을 찾기위해서 진행하는 알고리즘아무리 그 경로가 복잡하더라도 그 순서나 관련된 내용은 체크할 필요가 없이 “최적의 값” 을 향해 나가는 방식에 사용메모이제이션(Memoization) & 타뷸레이션(Tabulation)재귀를 통한 값을 캐싱하면서, 표로 .. 2024. 11. 25.
(24.11.18) BFS를 활용한 도현의 외각선 탐색 도형의 외곽선 탐색하기 알고리즘도형의 외곽선을 탐색하면서 가장 짧은 거리를 반환하는 알고리즘내부로 진입 Ximport java.util.*;class Solution { // 방향키 public int[] dx = {-1,1,0,0}; public int[] dy = {0,0,-1,1}; public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { // 영역 지정 2배 확장 int[][] map = new int[101][101]; // 주어진 사각형 외각선 1 내부 2 설정하기 for(in.. 2024. 11. 18.
(24.11.11) BFS를 활용한 미로 최단 거리 찾기 가중치가 없는 그래프일 경우 Map> 자료구조의 graph로 BFS를 노드 단위, 또는 neighbor 단위로 활용할 수 있다. 하지만, 미로에서는 가중치가 1인 그래프에 특정 조건(막혀있을 경우 해당 경로는 X)이 있기 떄문에복잡할 수 있는 BFS 내지는 아래 비교를 위한 DFS를 좀더 다듬어서 사용할 수 있었다. 이전 DFS BFS 알고리즘에선 그 알고리즘의 플로우에 집중해서 정리를 해서 코드의 양이 길고, 효율적이지 못했기 때문에이번에는 미로에서 BFS 를 이용한 최단 거리 알고리즘을 통해서효율적으로 그래프에서 최단거리를 확인하는 방식을 정리하려고 한다.최단경로 미로찾기“최단경로” 이기 때문에 BFS를 통해서 Queue 를 통해 같은 레벨의 node(neighbors)를 반복하면서 도착지점에 부합할.. 2024. 11. 11.
(24.11.08) ELK 스택에 관하여 (1) ELK 스택을 적극적으로 활용하는 회사도 많지만,실제로는 실무 경험 내지는 대용량 트래픽을 다루는 경험이 많지 않은 이상 ELK 스택을 전부 활용하자는 아키텍쳐 구성 아이디러를 활용할 기회가 없었다. 오픈 소스이기도 해서 부담은 없지만, 실제로는 ElasticSearch에 대해서만 알고 있었기 때문에,이번 기회에 ELK 스택 전부를 알아보고 실제 프로젝트의 파이프라인(AWS 인프라 활용, 컨테이너 활용) 환경에서 어떻게 적응할지에 대해서 고민하면서 찾아보고 공부하면서 스스로 정리했다.ELK 스택Elasticsearch, Logstash, Kibana 의 약자, 로그 및 데이터 분석을 위한 강력한 오픈소스 플랫폼 스택가격 부담없이 운용이 가능각 구성요소가 서로 보완적으로 작동 내지는 독립적으로대규모 데이터.. 2024. 11. 8.
(24.11.05) DFS 응용과 백트래킹 DFS알고리즘에 대해서 학습을 했지만,어떠한 조건에 따라서는 백트래킹의 여부에 대해서 고찰을 할 필요가 있어조금 이해하는데 어려웠지만 한번더 점검을 해보면서 DFS를 적용하는 문제를 풀고백트래킹에 대해서 다시 정리해보려고 했다.DFS (Depth-First Search, 깊이 우선 탐색)한 노드에 대해서 끝까지 자식 노드를 탐색한 뒤에 다음 노드로 넘어가는 전체 탐색 알고리즘이러한 전체 탐색의 알고리즘은 어떤 목표를 찾아가는 조건이 있을 경우 모든 경우의 수를 찾는 방향따라서, 완전 탐색을 통해 최적의 답을 찾는 로직에서도 유용하게 사용할 수 있음DFS의 직접적인 활용DFS는 가중치가 존재하지 않는 그래프에서 사용이 뜻은 여러가지의 선택의 경우의 수를 선택하는 상황(가중치가 X)에서 완전탐색을 가능하게 .. 2024. 11. 5.

티스토리툴바