본문 바로가기

분류 전체보기

 (214)
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..
13기 SW마에스트로 최종 합격 후기 (서류 제출, 1차 코테, 2차 코테, 면접) 소프트웨어 마에스트로 13기에 최종 합격했다. 자기소개서 작성부터, 1차 코테, 2차 코테, 면접까지 전체적인 회고를 해봐야겠다. 자기소개서 자기소개서는 4개의 문항이다. 1. [자기소개]소프트웨어분야 전문성을 키우기 위해 남들과 달리 특별한 노력을 한 경험을 서술하여 주시기 바랍니다 -> 나는 1번 문항을 제일 길게 작성 했다. 지금까지 내가 개발을 어떻게 공부했고, 새로운 것을 배울 때 어떻게 하는지, 협업 경험등 그냥 어떻게 살아왔는지에 대해서 작성한 것 같다. (공백 포함 1988자 작성) 2. [자기소개] 귀하의 장래희망을 서술하여 주시기 바랍니다. -> 장래희망을 작성하는데 많은 고민을 했다. 근데 하나로 작성하기보다는 여러가지 꿈을 작성하고 그 꿈에 대한 설명을 나열하는 방식으로 작성을 했다..
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) };

티스토리툴바