알고리즘 (54) 썸네일형 리스트형 704. Binary Search O(log n ) . 문제이름도 이진탐색이다. const search = function(nums, target) { let start = 0,end = nums.length-1 while(start 17299. 오등큰수 우선, n이 백만이여서 O(n2)으로 풀면 시간초과에 걸린다. 아래는 시간초과 풀이이다. import sys;input=sys.stdin.readline n = int(input()) a = list(map(int,input().split())) from collections import Counter c = Counter(a) most_common = c.most_common()[0][0] for i in range(n): if a[i] == most_common: print(-1, end=' ') continue for j in range(i+1, n): if c[a[j]] > c[a[i]]: print(a[j], end= ' ') break 리스트를 순회하면 안될 것 같다. 어떻게 하면 순회를 안하.. 62. Unique Paths 우선 m이 row를 뜻하므로 1줄이라면 별까지 가는 경우의 수는 1개일 수밖에 없다. 1줄이 아니라면 옛날에 그 미로찾기같은거 할 때 경우의 수 구하는 방법에서 여기까지 오는데 가능한 경우의 수를 써놓고 한칸전진하면 이전 경우의 수들 더해서 작성하는 그 방식으로 문제를 풀었다. const uniquePaths = function(m, n) { if (m == 1) return 1; const arr = Array.from ({length: m}, () => Array.from ({length: n} , () => 0)) for (let i = 0 ; i < n ; i++) { arr[0][i] = 1 } for (let i = 0 ; i < m ; i++) { arr[i][0] = 1 } for (let.. 15681. 트리와 쿼리 트리에서의 동적계획법. 재귀 호출을 통해서 노드의 개수를 세줄 수 있다. import sys;input=sys.stdin.readline sys.setrecursionlimit(10**9) n,r,q=map(int,input().split()) tree = [[] for _ in range(n+1)] cnt = [0] * (n+1) def NodeCount(x): cnt[x] = 1 for i in tree[x]: if not cnt[i]: NodeCount(i) cnt[x] += cnt[i] for _ in range(n-1): u, v = map(int,input().split()) tree[u].append(v) tree[v].append(u) NodeCount(r) for i in range(q).. 46. Permutations 파이썬으로 재귀 구현할 때랑 다른 느낌이다. JavaScript로 알고리즘문제풀이가 더 익숙해지도록 문제를 더 많이 풀어야겠다. 배열에 원소가 있으면 넘어가고 없으면 추가해준후 dfs를 돌렸다. const permute = function(nums) { const res = [] dfs(res, [], nums) return res }; const dfs = (res, arr, nums) => { if (arr.length === nums.length) { res.push([...arr]) return } nums.forEach(n => { if (!arr.includes(n)) { dfs(res, [...arr, n], nums) } }) }그냥 for문이 더 깔끔한 느낌이다. const permute.. 2629. 양팔저울 구슬의 무게를 구하기 위해서는 두 양팔 저울무게의 차이를 구하면 된다. 쉽게 접근하면 추1번을 왼쪽에 올릴 수도, 오른쪽에 올릴 수도, 올리지 않을 수도 있다. 근데 추가 30개 까지 가능하다. 즉 3의 30승 = 205,891,132,094,649 에 해당하는 경우의 수를 가질 수 있다. 이러면 약간 불안하다. 따라서 경우의 수를 적게 만들거나 이미 계산한 것은 계산하지 않는 방식을 취해야한다. 왼쪽 오른쪽에 놓을수 있고 놓지 않을 수도 있다. -> 탐색. dfs를 생각하게 되었다. dfs의 리턴 조건에서 추의 개수가 다 차면 리턴하면 좋을 것 같았다. import sys;input=sys.stdin.readline n = int(input()) weights = list(map(int,input()... 53. Maximum Subarray 처음엔 간단한듯 싶다가도 약간 해맸다. const maxSubArray = function(nums) { for (let i = 1; i < nums.length; i++) { nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]); } return Math.max(...nums) }; 187. Repeated DNA Sequences 완전 탐색을 선택했다. Set, Map은 이터러블이므로 Array.from 으로 배열로 바꿀 수 있다. const findRepeatedDnaSequences = function(s) { if (s.length < 10) return [] let set = new Set(), res = new Set() let start = 0 for (let end = 9; end < s.length; end++) { let substr = s.substring(start, end + 1) if (set.has(substr)) res.add(substr) else set.add(substr) start++ } return Array.from(res) } const findRepeatedDnaSequences = fun.. 이전 1 2 3 4 5 6 7 다음
