판교의 메타몽

개요Trie란?LeetCode 208번 문제 - Implement Trie (Prefix Tree)  1.  Trie란?문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조이다.Trie라고 적고 try로 발음되며, 다른 말로는 래딕스 트리(Radix Tree), 접두사 트리(Prefix Tree), 또는 탐색 트리(Retrieval Tree)라고도 한다.  우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화된 자료구조이며,디테일한 설명은 박지훈님이 작성한 [자료구조] 트라이(Trie)를 참고하자. [자료구조] 트라이 (Trie)트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.우리가 검색할 때 볼 수 있는 자동완성 기능,..

순서 무중단 배포란? 무중단 배포 전략 3대장 블루 / 그린 배포 (Blue / Green Deployment) 롤링 배포 (Rolling Update Deployment) 카나리 배포 (Canary Deployment) Nginx가 만능일까? L4 스위치와 L7 스위치, 그리고 Nginx 0. 무중단 배포란? 서비스를 중단하지 않고 배포하는 것을 의미한다. 1월에 점검이 진행되고, 점검날에 1월동안 새로 개발한 코드들을 반영한다고 상상하자. 점검 이전에 실제 서비스에 돌아가던 프로젝트를 v1, 점검 이후 반영되는 신규 프로젝트를 v2라고 가정했을때, v1이 돌아가던 서비스를 종료하고 v2를 배포 + 반영하기까지 서비스가 중단된 시간을 다운타임(downtime)이라고 한다. (1) v1 서비스를 중단시켜..

문제 링크 The problem link : LeetCode 49. Group Anagrams 문제 요약 문자열 배열 strs가 주어진다. 애너그램으로 재배열했을때 같은 단어들끼리 그룹으로 뭉쳐라. 그룹으로 뭉쳐진 단어들을 반환하라. 이때 순서는 상과없다. 문제 풀이 class Solution { public List groupAnagrams(String[] strs) { HashMap map = new HashMap(); for(int i=0; i

문제 링크 HackerRank : Fraudulent Activity Notifications (Click) 문제 요약 List 타입의 expenditure와 int타입의 d가 아래와 같이 주어진다. expenditure = [10,20,30,40,50] d = 3 중간값의 정의는 해당 글을 참고한다. 예를 들어 위와 같이 d가 3인 경우, n-3, n-2, n-1의 값중 중간값 * 2 이상의 값을 n번째 날이 가질 경우, 고객에게 알림을 보내줘야한다. 10,20,30의 중간값은 20인데, 40의 경우 20*2 이상의 값을 가지므로 알림을 보내야한다. 20,30,40의 중간값은 30인데, 50의 경우 30*2 보다 값이 작으므로 알림을 보낼 필요가 없다. 때문에 위 예시에서 알림을 보내는 개수(정답)는 ..

문제 링크 HackerRank : Sorting : Comparator (Click) 문제 요약 n 사이즈의 선수들의 정보가 담긴 배열이 주어진다. 여기서 두 사람씩 차이를 비교할 compare메서드를 완성하라. 성적(score)은 내림차순으로, 이름(name)은 오름차순으로 정렬해야한다. a > b라면 1을, a = b라면 0, a b.score) return -1; else if(a.score < b.score) ret..

문제 링크 HackerRank : Recursive Digit Sum (Click) 문제 요약 1

문제 링크 HackerRank : Davis&#39; Staircase (Click) 문제 요약 Davis의 집에는 계단이 많은데, Davis는 한번에 계단을 오를때 1칸, 2칸, 또는 3칸을 오를 수 있다. Davis가 n층 높이의 계단을 오를때, 몇 가지의 가지수로 계단을 오를 수 있는지 정답을 구하라. 이때 정답은 10000000007로 나눈 나머지를 출력하라. 문제 풀이 public static int stepPerms(int n) { if(n == 0) return 0; else if(n == 1) return 1; else if(n == 2) return 3; else if(n == 3) return 4; int t1 = 1; int t2 = 2; int t3 = 4; int res = 0; ..

문제 링크 GeeksForGeeks : Union-Find (Click) 문제 요약 아래 2개의 메서드를 완성하라. Union : 2개의 부분집합을 하나로 합치기 isConnected : 2개의 부분 집합이 하나의 부분 집합인지 true or false로 출력하기 문제 풀이 class Solution { public int find(int x, int par[]) { while(x != par[x]) { x = par[x]; } return x; } //Function to merge two nodes a and b. public void union_(int a, int b, int par[], int rank[]) { a = find(a, par); b = find(b, par); if(a==b) re..

문제 링크 The problem link : Geeks For Geeks - Transitive closure of a Graph(클릭) 문제 요약 N*N 배열 graph가 주어집니다. 이 배열은 방향이 있는 그래프를 뜻합니다. graph[i][j]가 의미하는 것은, i 정점에서 j 정점까지 연결되어있는 (= 방향이있는) 간선이 있음을 뜻합니다. 정점 i에서 j까지 (다른 정점을 거쳐서라도) 도달할 수 있는지를 가리키는 그래프를 출력하세요. 핵심 요약 문제 조건을 보면 예상 시간복잡도와 공간복잡도를 이렇게 언급했다. Expected Time Complexity: O(N^3) // 시간복잡도 Expected Auxiliary Space: O(N^2) // 공간복잡도시간 복잡도를 보면 힌트가 나오는데, 이 ..

문제 링크 The problem link : LeetCode 841. Keys and Rooms 문제 요약 0번째부터 n-1까지 라벨이 붙여진 방이 있습니다. 0번째 문을 제외한 나머지 문은 잠겨있습니다. 방에 들어갔을때, 해당 방에 존재하는 key를 사용할 수 있게됩니다. 이렇게되면 key를 사용해 해당 방에 들어갈 수 있습니다. 당신의 목적은 0번째부터 n-1까지의 모든 방을 들어가는 겁니다. 가능할 경우 true를, 그렇지 않을 경우 false를 출력하세요. 예시 입력값 : rooms = [[1,3],[3,0,1],[2],[0]] 출력값 : false 해설 : 2번째 방(=[2])에 들어갈 수 없기 때문에 false입니다. 조건 - n == rooms.length - 2