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

보호되어 있는 글입니다.

defaultdict() - 숫자, list, set, 등으로 초기화 가능 - dictionary와 작동방식이 거의 동일한데, defaultdict()는 인자로 주어진 객체(default-factory)의 기본값을 dictionary 값의 초기값으로 지정할 수 있음 외부함수이기 때문에 import from collections import defaultdict 예시 1 A = [2,4,3,1,4,2] A_dict = defaultdict(int) for i in A: A_dict[i] += 1 # 일반적인 dictionary와 다른 부분 # A에서 개수가 1개인 값 찾기 (3과 1) for k, v in A_dict.items(): if v == 1: print("unique") defaultdict를 ..

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. 그 중에서 ..