Slow but steady wins the race

문제 https://www.acmicpc.net/problem/1967 풀이 한 노드 기준에서 각 정점까지 거리를 구하기 가장 먼 길이에 해당하는 노드 찾기 2번의 노드를 기준으로 거리 구하는 과정을 한번 더 반복하면 됨 import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def dfs(idx,v): for n_idx, n_val in tree[idx]: if visited[n_idx] == -1: visited[n_idx] = v+n_val dfs(n_idx,v+n_val) n = int(input()) tree = {} for i in range(1,n+1): tree[i] = [] for _ in range(n-1): a,b,c =..

가장 긴 증가하는 부분 수열의 '길이'을 구하는 방법은 1. DP(Dynamic Programming) - 동적 계획법 2. Binary Search - 이분 탐색 으로,, 이전 게시글 참고하기 : https://bskwak.tistory.com/259 이번 게시물은 '길이'가 아닌 가장 긴 증가하는 부분 수열(LIS) 자체를 구하는 방법이다. 풀이 방법을 간단하게 설명하면, 1. dp를 통해 LIS 길이 구하기 2. 역추적하여 배열 구하고 뒤집으면 구할 수 있음 관련 문제 : https://www.acmicpc.net/problem/14002 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split()..

가장 긴 증가하는 부분 수열(LIS) 풀이 방법 부분 수열 : 임의의 수열이 주어질 때, 몇 개의 수를 제거하여 만든 수열 부분 수열 중 가장 긴 증가하는 부분 수열을 구하는 방법은 2가지가 있다. 1. DP(Dynamic Programming) - 동적 계획법 2. Binary Search - 이분 탐색 1. 동적 계획법을 사용한 풀이 (백준 11053) 문제 : https://www.acmicpc.net/problem/11053 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dp = [1 for i in range(n)] for i in range(n): for j in range(..

문자열 → 숫자 : parseInt(문자열변수, 10) var str_n = "12"; var int_n = parseInt(str_n, 10); 숫자 → 문자열 : 숫자변수.toString() var n = 10 var str_n = n.toString(); 문자열 길이 : 문자열변수.length console.log(str_n.length) 문자열 → 배열 : [...문자열변수] my_string = '12345; console.log([...my_string]); 배열 뒤집기 : 배열.reverse() num_list=[1,2,3]; num_list.reverse(); 배열 자르기 : 배열.slice(시작,끝) const arr = ['a', 'b', 'c', 'd']; const arr1 = ar..

시도 1 deque로 풀 수 있을 것이라 생각했다.. [value, idx ] (value: 현재까지 값, idx : 현재 위치) 를 deque에 추가 하나씩 꺼내어 idx+1 번째의 값을 value에 더하고 m으로 나눈 나머지가 0인지 아닌지 체크 당연하게 시간초과.. 시도 2 (정답) list = [1,4], m으로 나눈 나머지 r 이라고 할 때, 다음과 같이 식을 작성할 수 있다 tmp1 = list[0] * m + r tmp2 = list[1] * m + r r의 값이 동일하다면, tmp2 - tmp 1 = m * (list[1] - list[0]) 이말은 즉,, 나머지가 같으면? m으로 나누어 떨어진다는 의미와 같다. 만약, list가 누적합 리스트라면, list[1] - list[0] 은 구간..

nums = [-2,1,-3,4,-1,2,1,-5,4] 이 배열에서 가장 큰 합을 가진 부분 배열은 [4,-1,2,1], 최대합은 6이다 어떻게 구해야 할까? # Brute Force 카데인 알고리즘이 생각나지 않는다면 Brute Force 접근법으로 풀어야한다! Brute-Force란, 모든 경우의 수를 다 구해본 후에 max값을 찾는것 풀이를 간략하게라도 적어보자면,, 1. nums의 index 0부터 시작해서 nums[0]과 함께할수있는(?) 모든 부분합을 구한다. 2. nums[0]의 가능한 모든 부분합 중 가장 큰 값을 변수/리스트/..에 저장 3. 나머지 index 1부터 n-1까지 '1','2' 반복 4. 그러면 리스트던지, 변수던지, 각 인덱스에 해당하는 큰 값들이 모아짐 5. 그 중에서 ..

1. JAVA 풀이 class Solution { public void wiggleSort(int[] nums) { Arrays.sort(nums); int[] answer = new int[nums.length]; int len = nums.length; if (nums.length %2 != 0) len = nums.length+1; for(int i=0;i< len/2; i++){ answer[i*2] = nums[len/2-i-1]; } for(int i=0; i< nums.length/2; i++){ answer[i*2+1] = nums[nums.length-i-1]; } for(int i=0;i None: """ Do not return anything, modify nums in-place ..

1. 루시와 엘라 찾기 동물 보호소에 들어온 동물 중 이름이 Lucy, Ella, Pickle, Rogan, Sabrina, Mitty인 동물의 아이디와 이름, 성별 및 중성화 여부를 조회하는 SQL 문을 작성해주세요.이때 결과는 아이디 순으로 조회해주세요. SELECT ANIMAL_ID, NAME, SEX_UPON_INTAKE FROM ANIMAL_INS WHERE NAME IN ('Lucy','Ella','Pickle','Rogan','Sabrina','Mitty') ORDER BY ANIMAL_ID 2. 이름에 el이 들어가는 동물 찾기 보호소에 돌아가신 할머니가 기르던 개를 찾는 사람이 찾아왔습니다. 이 사람이 말하길 할머니가 기르던 개는 이름에 'el'이 들어간다고 합니다. 동물 보호소에 들어온..