분류 전체보기657 [Leetcode] 32. Longest Valid Parentheses 문제 : https://leetcode.com/problems/longest-valid-parentheses/ '(', ')' 문자만 포함한 문자열이 주어질 때, 가장 긴 유효한 괄호 부분 문자열의 길이를 구하여라. DP + Stack dp[i] = s[~i] 문자열에서 s[i]를 포함한 부분 문자열의 가장 긴 유효한 괄호 부분 문자열 길이. stack 열린 괄호 문자 인덱스 문자열 s를 앞에서부터 탐색하면서 열린 괄호 문자면 스택에 저장하고 닫힌 괄호 문자이면서 스택에 값이 있으면 top 값을 가져온다. top은 현재 탐색 중인 닫힌 괄호 문자와 매칭 되는 열린 괄호 문자의 인덱스(let, index)이며 dp[i] = (i - index + 1) + dp[index-1] dp의 점화식은 위와 같다. .. 2022. 5. 24. 잔디 중간점검 Leetcode 요즘은 릿코드에서 챌린지로 매일 한 문제씩 푸는거 매일 풀고있다. 풀었던 문제도 복습겸 푸는 중 4월 올개근 뿌듯 Github 알고리즘으로 잔디 잘 심어지고 있긴한데 개발 관련 커밋 수도 더 늘려야겠다. 깃헙 잔디에서 View your contributions in 3D, VR and IRL! 요런거 누르니까 3d 모델링으로 보여준다. 트로피같다. https://skyline.github.com/ Your GitHub story in 3D - GitHub Skyline View a 3D model of your GitHub contribution graph. Share it, print it, and more! skyline.github.com 요기에서도 되는듯. 2022. 5. 19. [Spring] Spring Cloud Config 정리 개요 MSA 아키텍처에서는 환경설정 파일을 외부에서 관리하여 설정이 바뀐 경우 서비스의 수정, 재컴파일 없이 여러 환경에서 이를 적용할 수 있게 해줍니다. 이를 위해 Spring 프레임워크는 Spring Cloud Config를 제공합니다. 기본 세팅 컨피그 서버를 사용하는 경우 구조는 [그림 1]과 같습니다. 컨피그 파일 repository가 존재하며 컨피그 서버는 뜰 때 해당 레포를 바라봅니다. 서비스들은 배포될 때 컨피그 서버에서 배포 시 환경의 환경설정 정보를 가져와서 서버를 띄워줍니다. spring boot actuator 의 refresh endpoint를 이용하여 config file의 변경점이 있다면 서버 재시작을 하지 않고도 미리 명시해둔(@RefreshScope) 컨피그들은 변경된 정보.. 2022. 5. 15. [Leetcode] 785. Is Graph Bipartite? 문제 : https://leetcode.com/problems/is-graph-bipartite/ 인접한 노드의 색을 현재 노드의 색과 다른 색으로 칠해가면서 너비우선탐색을 진행한다. 칠할 수 있는 색은 두가지이다. 인접한 노드에 색이 칠해져 있지 않다면 현재 노드의 색과 다른 색으로 노드를 칠하고 칠한 노드를 탐색한다. 인접한 노드에 이미 색이 칠해져 있다면 현재 노드의 색과 비교한다 현재 노드의 색과 다른 색이면 유효한경우이다. 현재 노드의 색과 같은 색이면 유효하지 않으므로 false를 반환한다. 시작노드를 첫번째 노드만으로 잡고 너비우선탐색을 한 번만 진행한다면 [그림 1]과 같이 3~6번 노드의 유효성은 체크할 수 없다. 모든 노드를 시작지점으로 잡고 위 방법으로 노드들을 탐색하되 노드의 색 배.. 2022. 4. 29. [Leetcode] 1584. Min Cost to Connect All Points 문제 : https://leetcode.com/problems/min-cost-to-connect-all-points/ 최소신장트리, MST를 만드는 문제이다. 크루스칼 알고리즘을 사용했다. 각 point들을 정점으로 보고 모든 정점들간 간선을 연결하며 간선의 cost는 맨해튼 거리 수식으로 계산한다. 간선들을 cost 오름차순으로 정렬한뒤 DSU를 사용하여 사이클이 발생하는지 체크한다. 사이클이 발생하면 간선을 사용하지 못하고 사이클이 발생하지 않으면 cost를 정답변수에 더해준다. 시간복잡도는 정점의 수가 points 배열 크기이고 간선 수가 points^2이므로 간선들을 오름차순 정렬하는데 드는 O(간선 * log간선)이 된다. 소스코드 : https://github.com/fpdjsns/Algor.. 2022. 4. 26. [Leetcode] 538. Convert BST to Greater Tree 문제 : https://leetcode.com/problems/convert-bst-to-greater-tree/ 이진 검색 트리(BST)가 입력으로 주어지면 BST의 모든 키가 원래 키보다 큰 모든 키의 합으로 변경하라. BST를 오른쪽 자식 노드 -> root 노드 -> 왼쪽 자식 노드 순으로 탐색하며 탐색한 노드들의 합을 저장하고 root 노드를 노드의 합으로 갱신하라. 오른쪽 자식 노드 탐색 합 갱신 root->val을 합으로 갱신 왼쪽 자식 노드 탐색 시간복잡도는 O(노드수) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/538.%20Convert%20BST%20to%20Greater%20Tree.cpp 2022. 4. 16. 이전 1 ··· 4 5 6 7 8 9 10 ··· 110 다음
