본문 바로가기

알고리즘119

[다익스트라 레벨3] 부대복귀 문제링크 첫번째 풀이 (성공) 문제에 정해진 destination에서 다른 부대로 이동하기까지 최소비용을 구한다 => 몇일 전 공부한 다익스트라가 생각났다. 시작노드에서 각 노드까지 최소비용값을 저장할 distance 배열을 만든다 이 때 인덱스 = 노드값 동일하게 하기 위해 길이는 n+1이다 최소비용을 구하므로 Infinity로 초기화한다. roads를 순회하며 각 노드에 연결된 neighbors를 정리하여 양방향 그래프 graph를 만든다. (distance와 같은 길이) queue에 방문한 노드를 추가하는데 초기화로 시작노드 destination을 넣는다 queue.shift하여 시작노드의 값을 구하고, 2번에서 구한 graph에서 시작노드와 연결된 next를 구한다 시작노드에서 next 까지 최소.. 2023. 11. 3.
[레벨3] 기지국 설치 문제 링크 첫번째 풀이 (실패) set에 1부터 n까지 아파트를 정리한다 stations를 순회하면 영향을 받는 아파트들을 set에서 지운다 set을 배열로 변환하여 순회하면서 연속적인 숫자가 아닌 부분 (즉 2번에서 지운 구간에 의해 나눠진 구간들)을 만날떄마다 range의 갯수로 나눠 기지국 갯수를 구한다. function solution(n, stations, w) { var answer = 0; const numArr = Array.from({length: n},(_, i) => i+1); const set = new Set(numArr); for (const station of stations) { set.delete(station); for(let i = 1; i 2023. 11. 1.
[다익스트라] 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제정리 1번 마을에서 출발 K시간 이하까지의 마을에 배달을 한다. 배달이 되는 마을 갯수는? 1에서 각 마을까지 최단거리 배열을 구하고 그 중 최단거리가 K보다 작은 마을 갯수를 리턴한다 첫번째 풀이(성공) 하나의 시작노드에서 다른 노드로 이동, 최단기간 => 다익스트라 1. 그래프 생성 2. weightArr, queue 시작점 초기화 3. while queue 순회 3-1. 이웃노드찾기 3-.. 2023. 11. 1.
[two pointer] 릿코드 3Sum (medium) https://leetcode.com/problems/3sum/ 첫번째 풀이 (성공) var threeSum = function(nums) { const result = []; const target = 0; nums = nums.sort((a, b) => a - b); // 정렬해주어서 포인터의 이동시 판단을 더 간편하게 할 수 있다. // 첫번째 let i = 0; while(i < nums.length-2) { while(nums[i-1] === nums[i]) i++; // 첫번째가 이전과 같은 숫자면 스킵한다 // 두번째 let j = i+1; // 두번째는 첫번째 바로 뒤 부터 시작한다. while(j < nums.length-1) { // 세번째 let k = nums.length-1; wh.. 2023. 10. 30.
[two pointer] 릿코드 27. Remove Element https://leetcode.com/problems/remove-element/ Remove Element - LeetCode Can you solve this real interview question? Remove Element - Given an integer array nums and an integer val, remove all occurrences of val in nums in-place [https://en.wikipedia.org/wiki/In-place_algorithm]. The order of the elements may be changed. Then r leetcode.com 첫번째 방법(성공) 문제에서 in-place, 순서는 변경해도 된다고 한다 => 포인터가 뒤에서 앞으.. 2023. 10. 22.
[그리디] 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885# 첫번째 (성공) 무게를 오름차순으로 정렬 최소, 최대 무게의 합이 limit 이하면 answer을 더하고 최소, 최대를 빼준다 limit이상이면 최대만 뺀다. function solution(people, limit) { var answer = 0; people.sort((a, b) => a -b); while(people.length) { if (people[0] + people[people.length-1] a - b); let left = 0; let right = people.length-1; while(left < right) { // 2명이 구명보트를 탈 수 있을 때 if (pe.. 2023. 10. 14.

티스토리툴바