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] 은 구간..