알고리즘119 [순서 확인 shift] 스킬트리 https://school.programmers.co.kr/learn/courses/30/lessons/49993 첫번째 방법 (성공) 필요한 스킬인지 빨리 탐색하려고 해쉬로 필요한 스킬을 정리 {skill이름: 번호} 각 트리마다 첫 스킬이 첫번째로 필요한 스킬이 아니면 다음 트리로 넘어간다 첫 스킬이 첫번째로 필요한 스킬이지만 다음 스킬이 순서가 틀려도 다음 트리로 넘어간다 여기서 순서가 맞는지 확인하는 법은 hash[전 스킬] +1 = hash[현 스킬] 이면 순서가 맞다. 이런식으로 전체트리를 순회한다. function solution(skill, skill_trees) { var answer = 0; let queue = []; const obj = {}; const firstSkill = sk.. 2023. 10. 11. [프로그래머스 lv2] 두 큐 합 같게 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/118667 첫번째 풀이 (성공) 탈출조건, 시간초과를 어떻게 세울지 고민했다. 탈출조건 먼저 탈출조건은 두 큐의 합이 같거나 최대이동 횟수를 넘었을 때다 여기서 최대이동 횟수는 두 큐의 길이가 같으므로 queue1.length*2로 설정했다. 최대이동횟수 이상 이동하게 되면 -1을 리턴한다. 시간초과 shift의 시간복잡도는 O(n)으로 시간초과가 난다 따라서 shift를 사용하지 않고 shift 할 위치는 인덱스로 기억하고 push만 한다. 두 개의 큐의 합이 홀수이면 -1 리턴한다 각 큐의 shift할 인덱스 변수를 0으로 설정한다 각 큐의 합이 같거나 최대이동 횟수 전까지 두 큐의 합을 비교해 .. 2023. 10. 10. [프로그래머스] 디펜스 게임 https://school.programmers.co.kr/learn/courses/30/lessons/142085 문제요점n명의 병사적이 더 많으면 게임 종료무적권: 병사소모 없이 한 라운드를 막을 수 있음. k개최대 몇 라운드까지1,000,000,000 => logN DFS 풀이 (시간초과)초기에 dfs를 통해 무적권을 사용하는 경우/ 사용하지 않는 경우르 모두 탐색하는 방법을 생각했는데 N이 너무 커서 시간초과가 났다. // 무적권을 쓸지 말지 2가지 경우function solution(n, k, enemy) { var answer = 0; function dfs(index, n, k) { // 적을 다 막았거나 더 이상 적을 막을 수 없으면 게임.. 2023. 10. 10. [이진탐색] 점 찍기 https://school.programmers.co.kr/learn/courses/30/lessons/140107 첫번째 풀이(시간초과) 처음엔 단순하게 가능한 경우를 모두 구한 뒤, 두 점사이의 거리가 d보다 작은 점만 가려냈다 function solution(k, d) { var answer = 0; const group = []; const count = Math.floor(d/k); for (let i = 0; i 2023. 10. 9. [이분탐색] 입국심사 https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=javascript 첫 풀이 (성공) 최소, 최대로 걸리는 시간의 중간시간을 구한다. 중간시간보다 시간이 더 필요하면 최소시간을 늘리고 다시 중간시간을 찾는다 중간시간보다 시간이 남으면 최대시간을 줄이고 다시 중간시간을 찾는다 2,3번을 최소시간과 최대시간이 엇갈릴 때까지 반복한다 주의할 점 최소값을 구해야하니까 minTime을 리턴하게 시간이 부족한 경우에만 minTime을 늘리고 그 외는 maxTime을 줄인다. 최소시간 = 최대시간이라고 최소시간을 찾은게 아니다. 최소시간이 늘어나서 최대시간이랑 같을 수 도 있기때문이다 따라서 최소시간과 최대시간이 엇갈릴 떄까지 찾는다 .. 2023. 10. 9. [프로그래머스 lv2] 연속된 부분 수열의 합JS [투포인터] https://school.programmers.co.kr/learn/courses/30/lessons/178870 문제 요점 비내림차순이란 222, 2334 처럼 nlogN 풀이 투포인터 시작 포인터와 끝 포인터 두 가지를 사용하면서 범위를 넓혀나간다. 포인터 사이의 모든 원소의 합이 k이하면 끝 포인터 값을 늘리고 k초과면 시작 포인터 값을 늘리기 포인터 i, j 둘 다 0인덱스에서 시작하고, j가 sequence 배열 끝에 다다를 때까지 순회하면서 합sum을 계산한다. (j가 sequence를 넘어가면 더 이상 큰 부분수열의 합을 구할 수 없다.) 둘의 합 = k 이면 answer에 {시작 인덱스, 끝 인덱스, 끝 인덱스-시작인덱스}를 저장한다 가장 작은 수인 sequence[i]를 sum에서 빼고.. 2023. 10. 9. 이전 1 ··· 8 9 10 11 12 13 14 ··· 20 다음
