본문 바로가기

알고리즘

(10)
[알고리즘] 최소 실행 시간 구하기 https://leetcode.com/problems/task-scheduler/description/태스크 스케줄러문제) You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.Return the minimum num..
[알고리즘] 원의 방정식 (두 원 사이의 정수 쌍) 문제: LV2 두 원 사이의 정수쌍https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Q. 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 리턴하라... 개인적으로 이 문제를 보고 원을 4분면으로 나누고, 한분면에 해당하는 점의 개수를 구한 뒤 곱하기 4해주면 된다고 생각했다.여기까지는 좋았는데... 그 다음이 생각나지 않았다.왜냐하면 일단 1  그래서 인터넷을 뒤적이며 검색했는데일단 원의 방정식은 x^2 + y^2 = r^2 이다...
[알고리즘] 집합 (Set) 배열 합집합전개연산자 spread operator(...)와 Set을 사용하여 두 배열을 병합하고 모든 중복된 요소를 제거할 수 있다.let arrA = [1, 2, 3, 4];let arrB = [5, 6, 7, 2, 1];[...new Set([...arrA, ...arrB])]; // returns [1, 2, 3, 4, 5, 6, 7]배열 교집합filter와 includes을 사용하여 두 배열에 서로 포함된 요소들을 알 수 있다.includes() 함수는 배열이 특정값을 포함하고 있는지의 여부를 boolean 값으로 반환한다.let arrA = [1, 2, 3, 4];let arrB = [1, 2, 5, 6, 7];arrA.filter(e => arrB.includes(e)); // returns..
[알고리즘] 정규식(Regex) 정규식(Regular Expression)은 문자열을 다룰 때, 문자열의 일정한 패턴을 표현하는 일종의 형식이다.코딩테스트 문제에서 문자열을 다뤄야할때 유용하게 쓰일 상황이 꽤 많을 것 같아 기록으로 남겨놓고자 한다. 특정한 패턴에 따라 문자열을 나눠야할때(Split)1. 문자열에서 URL을 찾는 정규표현식/(http|https|ftp|telnet|news|mms):\/\/[^\"'\s()]+/i 2. 프로그래머스 [3차] 파일명 정렬 문제에서 참고const files = ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]let answer = [];files.forEach(file => { let matc..
[알고리즘] 유클리드 거리 & 맨해튼 거리 https://school.programmers.co.kr/learn/courses/30/lessons/67256 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제를 풀며 키패드 간의 거리를 계산하기 위해서는 두 좌표(이전 키패트와 현재 키패드의 거리)의 거리를 계산해야한다고 생각해 유클리드 거리를 사용했지만 제대로 풀리지 않았다.고려하지 못했던 것은 유클리드 거리는 대각선 이동을 포함한 직선 거리를 계산하기 때문에, 수평 및 수직 방향으로만 이동 가능한 키패트 문제에서는 실제 이동 거리와 맞지 않는다는 것이다. 그래서 맨해튼 거리를 사용했더니 문제없..
[알고리즘] 정렬 (개선 ver) 앞서 소개한 정렬에 대해 공부하며 개선된 방식을 소개해볼까 한다. 병합 정렬 (개선 ver)첫째로, 이전 글에서 작성한 병합 정렬 코드의 성능 최적화를 위해 다음과 같은 방법을 사용했다. 임시 배열 사용: 병합 과정에서 사용할 임시 배열을 미리 할당하여 메모리 할당을 최소화배열 복사 최소화: 병합 과정에서 정렬된 배열을 원본 배열로 복사하는 작업을 최소화인플레이스 병합: 병합 과정에서 인덱스를 사용하여 배열 요소를 직접 교환하여 성능을 개선아래는 코드 예시이다.function mergeSort(arr) {if (arr.length = rightEnd) {return;}let mid = Math.floor((leftStart + rightEnd) / 2);sort(arr, tempArray, leftSta..
[알고리즘] 간단한 식 계산하기 (+ 사칙연산) https://school.programmers.co.kr/learn/courses/30/lessons/181865# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  해당 문제는 아주 간단한 문제이다. 두가지 숫자의 합, 곱, 빼기를 구하면 되는 문제였다. 그렇기에 내 맘대로 몇가지 규칙을 더해봤다.더한 규칙은 다음과 같다.모든 사칙연산이 등장할 수 있다 ( +, -, * / )사칙연산은 하나가 아닌 여러개가 등장할 수 있다. (예를 들어 '15 + 12 - 7 * 3 * 1' 이 들어오면 6을 리턴하도록 한다)단순했던 문제가 새로운 규칙을 더하자마자 조금 ..
[알고리즘] 우선순위 큐 구현 (더 맵게) https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   해당 문제를 풀기 위해 우선순위 큐를 직접 구현해보았다.안타깝게도 자바스크립트에는 내장된 우선순위 큐가 없기에 직접 구현해야했다...보시다시피 우선순위큐만 구현하고 나면 그 다음부터는 그저 큐에서 두가지를 뽑고 계산하여 삽입한다. 구현한 것은 minHeap이기에 최소값이 가장 첫번째 요소로 지정되어 있을것이다.그렇다면 큐의 첫번째요소(최솟값)이 가장 주어진 K값이상인지만 확인해주면 정답을 구할 수..