코딩곳간

문제 링크 분류 / 레벨 / 언어탐욕법(Greedy) / LV.3 / Javscript 설명공간 복잡도 절약문제의 요구사항은주어진 추들을 다양하게 합산해도 도저히 만들 수 없는무게들 중 최소값을 찾는 것이다. 운이 좋게도, 무게들은 모두 양의 정수이다.양의 정수는 1부터 시작해서 간격이 1이다.또한 이 세상의 모든 Array는 index가 0부터 시작해서 간격이 1이다. 추의 조합으로 나올 수 있는 양의 정수들을 배열로 만들고배열의 앞에 0를 임의로 넣는다면문제에서 원하는 임계점까지는 index와 value가 완전히 일치하게 된다. 따라서 배열을 메모리에 할당하지 않고가상으로 배열이 있다고 생각하며 풀 수 있다. 구체적으로 말하면최종적으로 체크 완료한 index(= 무게 합)을 let 변수로 두고 풀 것이다. Greedy 적용앞서 말한 가상의 배열은 일단 논외로 하고 Greedy를 생각해보자. 중간 지점의 예를 들면 기존의 합산 list ...

문제 링크 분류 / 레벨 / 언어탐욕법(Greedy) / LV.3 / Javscript 설명이분탐색 시도차량의 대수가 1대 ~ 10000대 이다.차량이 10000대 있을 때운이 좋으면 카메라 1대로 끝나고, 운이 없으면 카메라를 10000대 두어야 한다.return의 range가 넓기에 역으로 대입하고자 이분탐색의 틀을 먼저 짜보았다. 12345678910111213141516function solution(routes) { routes.sort((a, b) => a[1] - b[1]).sort((a, b) => a[0] - b[0]); const setCam = () => {}; let left = 1; let right = routes.length; let mid; while (right - left > 1) { mid = Math.floor((left + right) / ...

문제 링크 분류 / 레벨 / 언어탐욕법(Greedy) / LV.3 / Javscript 설명이 문제에서 기준이 되는 것은각 노드가 아니라노드을 연결하는 간선이 되어야 한다. 이것을 시행착오를 겪고 알았다. 노드를 기준으로처음엔 노드를 기준으로 그리디를 적용해보았다. 각 노드에서 가장 짧은 간선을 찾아 건너간다. 건너간 노드에서 또 최소 간선을 찾아 건너간다. 건너간 노드에서 갈 수 있는 간선이 없다면 index=0부터 index++하여 다음 노드로 기준을 옮긴다. 이렇게 풀면 백프로 연결하는 것은 보장되지만 최소가 아닐 수 있다. (사이클)0-1 : 21-2 : 42-3 : 53-4 : 64-1 : 3 이 경우 0부터 시작하면 2 4 5 6 간선을 건너갈 것이다.그러나 3-4 대신 4-1을 연결하는 것이 더 최적의 경로이므로이 방법으로는 정답을 도출할 수 없다. 간선을 기준으로 간선을 기준으로 costs 배열을 오름차순 정렬한다. co ...

문제 링크 분류 / 레벨 / 언어동적계획법(Dynamic Programming) / LV.4 / Javscript 설명처음 풀이빠르게 구현할 수 있고 동시에 모든 요소를 검증할 수 있는재귀를 사용해 먼저 풀어보았다.그러나 left와 right의 최대 길이가 각 1000개씩이고,left[0] >= right[0] 일 경우 최대 2개씩 갈라지므로최대 2의 1000제곱 만큼의 loop 발생한다.돌려보니 역시나 시간 초과가 발생했다. 12345678910111213141516171819202122function solution(left, right) { let max = 0; const next = (l, r, sum) => { if (l.length * r.length === 0) { if (sum > max) max = sum; return; } let ...

문제 링크 분류 / 레벨 / 언어동적계획법(Dynamic Programming) / LV.3 / Javscript 설명마찬가지로 메모이제이션을 할 건데,이 문제는 삼각형의 각 노드에 메모이제이션을 해줄 수 있어 편하다. 각 loop가 의미하는 것은 삼각형의 row들을 점검하는 것이고row 점검을 마무리한 후, 최댓값(최적의 값)으로 덮어씌운다. 그리고 이 과정을 보다 짧게 코딩하기 위해 reduce를 사용했다. 전체 코드123456789101112131415161718function solution(triangle) { return Math.max( ...triangle .reduce((acc, cur, idx) => { if (cur.length === 1) acc.push(cur); else acc.push( cur.map((v, i) => ...

문제 링크 분류 / 레벨 / 언어완전탐색 / LV.2 / Javscript 설명대기업 인적성에 규칙 찾기 part로 나오는 유형과 비슷하다.이 문제에서는 brown 블록과 red 블록의 규칙을 찾는게 우선이다. 전체 블록은 “가로 >= 세로” red 블록은 내키는대로 존재하고 brown은 그것을 1겹으로 둘러싸고 있음. for문, while문, 재귀 중 아무거나 사용하여 완전탐색을 하면 되고,나는 for문을 사용하는 대신, 전체 블록의 루트를 for문의 끝으로 지정했다. 전체 코드12345678function solution(brown, red) { const big = brown + red; let max = Math.floor(Math.sqrt(big)); for (let i = 3; i < max + 1; i++) { if (big % i === 0 && (big / i - 2 ...

문제 링크 분류 / 레벨 / 언어이분탐색 / LV.4 / Javscript 설명풀이 방법이 문제는 제거할 돌의 수 n이 input이고,output은 다음과 같다. 제거할 돌을 어떻게 pick하는지에 따라 여러 경우의 수 존재 각 경우에서, 돌 사이의 거리들 중 최솟값을 저장 <최솟값>, <최솟값>, <최솟값>, … 중 최댓값 반환 요약하자면 돌 사이가 서로서로 최대한 멀게끔 빼내라는 말이다. 새로운 함수 정의우리는 역으로 대입할 것이기 때문에output으로 가능한 “거리”들이 input이 될 것이다.그래서 이것을 받을 함수도 하나 더 정의해야 한다. 거리 => { 모든 돌 사이의 거리가 input보다 크거나 같아야 한다. 그만큼 돌을 빼내자(with count++) } => count 그리고 output == n 인 input 중 가장 큰 값을 택하면 된다. 애매한 ...

문제 링크 분류 / 레벨 / 언어스택,큐 / LV.2 / Javscript 설명아이디어문제에서도 가이드하듯, ()를 빔으로 치환하는 것이 최우선이다.단 치환이라고해서 ()를 굳이 다른 값으로 replace하기 보다는배열에서 , 정도로 생각하는 편이 낫다. = string.split(“()”) 풀이 방법 배열의 요소를 하나씩 돌면서 (에는 stack push, )에는 stack pop한다. 각 차례가 끝날 때 = ,에 도달할 때 = 빔stack의 개수만큼 더한다. 단 stack을 참고할 때는 pop이 된 후라 막대가 한개가 빠지는 셈이다.그래서 pop이벤트마다 미리 answer++ 해준다. 전체 코드1234567891011121314151617181920function solution(arrangement) { let arr = arrangement.split("()"); let answer ...

문제 링크 분류 / 레벨 / 언어스택,큐 / LV.2 / Javscript 설명2개의 자료구조를 사용했다. 처음 input으로 받은 priorities priorities의 index만 따로 뽑은 배열 이 문제에서는 priorities에서 하나를 추출할 때 마다추출 지점의 앞 요소들이, 추출 지점 뒤쪽으로 옮겨진다.그리고 이 과정에서 index가 바뀌므로 기존의 index는 알 수 없게 된다. 단, 이 문제는 end point 여부를 검증할 때 원래 index를 알아야 하므로priorities가 바뀌더라도 원래 index는 꾸준히 들고 있어야 한다. priorities가 뒤섞일 때, index 배열도 똑같이 뒤섞어주면 원래 index를 계속 알 수 있다! 전체 코드1234567891011121314function solution(priorities, location) { let answer = 0; let index = priori ...

문제 링크 분류 / 레벨 / 언어동적계획법(Dynamic Programming) / LV.3 / Javscript 설명N을 몇 번 썼는지를 메모이제이션 해둔다.메모이제이션은 다음과 같다.https://ko.wikipedia.org/wiki/메모이제이션 메모이제이션을 사용하는 패턴은 대개 비슷하다.loop(i)에서 계산한 내용이 loop(i+1)로 넘어가면 증발하므로,증발하기 전에 loop(i) 단에서 계산 결과만 전역 변수에 따로 저장하는 방식이다. 단, 이번 문제에서는 loop의 수가 8까지로 정해져있고,각 메모이제이션마다 계산으로는 도달하는 것이 아닌 초기요소들 N, NN, NNN, NNNN, … 이 있으므로이를 초반에 정적으로 정의한다. 전체 코드12345678910111213141516171819202122232425262728293031323334353637383940function solution(N, number) { if ...